Rompecabezas | Los números restantes

Sahil y Amrit son amigos. Un día, Amrit llega a la casa de Sahil para llevarlo afuera para que puedan jugar juntos. Pero Sahil niega diciendo que no jugará a menos que llegue a la solución del problema con el que está atascado. Entonces, Amrit decide ayudarlo. El problema es que, dados los primeros 50 números naturales, es decir, 1, 2, . . . . . . . 49 , 50 que están escritos en una pizarra. Selecciona dos de los números en la pizarra, digamos a y b , escribe el valor absoluto de su diferencia |a – b| en la pizarra y luego borre tanto a como b. Aplique la operación anterior 49 veces. Determine todos los valores posibles del número restante que se pueden obtener de esta manera.

Solución: se puede obtener cualquier número entero positivo impar menor que 50.

Explicación:
1) Como inicialmente los números del 1 al 50 están en el tablero, entonces la suma inicial de los números en el tablero es igual a

         1 + 2 + 3 + 4 + ———- +50 = 1275, que es impar.

2) Como en cada operación seleccione dos números en la pizarra, es decir, a y b donde a<=b, escriba el valor absoluto de su diferencia |a – b| en la pizarra y luego borre tanto a como b.
Por eso,

        = – a – b + |a – b|

3) Como a<=b, por lo tanto, |a – b| = -(a – b) = b – a ,lo que implica:

          = – a – b + b – a = – 2a ————(1)

4) Del resultado 1, se puede concluir que cada operación de reemplazar a y b por |a – b|, donde a <= b sin pérdida de generalidad, disminuye la suma en 2a

5) A partir del resultado 1, está claro que la nueva suma debe ser impar si la suma anterior era impar y, por lo tanto, ningún número par puede resultar de aplicaciones repetidas de tal operación a partir de 1275.

6) También dado que todos los números en el tablero son siempre no negativos. También son menores o iguales a 50, ya que |a – b| es siempre menor o igual que el máximo de a y b para a y b no negativos. Ahora, cualquier entero impar del 1 al 49, inclusive, se puede obtener aplicando la operación del rompecabezas 49 veces.

7) Sea k tal número. Esto se puede obtener en la primera iteración restando 1 de k + 1 como | 1 – (k + 1) | = k.

8) Luego, aplique la operación a los pares de los números enteros consecutivos restantes,

(2, 3), (4, 5), . . . , (k – 1, k), (k + 2, k + 3), . . . , (49, 50), para obtener 24 unos en el tablero mientras se borran los pares anteriores.

9) Como hasta ahora, la operación se aplica 25 veces (1 en el paso 7 y 24 en el paso 8). Aplicando la operación 12 veces más a los 24 pares de unos se obtienen 12 ceros, que pueden reducirse a un solo cero después de aplicar la operación 11 veces.

10) Después del paso 9, el número total de veces que se aplica la operación es 48. Finalmente, aplicando la operación a los dos números restantes, k y 0, se obtiene k.

Como k es impar, cualquier entero positivo impar menor que 50 puede obtenerse después de aplicar la operación dada 49 veces.

Referencias: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin