Llegó la hora de dar la solución al problema planteado en Cómo resolver un juego de monedas con inducción matemática (I). Como muchos habréis intuido, necesitamos un número impar de caras en una fila, para que esta pueda vaciarse por completo. La cuestión es cómo demostramos que esta afirmación es cierta. Aquí es donde entra en juego la inducción matemática.
Ya sabemos que necesitamos una proposición, que dependa de un entero positivo:
P(n): «Toda fila de n monedas con un número impar de caras es vaciable»
En este caso utilizaremos el Principio de inducción fuerte.
Obviamente (esta palabra nunca les gusta a los alumnos) P(1) se cumple; pues si la fila sólo contiene una moneda, la podremos eliminar sólo si es cara. Ahora consideremos una fila de $k>1$ monedas, donde suponemos que para toda fila de longitud menor o igual que $k$ la podemos vaciar si tiene un número impar de caras. Veamos que ocurre cuando tengamos $k+1$ monedas en nuestra fila.
Supongamos que nuestra fila de $k+1$ monedas tiene un número impar de caras. Entonces elegimos la primera cara presente de izquierda a derecha. Puede darse dos casos. Que la primera cara sea la primera moneda(1) o que no(2).
(1)C*** ó (2)+***C***
Si es la primera moneda, caso (1), al eliminarla y darle la vuelta a la contigua sucederá que esta es cara o cruz.
(1)C***-> (1)C** ó (2)+**
Si es cara repetimos el proceso hasta vaciar la fila o que aparezca una cruz, y en tal caso, continuaríamos como en el caso (2).
Resulta que nuestra cara no es la primera moneda, caso (2).
******C******
Al eliminarla volteamos las contiguas y tendremos dos nuevas filas, resultado de la eliminación de la cara.
«*****C» y «{C ó +}*****»
Las dos nuevas filas en las que se ha troceado la fila original, tienen una cantidad menor que $k$ de monedas. Y resulta que las dos nuevas filas tienen una cantidad impar de monedas. La primera subfila, la que resulta a la izquierda de la cara eliminada, porque sólo tendrá la cara que acabamos de sacar al darle la vuelta a la cruz contigua a la cara eliminada. Del mismo modo, la segunda subfila, la situada a la derecha, porque el número impar de caras se mantiene al darle la vuelta a la contigua a la eliminada. Expliquemos esto.
Si «{C ó +}*****» resulta «C*****», entonces la cara eliminada reaparece manteniendo el mismo número de caras impar que habían antes de la eliminación.
Si «{C ó +}*****» resulta «+*****», entonces la eliminación de la cara a provocado que la cara contigua pase a cruz, con lo cual restamos dos caras del computo inicial de caras, antes de la eliminación. Si al número impar de caras le restamos dos, seguiremos teniendo un número impar de caras.
Por la hipótesis de inducción, las dos nuevas subfilas, como tienen un número impar de caras, podrán ser vaciables completamente. Por tanto, habremos vaciado toda la fila y quedará probado para la fila con $k+1$ monedas. Hemos concluido el paso de la inducción que nos lleva a justificar que es válido para toda fila de n monedas con un número de ellas mostrando la cara.
Con lo dicho, necesitamos un número impar de caras; es decir, si la fila tiene un número impar de caras, seguro que la podremos vaciar. Pero, ¿puede vaciarse en algún caso de que tenga un número par? En el ejemplo de la primera entrada vimos un caso de un número par de caras que no tenía solución. ¿Podemos afirmar que cualquier fila con un número par de caras no será vaciable? Ya tenemos otro problema planteado. Se atreven.
Esta entrada participa en la Edición 8.1 del Carnaval de Matemáticas cuyo anfitrión es Tito Eliatron Dixit.