Solución del problema de marzo, 2002

A su enemigo se le da a escoger 2000 números enteros entre el 1 y el 3000. Su trabajo es encontrar una subsecuencia de 1000 números de los de enemigo en tal forma que resultan alternados: non, par, non, par,...cuando se les enumera en su orden natural. Pruebe que no importa que tan ingenioso es su enemigo, usted siempre podrá hacerlo.

Agradecemos a Aart Blokhuis de la Universidad de Tecnología de Eindhoven por el problema de marzo. El hizo este problema para la Olimpiada de Matemáticas de Holanda. Recibimos cinco soluciones este mes:

Francesco Barioli (Regina)
Juan Mir Pieras (España)
Penny Nom (Regina)
Alexander Potapenko (Russia)
Gordon Turpin (Toronto)

Dos de éstas fueron ingeniosas y muy similares, pero las otras fueron ingeniosas y muy diferentes una de la otra. Es interesante revisar las cuatro soluciones y ver que tienen en común.

Solución 1. Enviada independientemente por Francesco Baroli y Juan Mir Pieras.

Cogemos los números del 1 al 3000 y los separamos en parejas de la siguiente manera: (1,2),(3,4),(5,6), ... ,(2999,3000)

En total tenemos 1500 parejas.

Lo que hace nuestro enemigo (elegir 2000 números) es equivalente a eliminar 1000 números. Entonces, con nuestras parejas pueden pasar tres cosas: - se han eliminado los dos números de la pareja - se ha eliminado uno de los números de la pareja - no se ha eliminado ninguno de los números de la pareja Por eso, nuestro enemigo, eliminando mil números, como mucho ha desbaratado mil parejas, así que nos quedan como mínimo quinientas parejas completas. Cogemos quinientas de esas parejas completas, y así tenemos mil números que, ordenados, siguen la secuencia impar-par-impar-par-...-impar-par.

Solución 2. Submitted by Gordon Turpin.

Considere la secuencia de números escogidos por el adversario en orden natural. La secuencia completa exhibe un orden non-par si no fuera por las secuencias de números faltantes (números no escogidos). De éstas secuencias continuas de números faltantes, notamos que

Solamente secuencias de longitud non pueden interrumpir la forma non-par de números escogidos

Justificación: si un número n es seguido de un número par (digamos 2k) de números faltantes, entonces el próximo número sería n + 2k +1, el cual tendría paridad diferente, de manera que se preserva la forma non-par. Un argumento similar muestra que las secuencias de longitud non interrumpen la forma non-par.

Escogemos nuestra subsecuencia de la secuencia del adversario como sigue: quite los números escogidos que están inmediatamente después de cada secuencia de longitud non de números faltantes. Esto cambia todas las secuencias de números faltantes de longitud non en secuencias de números faltantes de longitud par y nos cuesta un número escogido por cada conversión de longitud non a longitud par. La secuencia mas corta de números faltantes de longitud non tiene longitud 1. Hay 1000 números faltantes en total, así que a lo más 1 000 secuencias de longitud non. Cambiando todas las secuencias de longitud non a longitud par causará entonces que a lo mas 1 000 números sean quitados de la secuencia de 2 000 números escogidos por el adversario.

Nos quedan por lo menos 1000 números en formación non-par.

Solución 3. Enviada por Alexander Potapenko

Nuevamente veamos los agujeros en la secuencia escogida por el enemigo, pero en forma diferente: La secuencia es x1, x2, ..., x2000, y ponemos
y1 = x1 - 0, y2 = x2 - x1, y3 = x3 - x2, ..., y2000 = x2000 - x1999. Entonces por cada n tenemos

xn = y1 + y2 + ... + yn. Si los números nones en la secuencia y con yn1, yn2, ..., yna, entonces xn1, xn2, ..., xna es la secuencia alternante entre los números non y par; es suficiente mostrar que a >= 1000.

Para este propósito, definimos Ynon como el promedio de nos números nones en la secuencia y, y Ypar como el promedio de los números pares en la secuencia y. Por supuesto que si la secuencia y no contiene ningún número par, entonces Ypar no existe, pero entonces a = 2000 y con esto terminámos.

Si no, tenemos Ypar >= 2. And since y1 + y2 + ... + y2000 = x2000 <= 3000, , el promedio de todos los números en la secuencia y es a lo mas  3/2, por lo tanto Yimpar <=  3/2. En particular esto muestra que Yimpar < Ypar. De la desigualdad a Yimpar + (2000-a)Ypar <= 3000, Obtenemos

Solución 4. Enviada por Penny Nom

Penny nos envió una variación del argumento de Alexander, mostrando que en efecto, por lo menos 999 de las diferencias y2, y3, ..., y2000 son iguales a 1:
tenemos

y2 + y3 + ... + y2000 = x2000 - x1 <= 2999. Si k de las y2, y3, ..., y2000 son iguales a 1 y las otras 1999 - k son por lo menos 2, entonces el término de la izquierda es por lo menos k + 2. (1999 - k), así que la desigualdad de arriba da k + 2.(1999 - k) <= 2999; esto es, k >= 999.

El resto de su argumento es como sigue: considere la subsecuencia mas larga a1, a2, ...,ap de números alternados entre nones y pares. Entonces los términos xi que están antes de a1 deben todos tener la misma paridad como a1, así que xi+1 - xi es por lo menos 2. Similarmente, los términos xi que están después de ap todos tienen la misma paridad que ap, asi que xi - xi -1 es por lo menos 2. De aj a aj+1, los términos xi pueden cambiar paridad solamente una vez (de otro modo sería imposible agrandar nuestra subsecuencia), así que hay a lo mas un término xi - xi -1 igual a 1. Por lo tanto, p - 1 es por lo menos 999, y p es por lo menos 1000.

Note que la secuencia construida con el argumento de Penny podría empezar con un número par. Una ligera variación en el argumento sería necesaria para mostrar que hay una subsecuencia alternante de 1000 términos con un número non. (Puede usted encontrar esta modificación?). Por otra parte, combinando la solución de Penny con las soluciones previas, encontramos que si la subsecuencia alternante mas larga empieza con un número par, entonces contiene por lo menos 1001 términos