A tarefa de 165 anos atrás assombra matemáticos

Em 1850, o Rev. Thomas Kirkman, matemático britânico e reitor da paróquia de Lancashire, formulou um quebra-cabeça de aparência inocente em uma revista de entretenimento para os amantes da matemática “Notebook for Ladies and Gentlemen”:

“Quinze jovens estudantes saem para passear por sete dias em três filas: você precisa organizar todos os dias "para que o mesmo par de alunas nunca se encontre duas vezes na mesma fila."

A tarefa parece simples, mas se você tentar resolvê-la, imediatamente perceberá que não é assim. Você pode tentar resolvê-lo com um lápis e papel ou jogar na versão HTML .

Devido à sua falsa simplicidade, a tarefa rapidamente se tornou famosa. Os amantes da matemática enviaram suas decisões e os cientistas publicaram artigos científicos com a tentativa de formular uma solução geral para o problema.

Como resultado, esse quebra-cabeça ajudou a moldar uma nova área da matemática: esquemas combinatórios , que agora são objeto de grossos livros didáticos.. O que começou como uma tarefa simples de distribuir pessoas em grupos (ou esquemas, como eram chamados eventualmente) agora se tornou um método usado no design experimental, códigos de correção de erros em ciência da computação, criptografia, agricultura, esportes e até fraudes de jogo (houve uma história em que um cartel criminoso ganhou milhões de dólares em sete anos comprando bilhetes com todas as combinações possíveis de 5 em 46 em uma loteria em 6 de 46 se o custo dos ingressos fosse menor que os bônus extras por ganhar 5 em 46 mais a probabilidade de ganhar o jackpot).

Por exemplo, o código clássico de Hamming para resolver erros usa a solução do problema das alunas (criando grupos de três alunas, onde nenhum par é repetido), mas apenas para o esquema de sete meninas (bit).


Avião Fano para (7, 3, 2)

Surpreendentemente, por 165 anos, os matemáticos não foram capazes de resolver o problema de maneira geral. Eles ainda não pode dar uma resposta, qual é a solução para o quebra-cabeça sob as condições iniciais: existem n alunas, você precisa criar grupos de tamanho k , para que conjuntos de t meninas nunca se encontraram duas vezes no mesmo grupo. Essa formulação é chamada de esquema (n, k, t) .

Por exemplo, para um grupo de 19 meninas, existem mais de 11 bilhões de trigêmeos possíveis em que cada par se encontra apenas uma vez. Este número é a resposta. Mas o número de opções está crescendo exponencialmente com um aumento no número de alunas.

É claro que o problema é resolvido sob certas condições e não é resolvido sob outras. Por exemplo, se trigêmeos de todos os pares possíveis são compostos por seis alunas, obviamente o problema não está resolvido (há cinco pares possíveis com a estudante Anya, ao mesmo tempo, cada trigêmeo tem dois pares com Anya e cinco não são divididos em dois). Ou seja, de acordo com o princípio da divisibilidade, muitas opções (n, k, t) são eliminadas imediatamente .

Ao mesmo tempo, existem (n, k, t) que cumprem totalmente o princípio da divisibilidade, mas ainda não têm solução: por exemplo, (47, 3, 2) .

Nos últimos anos, a solução ficou conhecida por muitas combinações (n, k, t)que foram verificados algebricamente ou por força bruta nos computadores. Mas como resolver isso de uma maneira geral, o que fazer com exceções como (47, 3, 2) ? Como entender se um problema tem uma solução ou não?

Essa tarefa há muito é considerada um dos problemas mais famosos da combinatória, diz o matemático Gil Kalai, da Universidade Hebraica de Jerusalém, em entrevista à Wired. Ele se lembra de discutir com colegas sobre isso há um ano e meio e eles chegaram à conclusão de que "nunca saberemos a resposta, porque a tarefa é claramente muito complicada".

No entanto, apenas duas semanas depois, o jovem professor de matemática Peter Keevash, de Oxford, provou que Kalai estava errado. Num artigo científicoa partir de janeiro de 2014, ele argumenta que quase sempre existe uma solução para um problema se a condição de divisibilidade for atendida. Em um novo artigo de abril de 2015, ele mostrou como calcular o número aproximado de soluções para determinados parâmetros.

Ninguém esperava que a teoria das probabilidades fosse aplicada à solução do problema, mas o método funcionou perfeitamente.

Voltando às loterias, os golpistas perceberam que é possível reduzir o número de bilhetes comprados comprando todas as combinações de 5 em 46 (ao especificar 6 em 46 números), então eles receberão absolutamente todos os prêmios adicionais e também poderão receber um jackpot. Embora o esquema (46, 6, 5) ainda não tenha sido calculado, existem esquemas suficientemente próximos para aplicação prática. Um deles provavelmente foi usado por um cartel criminoso.

O número de novos circuitos calculados está em constante crescimento. Muitos deles encontram aplicação prática, como (15, 3, 2) do problema clássico e (46, 6, 5) . São apresentados guias de 1000 páginas com diagramas. No entanto, os matemáticos ainda não sabem como determinar se existe uma solução para determinadas condições específicas. Graças a Kivash, aprendemos que a probabilidade disso é bastante alta. Portanto, pelo menos agora está claro que, com todas as incógnitas, é melhor procurar uma solução do que recusá-la. Além disso, existem ferramentas para gerar circuitos de amostra para quaisquer parâmetros.

Mas graças ao trabalho de Kivash, esperava-se que um método poderia ser desenvolvido para criar precisasesquemas para quaisquer parâmetros. Se isso acontecer, será um avanço extraordinário em matemática.

No entanto, o trabalho de Kivash é puramente teórico. Especialistas dizem que a criação de algoritmos práticos com base em seu método exigirá o trabalho árduo de várias gerações de matemáticos.

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