Sergio piensa un número entero positivo $S$, menor o igual que $100$. Iván debe adivinar el número que pensó Sergio, utilizando el siguiente procedimiento: en cada paso, elige dos números enteros positivos $A$ y $B$ menores que $100$, y le pregunta a Sergio cuál es el máximo común divisor entre $A+S$ y $B$. Dar una secuencia de siete pasos que le asegure a Iván adivinar el número $S$ que pensó Sergio.
Aclaración: En cada paso, Sergio responde correctamente la pregunta de Iván.
Lo que me llevó a pensar por dónde podía venir la idea para resolverlo fue que en el enunciado, [math]S \leq 100 y que tenemos sólo [math]7 pasos para llegar a adivinar el número. Como [math]2^6 \leq 100 y [math]2^7 \geq 100 se me vino a la cabeza que la solución debía andar por ahí (por ahí hay otra más simple, no sé).
Notemos que al factorizar un número, éste es de la forma: [math]n = 2^k \cdot a donde [math]a es [math]Impar (O sea, que [math]2^k es la mayor potencia de 2 que divide al número y [math]a es el producto de todos los factores primos del número que no son [math]2). Ahora, veamos qué ocurre al sumar [math]2^k al número:
[math]n + 2^k = 2^k \cdot a + 2^k = 2^k (a+1). como [math]a es [math]Impar entonces [math]a+1 es [math]Par, de acá que [math]a+1=2b para algún [math]b (que no necesariamente es impar). Entonces tenemos que:
[math]n + 2^k = 2^k \cdot 2 \cdot b = 2^{k+1} \cdot b
Entonces, al sumar la mayor potencia de 2 que divide al número (llamémosla [math]2^k), obtenemos un número divisible por una potencia de 2 más grande (por lo menos [math]2^{k+1}).
Sabiendo ésto hacemos el siguiente procedimiento: En el Paso 1 preguntamos por [math]MCD (S+1, 64) (O sea, que [math]A = 1 y [math]B =64, de ahora en adelante se dará por entendido cuál es [math]A y cuál es [math]B), si la respuesta es [math]1, 2, 4, 8, 16 preguntamos por el [math]MCD (S+1 + q_{1}, 64), con [math]q_{1} = 1, 2, 4, 8, 16 respectivamente en cada caso (porque el [math]MCD entre un número y [math]64 será la mayor potencia que divida al número hasta [math]64), en el Paso 2 preguntamos por el [math]MCD (S+1+q_{1}+q_{2}, 64), donde [math]q_{2} es la mayor potencia de 2 que divide a [math]s+1+q_{1}, y así, repitiendo estos pasos, nos aseguramos que como mucho en el Paso 6 tenemos un número de la forma [math]S + m tal que [math]32|S+m. Entonces tenemos 2 cursos a seguir:
CASO 1: Si en algún momento nos respondieron que [math]MCD (S+m, 64) = 64 entonces en el paso siguiente preguntamos [math]MCD (S+m+1, 5). Si la respuesta es [math]5 entonces [math]S=64-m, si es [math]1, entonces [math]S=128-m[math](*)
CASO 2: Si en algún momento nos respondieron que [math]MCD (S+m, 64) = 32 entonces en el paso siguiente preguntamos [math]MCD (S+m, 3). Si la respuesta es [math]1 entonces [math]S= 32-m, si la respuesta es [math]3 entonces [math]S = 96 -m[math](**). Notemos que el valor de [math]m lo vamos dando nosotros así que podremos despejar.
[math](*) Nuestro valor de [math]m que vamos dando va desde [math]1 hasta [math]32, entonces al máximo [math]S+m que podremos llegar será [math]132, entonces hay dos valores para [math]S+m donde [math]MCD (S+m, 64) = 64, que son [math]64 y [math]128
[math](**) Los únicos números entre [math]1 y [math]132 tales que [math]MCD (S+m, 64) = 32 son [math]32 y [math]96, ojo ([math]32|64 y [math]32|128, pero el [math]MCD en ese caso da [math]64).
De esta forma nos aseguramos en como mucho siete pasos adivinar el número [math]S que pensó Sergio.
En el primer paso Iván elige [math]A=B=2, entonces [math]S\equiv S+2\equiv (S+2;2)\pmod 2. Conociendo [math]x en [math]S\equiv x(2^n), en el paso [math]n+1 Iván elige [math]A=2^n-x y [math]B=2^{n+1}. Afirmo que de esta forma Iván puede conocer el resto de [math]S en la división por [math]2^{n+1}
En efecto, como [math]S\equiv x(2^n)\Rightarrow S-x\equiv 2^n\equiv 2^{n+1}\equiv 0(2^n), entonces solo puede ser [math](S+2^n-x;2^{n+1})=0\vee 2^n. Si [math](S+2^n-x;2^{n+1})=0 entonces [math]S-x+2^n\equiv 0(2^{n+1})\Rightarrow S\equiv -2^n+x\equiv 2^n+x(2^{n+1}), sino [math]S-x+2^n\equiv 2^n(2^{n+1})\Rightarrow S\equiv 2^n-2^n+x\equiv x(2^{n+1}). En cualquier caso, Iván conoce el resto de [math]S en la división por [math]2^{n+1}. Entonces después del paso [math]6 Iván conoce el resto de [math]x en la división por [math]2^6=64
Como [math]S\equiv x(64), tenemos que [math]S=x\vee S=64+x. Si [math]x>36 entonces [math]64+x>64+36=100, por lo que [math]S=x. Si [math]x=0 entonces [math]S es múltiplo de [math]64, como el único múltiplo de [math]64 en [math][1;100] es [math]64 entonces [math]S=64. Por lo que Iván ya sabe el valor de [math]S y no importa cuál sea su última pregunta
Si [math]1\leq x\leq 34 entonces Iván elige [math]A=1 y [math]B=64+x+1. Si [math](S+1;64+x+1)=64+x+1 entonces [math]S+1=64+x+1\Rightarrow S=64+x (ya que el único múltiplo de [math]64+x+1 en [math][1;100] es [math]64+x+1), sino [math]S=x
Si [math]x=35 o [math]x=36 entonces Iván elige [math]A=x y [math]B=2x. Vemos que [math](35+35;70)=(70;70)=70 y [math](64+35+35;70)=(134;70)=2; y vemos que [math](36+36;72)=(72;72)=72 y [math](64+36+36;72)=(136;72)=8, entonces Iván puede conocer el valor de [math]S.
Queda demostrado que con esta secuencia de pasos Iván puede conocer con certeza el número que pensó Sergio.
