Hace unos dos años, empecé a pensar en el siguiente problema: te dan una $N$ y un $S$ , enteros positivos. Se comienza con un $N$ -que tiene etiquetas enteras positivas en cada vértice, tales que las etiquetas suman $S$ . Un "movimiento" es la sustitución de la etiqueta de un vértice por la diferencia positiva de las etiquetas de sus dos vértices adyacentes. Ganas si puedes exhibir una secuencia de movimientos tal que todas las etiquetas de los vértices sean cero al final.
Se trata de una generalización del problema B3 de la USAMO de 2003,
"En cada vértice de un hexágono se escribe un número entero positivo. Un movimiento consiste en sustituir un número por la diferencia (no negativa) entre los dos números de los vértices adyacentes. Si los números iniciales suman $2003^{2003}$ , demuestran que siempre es posible hacer una secuencia de movimientos que termine con ceros en cada vértice".
El problema de USAMO en sí mismo puede responderse afirmativamente haciendo un algoritmo codicioso modificado para la mayoría de las jugadas, mostrando que siempre hay una jugada en la que se puede reducir el problema a una suma menor mientras se cambian las paridades sistemáticamente, y luego haciendo un trabajo de casos para el "juego final" para mostrar que cada configuración de 1's y 0's (o k's y ceros, los casos son, por supuesto, equivalentes) puede reducirse a todos los ceros.
Es fácil comprobar que para $n=4$ y $S$ impar, hay una estrategia ganadora. Tengo muchas pruebas de simulación/numéricas y algunas ideas a medias que sugieren que, en general, hay una estrategia ganadora si y sólo si $N$ y $S$ tienen paridades opuestas. Pero en dos años de volver a ella de forma intermitente, no he avanzado mucho. Está abierto, por lo que sé, aunque eso lo sabía con más seguridad hace dos años que ahora.
¿Ideas?
