La tarea de hace 165 años persigue a los matemáticos

En 1850, el reverendo Thomas Kirkman, un matemático británico y rector de la parroquia en Lancashire, formuló un rompecabezas de aspecto inocente en una revista de entretenimiento para amantes de las matemáticas "Cuaderno para damas y caballeros":

"Quince jóvenes colegialas salen a caminar durante siete días en tres filas: necesita organizar todos los días "para que el mismo par de colegialas nunca se reúnan dos veces seguidas".

La tarea parece simple, pero si intentas resolverla, inmediatamente te das cuenta de que no es así. Puedes intentar resolverlo con lápiz y papel o jugar en la versión HTML .

Debido a su falsa simplicidad, la tarea rápidamente se hizo famosa. Los amantes de las matemáticas enviaron sus decisiones, y los científicos publicaron artículos científicos con el intento de formular una solución general al problema.

Como resultado, este rompecabezas ayudó a dar forma a una nueva área de las matemáticas: esquemas combinatorios , a los que ahora se dedican libros de texto gruesos .. Lo que comenzó como una simple tarea de distribuir a las personas en grupos (o esquemas, como finalmente se les llamó) ahora se ha convertido en un método que se utiliza en el diseño experimental, los códigos de corrección de errores en informática, criptografía, agricultura, deportes e incluso en fraudes de juegos de azar. (Hubo una historia cuando un cartel criminal ganó millones de dólares en siete años comprando boletos con todas las combinaciones posibles de 5 de 46 en una lotería de 6 de 46 si el costo de los boletos era menor que las bonificaciones adicionales por ganar 5 de 46 más la probabilidad de ganar el premio mayor).

Por ejemplo, el código clásico de Hamming para resolver errores utiliza la solución del problema sobre las colegialas (creando grupos de tres colegialas, donde no se repite ningún par), pero solo para el esquema de siete niñas (bit).


Avión Fano para (7, 3, 2)

Lo más sorprendente es que, durante 165 años, los matemáticos no han podido resolver el problema de manera general. Todavía no pueden dar una respuesta, cuál es la solución al rompecabezas en las condiciones iniciales: hay n colegialas, debes crear grupos de tamaño k , de modo que grupos de t niñas nunca se hayan reunido dos veces en el mismo grupo. Tal formulación se llama esquema (n, k, t) .

Por ejemplo, para un grupo de 19 niñas, hay más de 11 mil millones de trillizos posibles en los que cada pareja se reúne solo una vez. Este número es la respuesta. Pero el número de opciones está creciendo exponencialmente con un aumento en el número de colegialas.

Está claro que el problema se resuelve bajo ciertas condiciones y no se resuelve bajo otras. Por ejemplo, si los trillizos de todos los pares posibles están compuestos por seis colegialas, el problema obviamente no se resuelve (hay cinco pares posibles con la colegiala Anya, al mismo tiempo, cada triplete tiene dos pares con Anya, y cinco no se dividen en dos). Es decir, según el principio de divisibilidad, muchas opciones (n, k, t) se eliminan de inmediato .

Al mismo tiempo, hay (n, k, t) que cumplen totalmente con el principio de divisibilidad, pero aún no tienen solución: por ejemplo, (47, 3, 2) .

En los últimos años, la solución se ha dado a conocer para muchas combinaciones (n, k, t)que fueron verificadas algebraicamente o por fuerza bruta en las computadoras. Pero, ¿cómo resolver esto de manera general, qué hacer con excepciones como (47, 3, 2) ? ¿Cómo entender si un problema tiene solución o no?

Esta tarea ha sido considerada uno de los problemas más famosos en combinatoria, dice el matemático Gil Kalai de la Universidad Hebrea de Jerusalén en una entrevista con Wired. Él recuerda cómo discutió con sus colegas sobre esto hace un año y medio, y llegaron a la conclusión de que "nunca sabremos la respuesta, porque la tarea es claramente demasiado complicada".

Sin embargo, solo dos semanas después, el joven profesor de matemáticas Peter Keevash de Oxford demostró que Kalai estaba equivocado. En un articulo cientificodesde enero de 2014, argumenta que casi siempre existe una solución a un problema si se cumple la condición de divisibilidad. En un nuevo documento con fecha de abril de 2015, mostró cómo calcular el número aproximado de soluciones para parámetros dados.

Nadie esperaba que la teoría de la probabilidad se aplicara a la solución del problema, pero el método funcionó perfectamente.

Volviendo a las loterías, los estafadores se dieron cuenta de que es posible reducir la cantidad de boletos comprados comprando todas las combinaciones de 5 de 46 (al especificar 6 de 46 números), luego recibirán absolutamente todos los premios adicionales, y también pueden recibir un premio mayor. Aunque el esquema (46, 6, 5) aún no se ha calculado, existen esquemas lo suficientemente cercanos para su aplicación práctica. Uno de ellos probablemente fue utilizado por un cartel criminal.

El número de nuevos circuitos calculados está en constante crecimiento. Muchos de ellos encuentran aplicación práctica, como (15, 3, 2) del problema clásico y (46, 6, 5) . Salen guías de 1000 páginas con diagramas. Sin embargo, los matemáticos aún no saben cómo determinar si existe una solución para determinadas condiciones específicas. Gracias a Kivash, aprendimos que la probabilidad de esto es bastante alta. Entonces, al menos ahora está claro que con todas las incógnitas, es mejor buscar una solución que abandonarla. Además, existen herramientas para generar circuitos de muestra para cualquier parámetro.

Pero gracias al trabajo de Kivash, se esperaba que el método podría ser desarrollado para crear precisaesquemas para cualquier parámetro. Si esto sucede, será un avance extraordinario en matemáticas.

Sin embargo, el trabajo de Kivash es puramente teórico. Los expertos dicen que crear algoritmos prácticos basados ​​en su método requerirá el arduo trabajo de varias generaciones más de matemáticos.

Source: https://habr.com/ru/post/es380785/