Consideraciones metacognitivas sobre Problem Solving

Consideremos las siguientes proposiciones:

Proposición 1: En cualquier conjunto de $n+1$ números naturales siempre hay dos cuya diferencia es múltiplo de $n$.

Proposición 2: Cualquier número natural $n$ tiene un múltiplo $kn$ formado únicamente por ceros y unos (en su representación usual del sistema decimal).

¿Qué relación hay entre estas dos afirmaciones? Lo primero que se nota es que ambas contienen la frase "múltiplo de $n$"

Recordemos que la primera afirmación se demuestra por el principio de pichoneras: hay dos con el mismo residuo al dividir entre n, por lo tanto...
Desearíamos aplicar el mismo método para demostrar la segunda. (Si tuviera algunos huevos, podría tener unos huevos con jamón... si tuviera algo de jamón --Groucho Marx.) Si tuviera que la diferencia de dos números fuese de ceros y unos, el problema quedaría resuelto... si pudiera ligar esos números con $n$. ¿La diferencia de qué números resulta en ceros y unos? La respuesta fácil es: dos de la forma $11...1$. Ello sugiere considerar la sucesión $1, 11$,...,$11...1$ de $n+1$ números naturales...

\[x_1 = 1, x_2 = 10 + 1, x_3 = 10^2 + 10 + 1, ... x_{n+1} = 10^n + ... + 10 + 1\]

Si consideramos esos $n+1$ números en el marco de las clases residuales módulo$n$, es decir, en el contexto de $Z_n$, entonces es claro que debe haber al menos dos en la misma clase, digamos $x_k=x_l$ $\pmod{n}$. Y si $k < l$, entonces $x_l-x_k=11...100...0$, con $l-k$ unos y $k$ ceros.

Ahora bien, puesto que $x_k=x_l(modn)$, entonces $x_k-x_l$ pertenece a la clase residual del cero (módulo $n$). Es decir, $x_k-x_l$ es múltiplo de $n$ y está compuesto únicamente de ceros y unos.

Este problema de concurso es más o menos bien conocido. Lo hemos escogido para ilustrar una característica de muchos problemas de concurso: lo que se tiene que demostrar es un caso particular de lo que un recién llegado (un novicio) entiende que debe demostrar.

En este caso, con "formado únicamente con ceros y unos" se entiende un número como $1000110...$, donde los ceros y unos no tienen ningún patrón de colocación en la cadena de ceros y unos (puesto que no se da ninguna restricción sobre la forma de ese patrón, y ni siquiera se dice que debe tener uno).

Pero lo que tiene que hacer el cognizador resolvedor de problemas es buscar que lo que se pide demostrar se cumpla con el patrón más simple posible. Un patrón donde sea posible pensar el problema. Y ese patrón es precisamente el de un número compuesto de dos bloques: $k-l$ unos al principio y $k$ ceros al final.

Muchas veces se pueden encontrar variaciones de un mismo problema a partir de un mismo teorema muy conocido. Veamos este otro problema de concurso, variante del recién considerado:

Proposición 3: En cualquier conjunto $S$ de $n$ números enteros, hay un subconjunto cuyos elementos suman un múltiplo de $n$. ¿Qué tienen en común las tres proposiciones enunciadas hasta ahora.

En particular, ¿qué tienen en común las proposiciones 1 y 3? Enunciemos de nuevo la proposición 1: "

En cualquier conjunto de $n+1$ números naturales siempre hay dos cuya diferencia es múltiplo de $n$"

De nuevo se recurre a considerar el conjunto $S$ de $n$ elementos en el contexto de las clases residuales módulo $n$. Claramente son a lo más $n$ clases. Y si uno de los elementos del conjunto $S$ es múltiplo de $n$, ya no hay nada que probar.

Entonces, basta con considerar el caso en que ningún elemento en $S$ es múltiplo de $n$. En este caso, se tendrían $n$ clases residuales todas distintas de cero:$1,2,...,n-1$. Pero son $n$ residuos. Por lo tanto dos de ellos son iguales. De aquí que la diferencia de esos dos números es divisible entre $n$. Surge una pequeña dificultad: queríamos la suma de elementos de un subconjunto de $S$.

¿Nuestro plan previo de demostración ha fracasado? La verdad sí. Pero, del fracaso se aprende. Todavía no está todo perdido... Para considerar las sumas de subconjuntos podemos intentar la siguiente transformación:

Sea $S=\{x_1, x_2,...x_n\}$, y consideremos las sumas parciales $y_1 = x_1$, $y_2 = x_1 + x_2$, ...$y_n = x_1 + x_2 +... + x_n$.

Tenemos entonces las sumas de los elementos de $n$ subconjuntos de $S$. Pero notemos que no son cualesquiera $n$ subconjuntos, sino $n$ subconjuntos elegidos según las necesidades del problema. De nuevo, consideremos las sumas $y_i$ en el contexto de las clases residuales módulo $n$. Y tenemos a lo más $n$ clases. Si alguna suma $y_i$ pertenece a la clase del cero (módulo $n$), ya no hay nada que demostrar. De otra manera, todos los $n$ residuos son no nulos, y dos de ellos tienen que ser iguales. Suponiendo que las sumas $y_k$ y $y_l$ pertenecen a la misma clase residual, entonces $y_l-y_k=x_1+x_2+...x_{l-k}$ es múltiplo de n. Pero $x_1,x_2,...,x_{l-k}$ forman un subconjunto de $S$. Y la demostración ha terminado.

Notemos que en ambos problemas considerados arriba, la clave de su solución es un teorema bien conocido. Son de hecho refinamientos de un principio de resolución de problemas de combinatoria muy conocido (pichoneras). En el problema de los ceros y los unos, se busca el patrón más simple para cumplir la condición (primero unos y después ceros). En el de las sumas, los subconjuntos a considerar no son subconjuntos generales, son subconjuntos de un cierto tipo. Bajo la biyección generadora de subconjuntos --$f(x_i)=1$ si $x_i$ en el subconjunto, y 0 de otra manera--, los subconjuntos considerados son de hecho los mismos números que se consideraron en el primer problema:

1................$x_1$
11...............$x_1, x_2$
111..............$x_1, x_2, x_3$
. . . .
111...1..........$x_1, x_2,...,x_n$.

Pero podemos dar un paso más en el acercamiento entre los dos problemas: el $11$ lo podemos ver como $10+1$, el $111$ como $100+10+1$, etc. Y, bajo esta perspectiva, el problema de los ceros y los unos es un caso particular del de las sumas: $x_i=10^{i-1}$.

La moraleja es que todo problema de concurso es fácil... si el cognizador resolvedor de problemas puede verlo desde la perspectiva correcta... y si tiene el entrenamieto suficiente para poder traer a presencia esa perspectiva...

Nota: Las proposiciones 2 y 3 se pusieron como problemas en el examen selectivo 4 (para veteranos).

Los saluda jmd