El problema 1 del concurso estatal (OMM Tamaulipas 2011) es más difícil de lo que parece (si se hubiese exigido la demostración). Es el siguiente (elegido de un lote de problemas que le enviaron al delegado desde el comité organizador nacional de la OMM):
En una reunión de 6 personas, éstas se saludaron de mano. Si se sabe que sólo una saludó a todos ¿cuál es el máximo número de apretones de mano que pudo haber en dicha reunión?
Afortunadamente para los concursantes, el criterio de evaluación no exigió la demostración de que la solución (correcta) encontrada fuese realmente la máxima. Y la solución correcta tenía el mismo valor por fuerza bruta (solución gráfica) o usando doble conteo (analítica).
De esta manera, lo que se valoró fueron las habilidades heurísticas de los concursantes en el problem solving (y, quizá su aplomo para enfrentar un problema que, aunque fácil, su enunciado resulta intimidante --pues no hay una ruta obvia hacia la solución). Así y todo, no todos los preseleccionados le sacaron los 7 puntos.
Necesidad de institucionalizar (en el sentido de Brousseau [1])
En lo que sigue presentaré la solución corta y una solución más detallada que incorpora las técnicas del problem solving utilizadas. La solución detallada hace explícitas las técnicas utilizadas para resolver el problema 1 del concurso estatal de la OMM Tamaulipas 2011.
Según la Teoría de las Situaciones Didácticas, la institucionalización (del conocimiento utilizado en la resolución de un problema) es la última etapa de una sesión de enseñanza y está a cargo del profesor.
Las primeras serían: la devolución (también a cargo del profesor), la situación de acción (en la cual el aprendiz, después de haber aceptado el reto de la devolución, pone en acción todos sus recursos para resolver el problema), la situación de formulación o comunicación, y la situación de validación (defensa de la solución).
En la situación de institucionalización (de las técnicas, principios, etc. usados en la solución) el profesor emprende la puesta en común del conocimiento implícito en los procedimientos de solución empleados por los alumnos que aceptaron el reto de la devolución y que pusieron todo su esfuerzo en resolver el problema y que con un poco de suerte llegaron a resolverlo.
Al plantear el problema a sus alumnos, el profesor les está devolviendo --de manera simbólica-- la responsabilidad de su propio aprendizaje. Y, en un concurso de matemáticas, todos los concursantes aceptan esa devolución --ése es uno de los aspectos más satisfactorios de tales concursos para los organizadores.
A riesgo de caer en un parloteo semántico, la solución que presento a manera de institucionalización tiene como propósito deliberado ilustrar el significado de la situación de institucionalización (en el sentido de Guy Brousseau [1]).
Y esto porque, con demasiada frecuencia, en las soluciones oficiales de los problemas de concurso, las técnicas utilizadas se mantienen ocultas. Son soluciones reticentes. Lo cual no necesariamente debe considerarse como algo negativo, y ni siquiera deliberado, por parte de los redactores de la solución. La reticencia es un rasgo cultural central de la comunidad matemática --para bien y para mal. (Ver mi post sobre reticencia [2] y este otro también sobre reticencia [3].)
Así que ésta es una de las contadas ocasiones en que presento una solución detallada --quizá en exceso-- de un problema. Y espero que el cibernauta aficionado a las matemáticas de concurso (y usuario de MaTeTaM) no me lo tome a mal y deje de lado, así sea por esta única vez, la cultura del "pícale" (el apuro por llegar a quien sabe donde).
La solución reticente y la institucionalización
La solución reticente podría ser así:
Sea A la persona que saludó a todas las restantes. Las 5 personas restantes pueden saludar a cuatro de los presentes (cuando mucho), incluyendo a A. Así que $5+5\times4=25$ es el máximo número de apretones "dirigidos" (A saluda a B se cuenta como distinto de B saluda a A). Por tanto, la respuesta es 12 apretones como máximo. Para demostrar que los 12 apretones son posibles basta considerar el siguiente ejemplo: AB,AC,AD, AE, AF, BC, BD, BE, FC, FD, FE, DC.
La solución detallada que se presenta a continuación muestra lo que queda oculto en la reticente, es decir, muestra el porqué de la división entre dos y el cómo se logra el ejemplo. En ambos casos está por detrás una técnica o principio.
La técnica del doble conteo [4]
Para contar el número máximo de apretones de mano usaremos doble conteo: contaremos de dos formas el número de parejas (apretón, persona). Para ello designemos con $X$ el número de apretones. Como en cada apretón participan dos personas en la reunión, ese número es $2X$. Pero también, y buscando el máximo, se puede calcular como $5+5\cdot 4=25$ (pues una de las personas saludó a las 5 restantes, y las otras 5 saludaron a 4). De aquí que el número de apretones máximo se deriva de la ecuación $2X=25$. Es decir, hubo a lo más 12 apretones en la reunión.
El algoritmo glotón
Para ver que realmente son posibles 12 apretones usaremos el algoritmo glotón en el grafo asociado (bueno, de hecho no voy a poner las figuras pero el lector podrá imaginarlas).
Para ello, designemos con A a la persona que saludó a todas las otras 5 a las cuales designaremos con B, C, D, E y F. Apartemos A y tratemos de lograr el máximo de saludos entre los restantes.
Como todos los 5 ya saludaron a A, todos ellos tiene 3 saludos disponibles (de acuerdo a la restricción del problema). Elegimos entonces cualquiera de los 5, digamos el B y hagamos que salude a C, D, y E. (llevamos 5+3 apretones).
Hasta aquí, A y B quedan saturados (ya no pueden saludar a nadie), y a C, D y E les quedan dos saludos. Pero a F le quedan 3. Por tanto se elige F como el más prometedor (para maximizar los apretones). Hagamos entonces que F salude a C, D y E (con lo cual llevamos 11 apretones).
Con esto, A, B, y F quedan saturados y a C, D y E les queda un saludo. Elegimos cualquiera de ellos, digamos el D, y hagamos que salude a cualquiera de los dos restantes no saturados, digamos al C (se han logrado los 12 apretones).
Para finalizar notemos que, el algoritmo tiene que parar pues solamente queda el E no saturado y, por tanto, a nadie puede saludar (de acuerdo a la restricción). Los 12 apretones obtenidos con el algoritmo glotón son AB,AC,AD,AE,AF, BC,BD,BE, FC,FD,FE, y DC.
Digresión sobre el algoritmo glotón
En otra ocasión elaboraré sobre el glotón. Pero, por lo pronto, destacaré algunas de sus características clave. En primer lugar están los conceptos utilizados para describirlo. Saturación, candidatos, candidato prometedor. Para más detalles ver el artículo de la wikipedia http://en.wikipedia.org/wiki/Greedy_algorithm [5]. Ver también este problema resuelto con glotón. [6]
El algoritmo glotón es una estrategia general para encontrar un máximo en un espacio de soluciones. Tiene el atractivo de incorporar (y formalizar) una regla de decisión que usamos los humanos:
elegir la opción que parece más prometedora aquí y ahora (sin pensar en el largo plazo).
En el algoritmo, como en nosotros los humanos, esa regla es central y es, a un tiempo, su fortaleza y su debilidad. En el mundo de los humanos esa debilidad es explotada con éxito por los estafadores y los vendedores de sueños.
Comentarios finales
La situación didáctica de Guy Brousseau [1] --vista como método de enseñanza-- ha sido criticada por la dificultad de su aplicación debido a los obstáculos que presenta un aula adolescente. Uno de ellos es que la mayoría de los adolescentes no aceptan la devolución debido a la cultura escolar dominante en la que esperan que el conocimiento les sea enseñado.
El efecto de esa negativa es la simulación (hacen como que están pensando el problema pero...). El otro es que, aun cuando aceptaran la devolución, sus recursos cognitivos (sus competencias matemáticas) son con demasiada frecuencia demasiado escasos --y no les alcanza para llegar a la solución.
Así que para un jurado es muy placentero constatar que dos o tres (o más) competidores llegaron a la solución sin conocer las técnicas --lo cual es la expectativa con frecuencia malograda de Brousseau. En este caso del problema 1 del concurso estatal OMM Tamaulipas 2011, por lo menos 10 competidores le sacaron los 7 puntos al problema (unos con el doble conteo y otros con fuerza bruta y algo parecido al algoritmo glotón).
Y esos casos en que el alumno aceptó la devolución y también resolvió el problema correctamente son los que hacen posible --en una situación de aula-- que el profesor intervenga hacia el final como institucionalizador entusiasta. Un poco como es mi caso en este post.
Los saluda
jmd