El difícil arte de construir pichoneras

El adolescente aficionado a las matemáticas no tiene por qué compartir las nostalgias de los profes. Así que tómese esta imagen sólo como una invitación a visitar mi dokuwiki (que Valentina me hizo el favor de hospedar en su espacio virtual). La tengo un poco olvidada pero... visítela el ciberlector clickeando aquí



He seguido leyendo en estos días el libro 500 retos (ver abajo) y puedo recomendarlo sin reservas. La solución al siguiente problema (con comentarios insertados) es un ejemplo del arte de razonamiento por indicios (pistas que sólo la experiencia en solución de problemas enseña a interpretar).

Comentarios previos

Un principio lógico de sentido común, formalizado como técnica de solución de problemas en Combinatoria y Matemáticas Discretas, es el denominado Box Principle o Pigeon Hole Principle (que se puede traducir como principio de las casillas y principio de las pichoneras, respectivamente).

El principio nos dice que si hay n pichoneras (nidos) y n+1 pichones (palomas)entonces en uno de los nidos van a dormir 2 palomas. (Formalmente se plantea de otra manera pero para solución de problemas con este planteamiento folklórico basta.)

Permítaseme compartir un ejemplo tomado del Barbeau y Klamkin (E. Barbeau, M. Klamkin, W. Moser, Five Hundred Mathematical Challenges, MAA, 1995) para ilustrar el hecho de que, a pesar de que el principio es una verdad evidente, lo que no es evidente es la forma de construir las pichoneras que hagan el truco de la demostración pedida.

Problema. De cualquier subconjunto de tamaño 7 tomado de {1,2,...,126} se pueden elegir 2 elementos a y b tales que b/a es mayor que 1 pero no mayor que 2. Se pide demostrar esta afirmación (proposición).

Comentarios previos 2.

La primera cosa que debe hacer el cognizador adolescente que aspira a ser una superestrella en solución de problemas es experimentar ejemplificando. Y esto con la finalidad de llegar a una comprensión cabal del enunciado. (Bueno, creo que antes que eso debe estar la disposición de ánimo y fuerza de voluntad --y espíritu de lucha-- que lo haga inmune a los espantajos --es decir, el cognizador no debe asustarse.)

Sugerencia:

¿Puedes poner la condición de otra forma aunque equivalente --pero más legible, es decir, más comprensible para tí? ¿Puedes verbalizar la condición equivalente?

Problema asociado:

Tratar de construir un subconjunto de tamaño 7 con los números del 1 al 126 y que no cumpla la condición dada. (Primero puede ser conveniente tomar un subconjunto cualquiera de tamaño 7 y ver si cumple la condición.)

Solución corta:

Las 6 pichoneras {1,2}, {3,4,5,6}, {7,...,14}, {15,...,30}, {31,...,62}, {63,...,126} hacen el truco. (Nótese que cada pichonera tiene la propiedad de que contienen un x tal que 2x también está en la pichonera. Además, la unión de ellas forman {1,2,...,126}.)

Nota 1:

La condición exigida en el problema se puede poner de otra forma multiplicando por a en la doble desigualdad 1 < b/a < (o igual)2. Es decir, la condición sería equivalente a a < b < (o igual)2a. La cual ya es más fácil de verbalizar: "existen a y b tales que b está entre a y 2a (y, si acaso, b=2a)"

Nota 2:

Si tratamos de construir un subconjunto de tamaño 7 que no cumpla la condición, tarde o temprano vamos a llegar a {1,3,7,15,31,63,127}. Y esto es ya iluminante, pues se puede ver que ningún elemento del conjunto tiene su duplo en el subconjunto. De aquí se podría eventualmente llegar a la idea de que los conjuntos
que cumplen la condición serían aquéllos en los cuales hay un elemento que tiene su duplo dentro del conjunto. (Las pichoneras construidas en la solución cumplen esta condición de forma ajustada --es decir, sólo tienen un elemento de ese tipo.)

Nota 3:

En los problemas de este tipo --en donde el principio de las pichoneras los resuelve trivialmente-- la forma de su redacción sugiere que se usen pichoneras. (Por supuesto que para lograr captar la sugerencia a partir del enunciado el cognizador requiere de la experiencia de haber resuelto unos 20 problemas elementales de este tipo --a través de la experiencia se adquieren la mayoría de los códigos.)

Nota 4:

Este tipo de problemas puede llegar a ser desesperante debido al hecho de que uno sabe que la afirmación que se trata de demostrar es cierta --por ejemplo, después de haber construido (en este caso) el conjunto de la nota 2, se logra la revelación... "¡claro! no es posible de otra manera porque faltarían elementos (el 127)", pero de ahí a demostrarlo formalmente hay una considerable distancia.