Inicialmente en el pizarrón están escritos en una línea y en algún orden todos los números enteros del [math]1 al [math]2002 inclusive, sin repeticiones.
En cada paso se borran el primero y el segundo número de la línea y se escribe al principio de la línea el valor absoluto de la resta de los dos números que se acaba de borrar; los demás números no se modifican en ese paso, y queda una nueva línea que tiene un número menos que la del paso anterior.
Luego de realizar [math]2001 pasos, queda sólo un número en el pizarrón.
Determinar todos los posibles valores del número que queda en el pizarrón al variar el orden de los [math]2002 números de la línea inicial (y realizar los [math]2001 pasos).
Sea [math]S_1 la suma de los números cuando no se realizaron operaciones
Sea [math]S_{2003-k} la suma de los numeros cuando quedan [math]k números en el pizarron
Luego si [math]x es el numero que queda solo [math]S_{2002}=x
Ademas si entre dos operaciones de usan los números [math]a,b entonces la nueva suma es [math]S_{l+1}=S_l-a-b+|a-b|
Hay dos opciones:
Si [math]a>b entonces [math]S_{l+1}=S_l-a-b+a-b=S_l-2b
Si [math]a<b entonces [math]S_{l+1}=S_l-a-b-a+b=S_l-2a
Luego la paridad entre las sumas se mantiene
Esto quiere decir que [math]2|S_1-S_{2002}=S_1-x=\frac{2002 \cdot 2003}{2}-x=1001 \cdot 2003 -x
...la idea seria induccion en la cantidad de numeros en el pizarron.
Y diria que dan todos los impares entre [math]1 y [math]2001
Te fijas un par de casos bases y ves que todos los pares/impares(dependiendo de la paridad de la suma) pueden aparecer
Y habria que ver los diferentes casos de la paridad de [math]n y de la suma
Como tenemos [math]2002 y la suma es impar, tomamos [math]n y la suma impar y [math]n+1 par con la suma impar
Como teniamos que podia ser cualquier impar entre [math]1 y [math]n; con [math]n+1 podemosnver que pasa lo mismo
a un orden que nos da [math]1 , le agregamos en [math]n+1 y tenemos a [math]n,[math]..., a un orden que nos da [math]n, le agregamos al [math]n+1 y nos da [math]1
Para terminar, por lo que demostraste antes y pk es una resta no va a ser mayor que n+1 son todos.
Reemplazas [math]n por [math]2001 y listo.
drynshock escribió: ↑Mié 16 Oct, 2024 6:40 pm
Y ahora, no tengo ni idea como se llama esto, si inducción, inducción fuerte, inducción Cauchy, inducción Drynshock ...,
Es obvio que con los pares no se puede, porque la suma se mantiene invariante $\pmod 2$ y la misma, por Gauss, es impar. Luego, veamos que todos los impares cumplen (entre $1$ y $2001$ claro).
Por inducción suponemos que si tenemos los números $1, 2, \dots 4k$ entonces podemos formar todos los pares. Debemos probar, en base a esa hipótesis, que podemos formar todos los pares desde $0$ hasta $4(k+1)$. Sin embargo, vamos a hacer inducción $x4$, primero probar que si eso se cumple, entonces si tenemos los números hasta $4k+1$, entonces podemos formar todos los impares, luego si tenemos todos hasta $4k+2$ todos los pares, y así siguiendo.
Demostración:
Parte 1)
$$1, 2, \dots, 4k, 4k+1$$
Por inducción, existe una permutación de $1, 2, \dots, 4k$ para formar $0, 2, 4, \dots, 4k$, luego podemos formar los números.
$4k+1-0 = 4k+1$
$4k+1-2 = 4k-1$
$\vdots$
$4k+1-(4k) = 1$
Por consiguiente, mediante $1, 2, \dots, 4k+1$ podemos formar todos los impares desde $1$ hasta $4k+1$.
$\blacksquare$
Parte 2)
$$1, 2, \dots, 4k+1, 4k+2$$
Como vimos recién, podemos formar todos los impares, por lo que
$4k+2-1 = 4k+1$
$4k+2-3 = 4k-1$
$\vdots$
$4k+2-(4k+1) = 1$
Entonces, otra vez, podemos formar todos los impares.
$\blacksquare$
Parte 3, a)
$$1, 2, \dots, 4k+2, 4k+3$$
Con la misma idea que antes, podemos formar
$4k+3-1 = 4k+2$
$4k+3-3 = 4k$
$\vdots$
$4k+3-(4k+1) = 2$
De donde, podemos formar todos los pares salvo el cero (con esta lógica), entonces vamos a hacer uso de otra inducción para formar el cero (si, inducción dentro de otra inducción = inducción embarazada).
Parte 3, b)
Consideramos los números en el siguiente orden:
$$4k+3, 4k+2, 4k+1, 4k, \dots, 2, 1$$
y notemos que para $k = 0$ si los números están ordenados de esa forma, obtenemos $3, 2, 1 \Rightarrow 0$. Veamos que:
Y como $|0-4k-1|= 4k-1$ y $4k-1$ es de la forma $4m+3$, entonces esto termina la demostración de que siempre podemos formar un cero. Concluimos que podemos formar todos los pares entre $0$ y $4k+2$
$\blacksquare$
Parte 4, a)
$$1, 2, \dots, 4k+3, 4k+4$$
Se sigue que,
$4k+4-0 = 4k+4$
$4k+4-2 = 4k+2$
$\vdots$
$4k+4-(4k+2) = 2$
Por lo que podemos formar todos los pares entre $2$ y $4k+4$, entonces para terminar nos queda ver que también podemos formar el cero. Para ello, hacemos uso de inducción embarazada.
Parte 4, b)
Ponemos los números en el siguiente orden
Por lo tanto, mediante la suposición de que se podían formar todos los pares desde $0$ hasta $4k$ si teníamos los números $1, 2, \dots, 4k$ probamos que también se podía para $4(k+1)$. Es trivial que para $k = 0$ la lista $0$ cumple, entonces la inducción esta completa. Pero además, en el proceso probamos que podíamos formar todos los impares en los casos de $4k+1$ y $4k+3$, de donde esta claro que podemos formar todos los impares para $1, 2, \dots, 2002$ que era lo que buscábamos.
