Solución del problema de Octubre, 2008

Cualquier sucesión que cumpla
la suma de 7 términos consecutivos cualesquiera es positiva, (1)
y
la suma de 1términos consecutivos cualesquiera es negativa (2)
tiene a lo sumo 16 términos. Para demostrar esto, debemos primero mostrar que ninguna sucesión con 17 términos o más puede satisfacer ambas condiciones, y luego debemos mostrar un ejemplo de una sucesión de 16 términos que satisfaga ambas condiciones (y tal ejemplo lo será también para todas las longitudes menores que 16). Las respuestas recibidas siguieron tres buenos caminos para resolver el problema.

Método 1.
Si hubiera una sucesión de 17 términos a₁, a₂, ..., a₁₇ que cumple las dos condiciones, podríamos ordenar los elementos en una matriz de 11 por 7,

La condición (1) implica que la suma de cualquier fila (y por tanto la de todas las entradas de la matriz) es positiva, mientras que la condición 2 implica que la suma de cualquier columna (y por tanto la de todas las entradas de la matriz) es negativa. La contradicción nos muestra que tal sucesión no puede existir.
Para construir un ejemplo de sucesión de 16 términos que cumpla las dos condiciones, podemos elegir arbitrariamente los valores – positivos – de las sumas de cada una de las 10 filas a_j+1 + a_j+2 + ... + a_j+7 (para j de 0 a 9); por simplicidad, tomemos las 10 sumas igual a 1. Restando pares consecutivos de estas sumas, obtenemos por ejemplo

y deducimos que a_j = a_j+7 para 1 ≤ j ≤ 9. Similarmente, podemos tomar las sumas a_j+1 + a_j+2 + ... + a_j+11 como números negativos arbitrarios (para j de 0 a 5); digamos que todas las sumas son –1. De estas 6 ecuaciones deducimos que a_j = a_j+11. Estas igualdades implican que cada subsucesión de 7 términos consecutivos contendrá cinco a₁ y dos a₃, mientras que las subsucesiones de once términos consecutivos contendrán ocho a₁ y tres a₃; luego,

–5, –5, 13, –5, –5, –5, 13, –5, –5, 13, –5, –5, –5, 13, –5, –5.

Método 2. El método de Bojan Basic.
Basic, Fondanaiche, Lim y Sengupta generalizaron el problema. Encontraron que para dos enteros positivos cualesquiera m y n, la sucesión de números reales más larga tal que la suma de m términos consecutivos es positiva y la suma de n términos consecutivos es negativa tiene

Usaremos la idea de Bojan Basic de definir una sucesión de sumas parciales S_j como

S₀ = 0, S₁ = a₁, S₂ = a₁ + a₂, …, S_j = a₁ + a₂, …,+ a_j .

En lugar de presentar un argumento general, ilustraremos el método con tres ejemplos.

Ejemplo 1. Tomemos m = 3, n = 5. Mostraremos que la sucesión más larga tiene 3+5–1–1 = 6 términos tal como dice (3).

Para ver que ninguna sucesión que satisfaga estas condiciones tiene más de 7 términos, supongamos por el contrario que a₁, a₂, …, a₇ es una tal sucesión. Tenemos la siguiente cadena de desigualdades:

La contradicción 0 < 0 prueba que una sucesión que satisfaga las dos condiciones deber tener menos de 7 términos. Notemos que en (4) llevamos la cadena de desigualdades tan lejos como fue posible usando la condición S_j < S_j₊₃ (S₆ < S₉ no es válido porque S₇ es la suma parcial más larga), y luego trajimos los índices hacia atrás con tantas aplicaciones de la segunda condición S_j₊₅ <S_j como fue posible. La manera más rápida de llevar los indices de nuevo a cerp es usar las sumas parciales positivas n = 5 veces y las negativas m = 3 veces.

¿Como conseguir un ejemplo con seis términos? Si miramos la cadena (4) empezando a la derecha de S₇,

Cualquier elección de números reales que satisfaga (5) va a producir una sucesión de seis terminos que satisface las condiciones iniciales; por ejemplo S₂ puede ser cualquier número real negativo, y S₅ cualquier número entre ése y cero. S_i ponemos S₂ = –2, S₅ = –1, S₃ = 1, S₆ = 2, S₁ = 3, S₄ = 4, usamos S₁ = a₁, a_j₊₁ = S_j₊₁ – S_j, y obtenemos la sucesión 3, –5, 3, 3, –5, 3. Como esta sucesión fue elegida para satisfacer (5), sabemos que la suma de tres términos consecutivos cualesquiera es 1, mientras que la suma de cinco términos consecutivos es -1.

Ejemplo 2. Tomemos m = 4, n = 6. Como mcm (4, 6) = 2, esperamos que la sucesión más larga tenga 4+6–2–1 = 7 términos de acuerdo a (3). Tenemos

lo que muestra que nuestra sucesión no puede tener 8 o más términos (aquí trajimos los índices hasta 0 usando S_j < S_j₊₄ solamente

veces, mientras que usamos S_j₊₆ < S_j

veces). Para producir una sucesión válida de siete termino usamos la cadena de arriba sin S₈, es decir S₂ < S₆ < 0 < S₄ junto con las condiciones restantes S₃ < S₇ < S₁ < S₅. Como estas condiciones son necesarias y suficientes, se puede dar cualquier valor negativo a S₂ con S₃ completamente arbitrario. Si S₂ = – 2, S₆ = –1, S₄ = 1, S₃ = 0, S₇ = 1, S₁ = 2, and S₅ = 3, nuestra sucesión comienza con S₁ = a₁ = 2, y es 2, –4, 2, 1, 2, –4, 2.

Ejemplo 3. El problema original: Tomemos m = 7, n = 11. Como mcm (7, 11) = 1, esperamos que la sucesión más larga tenga 7+11–1–1 = 16 de acuerdo a (3). Como 7 y 11 son corrimos, cualquier sucesión de 17 términos produce una única cadena de desigualdades,

0 < S₇ < S₁₄ < S₃ < S₁₀ < S₁₇ < S₆ < S₁₃ < S₂ < S₉ < S₁₆ < S₅
< S₁₂ < S₁ < S₈ < S₁₅ < S₄ < S₁₁ < 0.

Para un ejemplo con 16 términos eliminamos S₁₇ en la cadena (comenzamos con S₆ y terminamos con S₁₀). Entonces para recuperar la sucesión–5, –5, 13, –5, … que teníamos antes, ponemos S₆ = –12 y hacemos cada S_j en la cadena una unidad más grande que la suma parcial previa en la cadena.

Método 3. Matrices.
Varias respuestas usaban matrices implícitamente. Billion las usó explícitamente. Para ilustrar las idea haremos primero un ejemplo pequeño con m = 2, n = 3; esto es, queremos a_j + a_j+1 positivo para todo j y a_j + a_j+1 + a_j+2 negativo. Esperamos que la sucesión más larga tenga 2+3–2 = 3 términos. Resumimos la información en la ecuación matricial

matrices

donde los bj pueden tomar cualquier valor positivo. Tomemos b_j = 1 para todo j, y resolvamos la ecuación calculando la matriz inversa, que existe porque la matriz de arriba es claramente no-singular:

matrices

La sucesión deseada está en la última columna:–2, 3, –2. Como la matriz de la ecuación anterior lleva a

vemos que cualquier elección de valores positivos para los bj va a producir una sucesión a_j, a_j+1, a_j+2en el orden negativo, positivo, negativo. Si existiera una sucesión a₁, a₂, a₃, a₄, … con más de tres términos que cumple las condiciones, sabemos que a2 tiene que ser positivo como parte de la subsucesión a₁, a₂, a₃, pero también tendría que ser negativo como parte de la subsucesión a₂, a₃, a₄. Como ese patrón no puede preservarse para todo j en una sucesión de más de tres términos, vemos que en efecto la sucesión más larga para las condiciones dadas tendrá necesariamente tres términos.
Para su solución del problema original (con m = 7 y n = 11) Billion usó las ecuaciones matriciales MA = B, A = M^–1B, con

M = matix ,

M^-1 = matix ,

A = [a₁, a₂, …, a₁₆]^t, B = [b₁, b₂, …, b₁₀, –b₁₁, …, –b₁₆]^t. Con b_j = 1 para todo j, recuperó nuestra sucesión

A = [–5, –5, 13, –5, –5, –5, 13, –5, –5, 13, –5, –5, –5, 13, –5, –5]^t.

Con b_j = 2 para j ≤ 10 y bj = 3 para j > 10, encontró que

A = [–12, –12, 31, –12, –12, –12, 31, –12, –12, 31, –12, –12, –12, 31, –12, –12]^t

es también una sucesión aceptable. Nuevamente vemos que cualquier sucesión con más de 16 términos no puede satisfacer las condiciones: a3 tendría que ser positivo por ser parte de la subsucesión a₁, a₂, a₃, …, a₁₆, pero negativo por ser parte de la subsucesión a₂, a₃, a₄, …, a₁₇.