Objetivos didácticos
Un lab universitario de Optimización y Matemática discreta sobre un único problema que aparece disfrazado cinco veces: formar parejas entre alumnos que se llevan bien, poner cámaras en las calles de un barrio, elegir un delegado distinto para cada club, repartir documentos entre traductores y asignar alumnos a empresas de prácticas. Los bloques A, B y F se pueden hacer desde Bachillerato.
El hilo es que un emparejamiento máximo se demuestra. Un «es máximo» se certifica con un recubrimiento del mismo tamaño (König), un «no hay perfecto» con un conjunto de Hall, y una asignación óptima con una matriz reducida con ceros independientes. El lab nunca dice «es óptimo» sin enseñar el certificado.
El orden es el de la experiencia, no el del índice de un tema. En la primera sala no aparece ninguna palabra técnica: el alumno forma parejas con la mano y se atasca. «Maximal» y «máximo» solo se nombran cuando ya ha vivido la diferencia con un rotulador que no se puede borrar. En toda sala que calcula un número (ν, τ, el coste óptimo, cuántos intercambios hacen falta), el alumno escribe primero su predicción.
Qué se aprende
- Distinguir un emparejamiento maximal (no admite más aristas) de uno máximo (tiene el mayor número posible), y ver por qué el voraz se queda en el primero.
- Mejorar un emparejamiento invirtiendo un camino aumentante, y reconocer cuándo ya no hay ninguno (teorema de Berge).
- Seguir el algoritmo de caminos aumentantes paso a paso, con su búsqueda en profundidad y sus ramas que fracasan, y el obstáculo de los ciclos impares que resolvió Edmonds.
- Entender el recubrimiento por vértices y la desigualdad ν ≤ τ, y ver que en los grafos bipartitos se da la igualdad (teorema de König).
- Estudiar a la vez un emparejamiento y un recubrimiento con la pareja concordante y su defecto, y bajar el defecto a cero con dos operaciones: cambiar solo M o cambiar solo C.
- Decidir si se puede saturar un lado de un bipartito dando siempre un certificado: el emparejamiento o un conjunto S con |N(S)| < |S| (teorema de Hall), y aplicarlo a tableros regulares y a un truco de cartas.
- Resolver problemas de asignación con costes por el método húngaro, entendiendo por qué restar una constante a una fila o columna no cambia la solución y por qué el número mínimo de líneas es König otra vez.
- Encontrar parejas bloqueantes, seguir el algoritmo de Gale–Shapley ronda a ronda y comprobar que quien propone sale ganando.
Ideas matemáticas clave
- Todo resultado viene con certificado. Emparejamiento y recubrimiento se vigilan mutuamente: cada pareja necesita su propia cámara, así que |M| ≤ |C| siempre, y cuando son iguales ninguno de los dos se puede mejorar.
- Un camino aumentante gana exactamente una arista. Tiene una arista más fuera de M que dentro. Por eso, partiendo de cero, llegar al perfecto en un 7 + 7 cuesta siempre 7 intercambios.
- El defecto cuenta los vértices libres de C. En una pareja concordante, f = |C| − |M| es exactamente el número de vértices del recubrimiento que se han quedado sin pareja. Las dos operaciones lo bajan; en un bipartito siempre se llega a cero, y ahí están los dos certificados a la vez.
- Los ciclos impares son el obstáculo. En el triángulo o en el pentágono ν < τ, y el defecto no baja de 1.
- Hall es necesario y suficiente. Si ningún grupo de clubes tiene menos candidatos que clubes, hay delegados para todos. En un tablero donde cada fila y cada columna tienen r casillas pintadas siempre caben n torres, y en una baraja repartida en 13 montones de 4 siempre se pueden sacar los 13 valores.
- Restar a una línea baja todos los totales lo mismo. El orden de las asignaciones no cambia, y una asignación de ceros en una matriz sin negativos es óptima.
- Quien propone, gana. Las dos versiones de Gale–Shapley dan asignaciones estables, cada una la mejor posible para el lado que propone.
Créditos
Las salas «Parejas concordantes», «Las dos operaciones», «Defecto cero» y «Torres en casillas pintadas» se basan en la hoja Паросочетания и покрытия de Vania Yakovlev (Кроссворд Тьюринга, https://d1-d57.github.io/matchings/), de donde vienen la noción de pareja concordante y la de defecto.
Notas para el aula
- «El rotulador permanente» explica la diferencia entre maximal y máximo en treinta segundos.
- «Las dos operaciones»: la reacción en cadena funciona muy bien proyectada. Conviene preguntar a la clase si la cadena va a cerrar antes de lanzarla.
- «Defecto cero»: el momento en que M y C se certifican mutuamente es la mejor introducción al teorema de König.
- «El truco de las cartas»: barajar tres o cuatro veces delante de la clase y pedir a un voluntario que encuentre la elección.
- Recorrido para Bachillerato: bloques A → B → F. Los bloques C, D y E piden nivel universitario, y el E se apoya en la sala «Defecto cero».
Contenidos por salas
Sala 1 · Parejas para la práctica
Doce amigos que quieren trabajar por parejas; cada línea es una amistad. Sin ninguna palabra técnica, el alumno forma parejas tocando las líneas o a los dos amigos. El grafo (rejilla 3 × 4 con algunas diagonales) tiene una sola forma de emparejar a los doce; eligiendo al azar uno se atasca el 94 % de las veces, y en la mayoría de los atascos deshacer una sola pareja no basta. La sala detecta cada atasco e invita a deshacer; a los dos atascos nombra a quienes se han quedado solos y a los cuatro enseña la solución.
Tareas para el alumno
- Formar seis parejas para que nadie se quede solo.
Sala 2 · El rotulador permanente
Las parejas se forman con rotulador: no se deshacen, y en cada tablero alguien ya ha marcado una deprisa. Cuando no cabe nada más, el alumno responde si, empezando de cero, se podrían formar más parejas. Los tres tableros están elegidos para que la intuición falle: en el primero siempre se puede mejorar, en el segundo quedan dos vértices libres y aun así no cabe ni una pareja más (al quitar el centro quedan tres triángulos), y en el tercero depende de lo que haya marcado. Después, las definiciones de maximal y máximo y dos preguntas sueltas sobre ellas, y el reto final: si el rotulador se atasca con 5 parejas, el máximo tiene como mucho 10.
Tareas para el alumno
- Decidir en tres tableros si se podrían formar más parejas.
- Responder si todo máximo es maximal y si todo maximal es máximo.
- Acotar el máximo a partir de un emparejamiento maximal de 5 aristas.
Sala 3 · ¿Cuántas parejas se forman?
Cuatro grafos en los que «la mitad de los vértices» no es la respuesta o no se ve: un árbol de 9 vértices (ν = 3), dos centros con cuatro triángulos (14 vértices, ν = 6), el tablero 4 × 4 sin dos esquinas opuestas (ν = 6) y el grafo de Petersen (ν = 5). El alumno predice ν viendo el grafo y después tiene que construir a mano un emparejamiento de ese tamaño; la explicación solo aparece si la predicción falla. Cierra con un razonamiento a lo Tutte (20 vértices; quitar uno deja 5 trozos impares: como mucho 8 parejas). El reto del tablero enlaza con los dominós del lab Poliminós.
Tareas para el alumno
- Predecir ν en cuatro grafos y construir un emparejamiento de ese tamaño.
- Acotar ν con el argumento de los trozos impares.
Sala 4 · El intercambio
Empieza con una animación sobre un grafo pequeño: qué es un camino aumentante y qué no lo es (uno que acaba en una arista azul, otro con dos aristas sin usar seguidas), un camino que sí lo es dibujado arista a arista y el intercambio animado, que suma una pareja. Se puede volver a ver desde cada reto. Los vértices no llevan nombre. Retos: una escalera de 8 vértices (2 × 4) con dos parejas ya marcadas que no caben juntas en ningún emparejamiento perfecto: con aristas sueltas siempre se acaba atascado en 3, y llegar a 4 exige un camino de al menos 3 aristas (se termina pulsando «Ya es máximo», que se comprueba); un camino aumentante único de 5 aristas con ramas sin salida; un grafo de 12 vértices donde hacen falta dos intercambios sin que se avise; un bipartito 6 + 6 con un único camino de 7 aristas; y la pregunta numérica sobre M △ M′ (|M| = 5, |M′| = 8: al menos 3 caminos aumentantes).
Tareas para el alumno
- Ver la animación del camino aumentante y del intercambio.
- Hacer crecer un emparejamiento vacío hasta el máximo.
- Encontrar e intercambiar caminos aumentantes de 5 y 7 aristas, y llegar al máximo con dos intercambios.
- Acotar cuántos caminos aumentantes hay en M △ M′.
Sala 5 · Encuentra el camino
Tres grafos con un emparejamiento maximal que no es máximo; en cada uno el alumno tiene que encontrar un camino aumentante (vale cualquiera) y aplicarlo. En el primero, un bipartito 6 + 6 con cuatro vértices libres, solo hay dos caminos, de 5 aristas, y los dos salen del vértice libre b3: b2 no es extremo de ninguno, así que empezar por él es perder el tiempo. El segundo (12 vértices, no bipartito, con triángulos) tiene dos libres y un único camino de 7 aristas; las bifurcaciones son reales y la arista de 8 hacia 9 lleva a un callejón sin salida. El tercero es una flor: el camino recorre por el lado largo un ciclo de 5 vértices, y el atajo corto entre los dos libres no alterna. Al resolverlo aparece Edmonds (1965) y el problema de los ciclos impares. Tras tres fallos seguidos se muestra el camino.
Tareas para el alumno
- Encontrar un camino aumentante en el bipartito, eligiendo bien el vértice libre de salida.
- Encontrar el único camino en un grafo con triángulos y callejones sin salida.
- Resolver la flor y ver por qué el atajo no sirve.
Sala 6 · Los proyectos de fin de grado
El algoritmo de caminos aumentantes ejecutado a mano. Seis alumnos (a1…a6) piden proyecto entre seis (b1…b6), cada uno solo entre los que le interesan, y se procesan por turnos: en cada turno hay que marcar un camino aumentante que empiece justo en quien toca (otro punto de partida se rechaza). Si cada alumno se quedara con el primer proyecto libre de su lista, los turnos de a5 y a6 solo podrían resolverse moviendo a otros: cadenas de 3 y de 5 aristas. Al intercambiar se pasa solo al turno siguiente, en el mismo tablero. Después, en un bipartito aleatorio 7 + 7 sin asignación perfecta (ν vale 5 o 6), se predice a cuántos alumnos, como mucho, se puede dar proyecto; si falla, se enseña el grupo de alumnos con menos proyectos que ellos y, si el alumno se quedó corto, una asignación. El reto final usa otro grafo 7 + 7, de un grupo de grafos difíciles (ν = 6, 18-20 aristas y solo 4 emparejamientos máximos): hay que construir un máximo desde cero y decidir uno mismo cuándo pulsar «Ya es máximo», que solo vale si lo es.
Tareas para el alumno
- Marcar el camino aumentante de cada alumno, de a1 a a6.
- Predecir a cuántos alumnos se puede dar proyecto en un 7 + 7 aleatorio.
- Construir un emparejamiento máximo desde cero y reconocer cuándo no se puede aumentar más.
Sala 7 · ¿Ya es máximo?
El teorema de Berge como decisión: cuatro tableros con un emparejamiento marcado y la pregunta «¿es máximo o se puede aumentar?». Los dos primeros son bipartitos 6 + 6: en el primero quedan cuatro vértices libres y hay dos caminos de 5 aristas; en el segundo quedan solo dos libres y no hay ninguno (a3, a4, a5 y a6 solo tienen aristas hacia b4, b5 y b6). Los otros dos no son bipartitos, con 12 vértices: en el tercero hay cadenas alternantes de hasta 10 aristas que acaban en un vértice ocupado y aun así es máximo; en el cuarto hay un único camino de 7 aristas. Quien dice «se puede aumentar» tiene que marcar el camino; quien dice «es máximo» y se equivoca pasa a buscarlo. Equivocarse de rama cuenta como fallo, y tras tres fallos se muestra el camino o, en los máximos, la cadena más larga que se queda sin salida y la razón de la cota. Acertar «es máximo» no exige demostrarlo: por ahora se le cree. Cierra con el enunciado de Berge.
Tareas para el alumno
- Decidir en cuatro tableros si el emparejamiento es máximo o se puede aumentar.
- Marcar el camino aumentante cuando existe, también en grafos no bipartitos.
- Distinguir una cadena alternante larga que no llega a ningún libre de un verdadero camino aumentante.
Sala 8 · Parejas contra cámaras
Cámaras en los cruces de un barrio de 14 cruces y 17 calles (una cuadrícula 3 × 6 con huecos): cada calle vigilada se ilumina. Tres retos. Primero se predice el mínimo de cámaras y luego se colocan: coloreado como un ajedrez, los 7 cruces de un color ya vigilan todo, pero el mínimo es 6, único, y mezcla los dos colores. Segundo, en el mismo barrio, construir a la vez un emparejamiento M y un recubrimiento C con |M| = |C| = 6. Tercero, el grafo de Petersen (3-regular, 15 calles): ¿cuánto vale τ? La primera pista recuerda que cada cámara vigila 3 de las 15 calles; la segunda, que 5 cámaras vigilarían 5 · 3 = 15 calles, justo todas, sin que ninguna calle tenga cámara en sus dos extremos, y pide mirar el pentágono exterior. Al terminar el reto (se acierte o se falle tras tres intentos) se enseña siempre, en el tablero, un recubrimiento de 6 cámaras y la demostración de que 5 no bastan: con 5 cámaras cada calle tendría exactamente un extremo con cámara, así que a lo largo de cualquier ciclo los cruces alternarían «con cámara» y «sin cámara», y eso es imposible en el pentágono exterior (5 vértices, número impar); por tanto τ ≥ 6, y el tablero muestra que 6 bastan. Cada calle sin vigilar y cada cámara de más se señalan al comprobar.
Tareas para el alumno
- Predecir y colocar el mínimo de cámaras (6) que vigila todas las calles.
- Construir a la vez un emparejamiento y un recubrimiento del mismo tamaño.
- Hallar τ en el grafo de Petersen y seguir la demostración de que 5 cámaras no bastan.
Sala 9 · ¿Cuánto puede valer ν?
Dado τ, ¿qué valores puede tomar ν? Primero se explora sin puntuar: dos deslizadores (τ de 3 a 7 y número de triángulos t) dibujan t triángulos disjuntos más τ − 2t aristas sueltas y escriben debajo τ y ν = τ − t, sin explicar nada todavía. Después se construye con una paleta de piezas que se añaden como componentes disjuntas y se pueden quitar (arista, camino de 3, triángulo, ciclo de 4, ciclo de 5 y K₄); τ y ν del total no se ven en vivo, solo al pulsar Comprobar. Retos: τ = 6 con ν lo más pequeño posible (3, tres triángulos), τ = 6 con ν lo más grande posible (6, piezas con τ = ν como las aristas) y τ = 7 con ν = 4 usando como máximo 3 piezas, lo que obliga a dos triángulos y un ciclo de 5 o un K₄. Si el grafo tiene τ = 6 pero un ν que no es el extremo, se avisa de que se puede conseguir menor o mayor. Después, con τ = 9, ¿qué valores puede tomar ν? Cualquiera entre 5 y 9; cada opción errónea se refuta con su contraejemplo. Al final queda en pantalla el teorema ν ≤ τ ≤ 2ν con la demostración de las dos desigualdades.
Tareas para el alumno
- Explorar con dos deslizadores cómo cambian τ y ν.
- Construir con piezas un grafo con τ = 6 y ν mínimo, otro con ν máximo y otro con τ = 7 y ν = 4 con solo 3 piezas.
- Decidir qué valores puede tomar ν cuando τ = 9.
Sala 10 · Parejas concordantes
Emparejamiento y recubrimiento estudiados a la vez. Tras las dos definiciones (una pareja (M, C) es concordante si C recubre y cada arista de M tiene exactamente un extremo en C; el defecto es f = |C| − |M|), el alumno decide en dos bipartitos 6 + 6 si la pareja mostrada es concordante, con cuatro opciones cuyo error se explica una a una. En el primero la arista a3–b3 de M tiene sus dos extremos en C; en el segundo sí es concordante (f = 2), aunque varias aristas fuera de M tienen los dos extremos en C: esa es la tentación. Después se pregunta qué garantiza f = 0: que M es máximo y C mínimo, porque |M| ≤ ν ≤ τ ≤ |C|. El reto final es construir una pareja concordante con f = 0 en un bipartito 7 + 7 de 19 aristas con ν = τ = 6 y un único recubrimiento mínimo, que mezcla los dos lados; el lab dice qué falla: C no recubre, una arista de M toca C dos veces o el defecto no es cero.
Tareas para el alumno
- Decidir si una pareja (M, C) es concordante y entender por qué fallan las otras opciones.
- Deducir qué garantiza un defecto cero.
- Construir una pareja concordante con f = 0.
Sala 11 · La operación 1
Definición corta de la operación 1 (un camino aumentante cuyos vértices alternan dentro de C, fuera de C, …: M crece en una arista, C no cambia y f baja en 1) y una animación lenta sobre un ejemplo de 3 + 3 vértices: se busca el vértice de C sin pareja, se recorre el camino con un pasillo verde detrás de las aristas, se intercambia por etapas y f baja de 1 a 0. Después, tres retos sencillos, cada uno con «Ver la explicación» y, al acertar, la operación animada por etapas con «Ver otra vez»: un 3 + 4 con f = 1 y un único camino válido de 3 aristas; un 4 + 4 con f = 2 en el que los dos vértices de C sin pareja están unidos por una arista (el camino tentador a4–b2 aumenta M pero no alterna con C y se rechaza) y el válido tiene 3 aristas; y un 4 + 5 con f = 2 y un camino válido de 5 aristas, con un camino tentador más corto que acaba dentro de C. Cada error se explica y cada reto tiene sus dos pistas.
Tareas para el alumno
- Marcar el camino de la operación 1 en un grafo de 7 vértices.
- Distinguir un camino aumentante cualquiera del que vale para la operación 1.
- Encontrar un camino de 5 aristas que alterna con C.
Sala 12 · La operación 2
Empieza por el caso más sencillo, apagar una cámara que sobra (S de un solo vértice), con su propia animación y su reto, antes del caso general. Definición de la operación 2 como algoritmo (empezar en un vértice de C sin pareja, seguir sus aristas hacia fuera de C, meter en S las parejas de los vértices a los que se llega, repetir; después S sale de C y entran sus parejas) y animación lenta sobre un ejemplo pequeño. Tres retos de tamaño creciente, cada uno con «Ver la explicación» y, al acertar, la operación animada por etapas: un 4 + 4 con un S de 2 vértices, un 5 + 4 con un S de 3 vértices en cadena y un 7 + 6 con un S de 4 vértices que se propaga en dos niveles; en los tres M es máximo (no hay camino aumentante), f = 1 y solo hay un S válido. Los errores se explican (S no independiente, una arista quedaría sin cubrir, no baja el defecto). Al final, un resumen de las dos operaciones sobre una misma pareja (4 + 5, f = 2): la operación 1 con un camino de 3 aristas (f baja a 1) y la operación 2 con un S de 2 vértices (f baja a 0), en una animación por etapas, y un texto: la operación 1 cambia solo M (crece en una arista), la operación 2 cambia solo C (pierde tantos vértices como vértices sin pareja había en S) y las dos conservan la pareja concordante y bajan f.
Tareas para el alumno
- Construir S siguiendo aristas hacia fuera de C y luego las parejas, en tres tableros cada vez mayores.
- Ver qué cambia con cada operación (M o C) sobre una misma pareja.
Sala 13 · Defecto cero
El teorema de König vivido antes de enunciado, y la única sala donde se combinan las dos operaciones. Dos botones grandes eligen la operación («Haré la operación 1 (marcar un camino)» o «Haré la operación 2 (marcar S)»), el activo se ve resaltado, una línea dice qué marcar y un único botón aplica la operación elegida; los mensajes de error de una operación no mencionan la otra. Primer reto: un bipartito aleatorio 5 + 5, con M vacío y C igual a un lado, y con ν = 4 < 5, de modo que para llegar a f = 0 no basta con ampliar M: hay que reducir C con la operación 2. Segundo: un 7 + 7 de 17 aristas, a medias (|M| = 5, |C| = 8, f = 3), que se resuelve siempre con exactamente dos operaciones 1 y una operación 2, y con al menos un camino de 5 aristas. Al llegar a f = 0, M y C parpadean a la vez (se puede repetir). Tercero: un grafo no bipartito de 11 vértices (un pentágono con dos ramas) en el que al empezar solo hay operaciones 2; se baja hasta f = 1 y ya no hay ninguna operación aplicable, y el alumno tiene que declararlo («No se puede bajar más»): hacerlo antes de tiempo cuenta como fallo. Una pregunta final: ¿qué lo impide? Un ciclo impar (aquí ν = 5 y τ = 6); el lab refuta con el propio grafo las opciones del ciclo par, el vértice de grado 1 y el vértice con tres vecinos. Cierra con König: en bipartitos, ν = τ. La pista (sin coste, a los dos fallos o a los 60 s sin avanzar) enseña primero el vértice de partida y, al pulsarla otra vez, dibuja la operación que sirve y activa su botón; al quinto fallo la aplica el lab.
Tareas para el alumno
- Llevar a defecto cero un bipartito aleatorio 5 + 5 en el que hace falta la operación 2.
- Hacerlo en un 7 + 7 que exige dos caminos aumentantes y un cambio de C.
- Reconocer cuándo no se puede bajar más en un grafo con un ciclo impar y explicar por qué.
Sala 14 · Delegados de los clubes
Un delegado distinto por club: 7 clubes y 8 personas, y el alumno toca la línea que une un club con uno de sus miembros. El primer reto tiene solución (17 aristas, 4 asignaciones), pero ir club a club con «el primer miembro libre» se atasca en el séptimo y, al azar, solo sale bien en torno al 18 % de las veces; la pista recuerda que Cris y Eva solo están en Teatro. El segundo reto tiene el mismo enunciado y los mismos dos botones, pero no tiene solución (ν = 6): aquí «No se puede» es la respuesta correcta, y después hay que demostrarlo señalando el único grupo de clubes que lo impide, cinco clubes (Coro, Danza, Judo, Pintura y Escalada) con solo cuatro personas entre todos. En el primero, pulsar «No se puede» cuenta como fallo; si el grupo señalado no vale, el lab dice cuántas personas suma. Cierra con la condición de Hall como condición necesaria.
Tareas para el alumno
- Asignar un delegado distinto a cada uno de los siete clubes.
- Decidir que en la segunda versión no se puede.
- Señalar el grupo de cinco clubes que cuenta con solo cuatro personas.
Sala 15 · Detective de Hall
Cuatro bipartitos 7 + 7 de 20 aristas y sin vértices de grado 1, con la pregunta ¿hay un emparejamiento que sature A? Las respuestas, por orden, son sí, no, no, sí. El alumno elige la rama y la demuestra: con el emparejamiento (en los dos «sí» hay 4 emparejamientos perfectos y el voraz se atasca) o con un grupo S de A con |N(S)| < |S|. En los dos «no» el grupo violador es único y no se ve mirando los grados: en el segundo son 4 vértices con solo 3 vecinos, y a7, que tiene grado 2, no está en S; en el tercero, 5 vértices con 4 vecinos. Elegir mal la rama cuenta como fallo y se explica, y cada grafo tiene su propia segunda pista. Cierra con el teorema de Hall: la condición no solo es necesaria, también es suficiente.
Tareas para el alumno
- Decidir en cada uno de los cuatro grafos si hay un emparejamiento que sature A.
- Dar el certificado: el emparejamiento o el grupo S que lo impide.
Sala 16 · Torres en casillas pintadas
En el reto del 8 × 8 se pueden probar torres antes de contestar y ver el tablero como grafo filas–columnas, sincronizado con las torres. Si cada fila y cada columna tienen r casillas pintadas, siempre caben n torres que no se atacan. Tres retos. Primero, un tablero de 7 × 7 con 20 casillas pintadas, que no es regular y tiene 4 colocaciones completas: ir fila a fila a la columna libre más a la izquierda se atasca en la fila 7. Segundo, un 8 × 8 con 24 casillas pintadas en el que no caben 8 torres: con el tablero bloqueado se predice cuántas caben, 6, y después se colocan; las filas 1, 2, 4, 5, 7 y 8 solo tienen casillas en las columnas b, c, g y h (seis filas para cuatro columnas), y el lab las marca tras tres fallos. Tercero, una pregunta de elección sobre por qué siempre caben n torres cuando hay r por fila y por columna: k filas suman rk casillas, que tocan al menos k columnas (Hall). Entre las respuestas erróneas, que el total sea múltiplo de n (el 8 × 8 anterior lo refuta) y la regla de la primera columna libre (que falla en un 4 × 4 con 2 casillas por fila).
Tareas para el alumno
- Colocar 7 torres en un tablero donde el voraz se atasca.
- Predecir y colocar el máximo de torres (6) en un 8 × 8 donde no caben todas.
- Explicar con la condición de Hall por qué siempre caben cuando cada fila y cada columna tienen r casillas.
Sala 17 · El truco de las cartas
Una baraja de 52 cartas repartida al azar en 13 montones de 4: hay que elegir una carta de cada montón para que salgan los 13 valores. Mientras se elige, el lab solo cuenta cuántos montones llevas; los valores que salen y los que se repiten aparecen marcados al pulsar Comprobar. Se puede barajar de nuevo tantas veces como se quiera y siempre hay solución. Tras dos intentos fallidos aparece un botón de pista que fija una carta, y tras tres el lab muestra una solución (sin contarla como acierto). Cierra con una pregunta de elección sobre por qué siempre se puede: k montones tienen 4k cartas y, como hay 4 de cada valor, entre ellas hay al menos k valores distintos; es Hall con montones y valores, porque el multigrafo montones–valores es 4-regular. Cada respuesta errónea se refuta (contar cartas no basta, los palos no importan, un montón puede repetir valor).
Tareas para el alumno
- Elegir una carta de cada montón para que salgan los 13 valores.
- Explicar con la condición de Hall por qué siempre se puede, se baraje como se baraje.
Sala 18 · El problema de asignación, a ojo
Cuatro traductores y cuatro documentos, con una tabla 4 × 4 de las horas que tarda cada uno en cada documento. Primero hay que calcular cuánto suma la estrategia voraz, en la que cada traductor, en orden, se queda su documento libre más rápido: 17 h. Después el alumno elige a mano una casilla por fila y por columna con el menor total posible. Hay 24 asignaciones y el óptimo es único, 12 h (T1–D4, T2–D3, T3–D2, T4–D1), a solo 2 h de la segunda mejor; no usa el mínimo de la fila de T1 ni el de la de T4, así que decidir fila a fila no basta. Al fallar, el lab solo dice el total conseguido (y avisa de que se está cerca si es a 2 h o menos del óptimo); al acertar, muestra que es la única de 12 h entre las 24.
Tareas para el alumno
- Calcular el total que da la estrategia voraz (17 h).
- Encontrar la asignación de menor total, 12 h, entre las 24 posibles.
Sala 19 · Restar no cambia nada
Se trabaja con la misma tabla 4 × 4. Primero hay que calcular cuánto cambia el total de una asignación concreta si se resta 2 a la fila T2 y se suma 5 a la columna D4 (+3, con signo). Después se pregunta si ese cambio altera cuál es la asignación óptima; entre las cuatro opciones, cada error se refuta: toda asignación usa exactamente una casilla de cada fila y de cada columna, y por eso todas cambian lo mismo. El reto final son seis deslizadores (de 0 a 9) sobre una tabla 3 × 3: hay que restar a cada fila y a cada columna un entero hasta que no queden negativos y haya tres ceros independientes. La tabla marca los ceros y los negativos, y se comprueba al soltar el deslizador. Solo hay una solución (filas 3, 0, 4 y columnas 0, 3, 1), y la sutileza es que restar a cada línea su mínimo no basta: deja como mucho 2 ceros independientes. Aparece una pista a los 12 movimientos y la solución a los 30.
Tareas para el alumno
- Calcular cuánto cambia el total de una asignación al restar a una fila y sumar a una columna.
- Explicar por qué la asignación óptima no cambia.
- Conseguir con los deslizadores tres ceros independientes sin negativos.
Sala 20 · El método húngaro, paso a paso
Reduce la matriz paso a paso: el alumno escribe el mínimo de cada fila y la matriz se transforma a la vista; luego el de cada columna; después cuenta ceros, los cubre con el mínimo de líneas, ajusta y forma la asignación, siempre con la matriz actual delante. La matriz 4 × 4 de horas, transformada paso a paso con el método húngaro y con dos ajustes; el óptimo, único, es 20 h. Primero se restan los mínimos de fila (5, 2, 2, 3) y de columna (0, 0, 2, 0) y se cuentan los ceros que quedan: 6. Después el alumno halla el máximo de ceros independientes (2) y tapa todos los ceros con el menor número de líneas pulsando las cabeceras (2: la fila T3 y la columna D4; aquí aparece König aplicado a la matriz de ceros). Luego calcula el valor de una casilla tras el primer ajuste (la de T3 y D4, en el cruce de las dos líneas, con mínimo no tapado 1), cuántas líneas hacen falta ahora (3) y el valor de otra casilla tras el segundo ajuste (mínimo no tapado 4). Por último marca cuatro ceros que forman una asignación completa y calcula su coste en la matriz original: 20 h, con T1–D2, T2–D4, T3–D1 y T4–D3. Cada pregunta tiene dos pistas y una solución.
Tareas para el alumno
- Reducir filas y columnas y contar los ceros que quedan.
- Hallar los ceros independientes y taparlos con el mínimo de líneas.
- Aplicar dos ajustes y calcular el valor de una casilla tras cada uno.
- Marcar la asignación de ceros y calcular su coste en la matriz original.
Sala 21 · Los técnicos
Con la tabla reducida a la vista y la suma de las casillas marcadas en vivo. Cinco técnicos y cinco averías, con una tabla 5 × 5 y sin guía: hay que elegir la asignación de menor total, 22 h (óptima y única; la voraz por filas da 33 h). Las dos reducciones por sí solas no bastan, porque aún hacen falta 4 líneas para tapar los ceros, así que hay que ajustar; el aviso de que se está cerca solo salta a 1 h del óptimo. Después, un problema de maximizar beneficios, con cuatro comerciales y cuatro zonas: primero se elige cómo convertirlo en uno de minimizar (restar cada beneficio del mayor de la tabla, 19; tomar el inverso 1/b o sustituir por puestos da una asignación de solo 52 mil € frente a los 54, y dividir solo cambia la escala) y luego se elige la asignación de mayor beneficio, 54 mil € con C1–Z3, C2–Z4, C3–Z1 y C4–Z2. Elegir el máximo de cada fila no sirve: C2 y C3 quieren Z4, y C1 y C4 quieren Z3.
Tareas para el alumno
- Encontrar la asignación de menor total en una tabla 5 × 5 sin guía.
- Elegir cómo convertir un problema de maximizar en uno de minimizar.
- Encontrar la asignación de mayor beneficio.
Sala 22 · Parejas bloqueantes
Cinco alumnos y cinco empresas de prácticas con sus listas de preferencias completas, y las definiciones de asignación, pareja bloqueante y asignación estable. Empieza con una animación paso a paso (con personas y con grafo) en un ejemplo de 3 × 3: qué es y qué no es una pareja bloqueante. Después, cuatro retos graduados (3 × 3, 4 × 4 y dos de 5 × 5): el alumno señala una pareja bloqueante (eligiendo un alumno y una empresa) o pulsa «Es estable»; tocando un alumno se le marcan las empresas que prefiere a la suya, y cada intento fallido dice quién prefiere qué. La animación se puede volver a ver en cada reto.
Tareas para el alumno
- Decidir si cada asignación es estable y, si no lo es, señalar una pareja bloqueante.
- Distinguir una pareja bloqueante de una en la que solo uno de los dos prefiere.
Sala 23 · Gale y Shapley
El algoritmo de aceptación diferida, ejecutado por el alumno en una tabla de rondas (una fila por ronda, una columna por receptor), con las mismas preferencias de la sala anterior y las listas coloreadas como en la animación (ámbar: solicitud, verde: se queda, rojo: rechazado y tachado). Primero solicitan plaza los alumnos (4 rondas, 11 solicitudes, con dos cadenas de rechazos: Ana desplaza a Carla en S y Elena a David en P): en cada ronda el alumno toca, en la lista de cada alumno libre, la primera empresa sin tachar y, al marcar la última, decide en cada columna con quién se queda cada empresa que tiene candidatos (los nuevos y el que ya tenía); el lab no calcula nada por él. Se equivoca si solicita con alguien que ya tiene pareja, se salta una opción sin tachar o elige un candidato peor, si pasa de ronda con nadie libre o si pulsa «Terminado» con alguien libre: cada error cuenta como fallo y se explica, y tres seguidos activan la pista completa (pista de tres niveles en cada paso). Después ofrecen el puesto las empresas (otras 4 rondas, 9 ofertas, con 4 decisiones entre dos candidatos). El resultado no depende del orden en que se atienda a los libres. Salen dos de las tres asignaciones estables, que difieren en 4 de las 5 empresas. Después, un reto de exploración: partiendo de esas dos, el alumno busca la que falta emparejando en el grafo (tocando una persona y una empresa) y comprobando con «¿Es estable?», que marca en rojo las parejas bloqueantes. Las pistas enseñan que cada alumno queda entre sus dos empresas de Gale–Shapley y cómo se pasa de una estable a otra con una cadena de bajadas (una rotación); al terminar se explica que así se obtienen todas (Irving y Leather, 1986). Una pregunta final: cuando proponen los alumnos, ¿qué consigue cada empresa? Su peor pareja estable; quien propone, gana. Al encontrar la tercera estable se explica por qué existe: para algunos alumnos hay un hueco entre sus dos empresas de Gale–Shapley, y la tercera cae en él. Cierra con el Nobel de 2012 y la asignación de médicos residentes.
Tareas para el alumno
- Ejecutar el algoritmo cuando solicitan los alumnos, escribiendo cada ronda en la tabla: solicitudes y decisión de cada empresa.
- Repetirlo cuando proponen las empresas y comparar los resultados.
- Reconocer qué lado sale ganando.
- Encontrar la tercera asignación estable con una rotación.
Sala 24 · El círculo ártico
Dominós y rombos elegidos al azar. Parte A: el diamante azteca AD(n) (filas de 2, 4, …, 2n, 2n, …, 4, 2 cuadrados) y sus recubrimientos por dominós, que son emparejamientos perfectos. El alumno construye a mano los 8 recubrimientos de AD(2) (con pista y botón «No encuentro más»), calcula cuántos tiene AD(4) a partir de 2, 8 y 64 (2^(n(n+1)/2), Elkies–Kuperberg–Larsen–Propp, 1992) y predice qué se verá al elegir uno al azar de un diamante grande. Después ve el sorteo exacto con el algoritmo de domino shuffling (destruir, deslizar, crear), con reproducción, pausa, velocidad, paso a paso y tamaño hasta n = 150: aparecen cuatro zonas de un solo color y, entre ellas, el círculo inscrito (teorema del círculo ártico, Jockusch–Propp–Shor, 1995). Parte B: el hexágono de lados a, b, c sobre la red triangular y sus recubrimientos por rombos (emparejamientos perfectos del panal), que con tres tonos parecen pilas de cubos en una caja a×b×c. El alumno gira vértices (añadir o quitar un cubo), averigua que de la caja vacía a la llena hacen falta abc giros (8 en 2×2×2), que los rombos de cada tono son siempre a·b, b·c y a·c (15 oscuros en 3×4×5) y predice la forma de la zona desordenada de un hexágono grande. Un último tablero deja derretirse la caja llena con giros aleatorios (dinámica de Glauber) hasta que aparece el círculo (la elipse inscrita si a, b, c son distintos; Cohn–Larsen–Propp, 1998). Cierra con la idea común: todo son emparejamientos perfectos elegidos al azar.
Tareas para el alumno
- Construir los 8 recubrimientos de AD(2).
- Deducir que AD(4) tiene 1024 recubrimientos.
- Predecir la forma de la zona desordenada de un recubrimiento aleatorio del diamante.
- Ver crecer el diamante con domino shuffling hasta el círculo ártico.
- Girar el hexágono de rombos y calcular el mínimo de giros de la caja vacía a la llena (8).
- Contar los rombos de un tono en el hexágono 3, 4, 5 (15 oscuros).
- Ver derretirse la caja hasta la elipse inscrita.
Salas para proyectar
Las más vistosas para mostrar y discutir en clase.