Considere un array de números enteros positivos $A$ de longitud $n$ . Ahora considera el conjunto de sumas de todos los subconjuntos contiguos de $A$ . Por ejemplo, si $A = (1,3,5,6)$ entonces el conjunto sería $S_A = \{1,3,5,6,4,8,11,9,14,15\}$ .
Si las sumas de todos los subconjuntos indexados contiguos son distintas (como en el ejemplo anterior), ¿acaso el conjunto de estas sumas especifican de manera única el conjunto de números enteros en la matriz que las sumas fueron calculado a partir de
Ciertamente podemos calcular el elemento más pequeño de la matriz original ya que es el elemento más pequeño de $S_A$ . Del mismo modo, debe haber un valor en el conjunto original que es el mayor valor en $S_A$ menos el segundo más grande.
Para mostrar una de las sutilezas de este problema, considere $A = (1, 6, 2, 3)$ y $S_A = \{1, 6, 2, 3, 7, 8, 5, 9, 11, 12\}$ . Podemos decir inmediatamente de $S_A$ que $1$ ocurre en algún lugar de $A$ . Del mismo modo podemos decir que $2$ ocurre en algún lugar de $A$ . Pero, ¿qué podemos decir sobre $3$ ? Si $1$ y $2$ estaban al lado de cada uno entonces como $1+2=3$ sabríamos que $3$ no puede estar en $A$ . Pero si $1$ y $2$ no están al lado de cada uno en $A$ entonces sabemos $3$ debe estar en $A$ . ¿Cómo sabemos en qué caso estamos?
La respuesta resulta ser NO . Toma $A = (4, 6, 5, 2, 1)$ y $B = (3, 8, 2, 4, 1)$ . Tenemos eso $S_A = S_B$ pero el conjunto de elementos en $A$ y $B$ son distintos.
