Por qué 61 nunca alcanza

Imagina a 16 amigos en una fiesta. Quieren tomarse fotos en grupo. En cada foto salen exactamente 5 amigos, y un amigo puede salir en todas las fotos que quiera.

Hay una sola regla. Escoge a 3 de los amigos, los que sean. Esos 3 tienen que salir juntos en al menos una foto. Y eso se tiene que cumplir con cualquier grupo de 3 que escojas.

Entonces, la pregunta es esta: ¿cuál es el menor número de fotos que cumple la regla?

Parece un juego de fiesta, pero es un problema de matemáticas de verdad, y es difícil. En 1997, un investigador llamado Rade Belić encontró un plan que usa 65 fotos. Mucho antes, en 1964, un matemático llamado Schönheim encontró un truco para contar. Ese truco muestra que siempre se necesitan al menos 61. Desde 1997, la mejor respuesta conocida era "entre 61 y 65".

Esta prueba nueva muestra que con 61 fotos nunca se puede. Eso sube la respuesta: ahora es 62, 63, 64 o 65. Nadie sabe todavía cuál de esos números es.

¿Por qué es difícil?

Contemos. Con 16 amigos se pueden formar 560 grupos distintos de 3. Una foto de 5 amigos contiene 10 de esos grupos. Así que se necesitan al menos 560 ÷ 10 = 56 fotos.

Pero 56 no alcanza, porque las fotos se enciman. Cuando dos fotos comparten amigos, algunos grupos de 3 quedan en las dos. Eso es espacio desperdiciado. Lo difícil es saber cuánto espacio se tiene que desperdiciar.

¿Y si una computadora probara todos los planes? Hay 4,368 fotos distintas que se podrían tomar. El número de formas de escoger 61 de ellas tiene 139 cifras. Una computadora que revisara mil millones de planes cada segundo desde el inicio del universo ni siquiera se acercaría.

Cómo funciona la prueba

La prueba usa dos tipos de razonamiento.

Primero, contar con cuidado. Si 61 fotos alcanzaran, casi no habría espacio desperdiciado. Al contar se ve que un amigo saldría en exactamente 20 fotos y todos los demás en exactamente 19. Las fotos tendrían que seguir un patrón muy estricto, casi sin margen para cambiar nada.

Segundo, una búsqueda por computadora. Ese patrón estricto reduce todo el problema a solo 4 casos. En cada caso, un programa intentó completar el plan de fotos. Las 4 veces demostró que el plan no se podía completar. Así que no existe ningún plan con 61 fotos.

¿Podemos confiar en la computadora?

Los programas de computadora pueden tener errores, así que esta prueba no te pide confiar en uno. El programa que buscó no solo respondió que no. Anotó cada paso de su razonamiento, como cuando muestras tu procedimiento en la clase de matemáticas. Cada una de esas anotaciones tiene más de 13 millones de líneas.

Después, otro programa revisó los pasos. Es un verificador que otros investigadores usan justo para este trabajo, y estuvo de acuerdo con cada paso que necesitaba. Otros dos programas que funcionan de otra manera tampoco encontraron ningún plan.

¿Quién hizo el trabajo?

Christopher Celaya, quien dirige el laboratorio, encabezó el proyecto y revisó las matemáticas. Los programas los escribieron asistentes de programación. Un asistente de programación es un programa de computadora que escribe código cuando una persona le dice qué construir. Después, el verificador confirmó cada una de las cuatro respuestas de la búsqueda.

Inténtalo tú

Aquí hay una versión más pequeña del mismo acertijo. Hay 7 amigos. En cada foto salen 3 de ellos. Cada par de amigos tiene que salir junto en al menos una foto. ¿Cuál es el menor número de fotos que necesitas?

Pista: con 7 amigos hay 21 pares. Una foto de 3 amigos contiene 3 pares. Así que necesitas al menos 21 ÷ 3 = 7 fotos. ¿Puedes lograrlo con exactamente 7?

El acertijo grande funciona igual, solo que es más grande: 16 amigos, fotos de 5, y cada grupo de 3 tiene que compartir una foto. Con 7 amigos puedes revisar tu plan a mano. Con 16 nadie puede, así que la prueba necesitó tanto contar con cuidado como una computadora.

Este resultado se explica en cuatro niveles. El primero está aquí en español. Los otros tres, para preparatoria, para universidad e ingeniería, y para investigación, están en inglés, igual que el artículo completo, el código y las pruebas.