Colegiais de Kirkman: o problema que fascina matemáticos há 172 anos

Números embaralhados
Enigma chamou a atenção de diversos matemáticos reconhecidos

Imagine que seu tão esperado aumento de salário depende de você fazer apenas uma coisa.

Sua chefe está organizando um congresso e confirmou a presença de sete grandes especialistas que vão debater entre si em mesas redondas. E ela pede a você que cada mesa tenha apenas três debatedores.

Até aqui, tudo bem, certo? Já está visualizando sua conta bancária?

Mas, durante a conversa com os debatedores, você descobre um detalhe: eles são os melhores nas suas áreas, mas não se dão bem entre si — e cada um, à sua maneira, impõe uma condição:

"Posso participar das mesas como for necessário, mas quero estar presente com cada um dos outros seis convidados apenas uma vez, nem mais, nem menos."

Parece difícil, mas não se desespere.

O que a sua chefe está pedindo é muito semelhante à questão formulada pelo matemático britânico Thomas Kirkman em 1850 — conhecida como problema das colegiais.

Com a ajuda do professor de matemática Raúl Ibáñez, da Universidade do País Basco, na Espanha, vamos te contar do que se trata.

"O problema das colegiais fascina as pessoas há muito tempo. Parece um quebra-cabeça, um enigma, mas tem aspectos muito profundos por trás dele", afirma Ibáñez, que é divulgador científico e autor de diversos livros e artigos sobre matemática. Um de seus livros dedica um capítulo a esse problema.

"Parece fácil, mas é intrinsecamente muito complicado, e sua resolução nem sempre é simples", afirma o professor.

Teoria de grupos

Kirkman nasceu em Manchester, na Inglaterra, em 1806.

Um professor observou na escola que ele tinha potencial para ser aceito na Universidade de Cambridge, mas seu pai tinha outros planos.

Ilustração do Trinity College, em Dublin
Thomas Kirkman estudou no histórico Trinity College, em Dublin, na Irlanda — esta ilustração foi publicada na revista The Illustrated London News em 1873

"Thomas foi obrigado a abandonar a escola aos 14 anos e ir trabalhar no escritório do pai", conforme contam, em uma breve biografia, os professores John Joseph O'Connor e Edmund Frederick Robertson, da Universidade de St. Andrews, no Reino Unido.

"Depois de nove anos trabalhando no escritório, Thomas contrariou os desejos do pai e entrou para o Trinity College de Dublin, na Irlanda, para estudar matemática, filosofia, os clássicos e ciências, a fim de obter uma licenciatura", dizem os professores.

Em 1835, Kirkman voltou para a Inglaterra e, quatro anos depois, se tornou vigário de uma paróquia da Igreja Anglicana, ocupando o cargo por 52 anos. Casou-se e teve três filhos.

Como indicou Robin Wilson, professor emérito de matemática pura da Open University, no Reino Unido, no artigo The Early History of Block Designs ("A história inicial dos desenhos de blocos", em tradução livre), os deveres paroquiais de Kirkman "ocupavam pouco do seu tempo".

Por isso, o reverendo "concentrava muitos esforços nas suas pesquisas matemáticas, especialmente em temas de álgebra e análise combinatória".

Os sistemas triplos

Em 1846, Kirkman apresentou seu primeiro artigo, com o título On a Problem in Combinations ("Sobre um problema de combinações", em tradução livre). Ele foi publicado em 1847, na revista Cambridge and Dublin Mathematical Journal.

O artigo é considerado pioneiro do sistema triplo de Steiner, vários anos antes da sua apresentação pelo geômetra suíço Jakob Steiner (1796-1863), considerado um dos mais importantes do século 19.

Jakob Steiner
O matemático suíço Jakob Steiner nasceu em 1796 e morreu em 1863

"Talvez esses sistemas triplos devessem ter sido chamados sistemas de Kirkman, já que ele foi o primeiro a publicá-los", afirma Ibáñez.

Ao longo da sua carreira, Kirkman aprofundou-se na teoria de grupos e deixou importantes contribuições para a análise combinatória.

Matemática recreativa

Kirkman publicou o problema das colegiais na revista The Lady's and Gentleman's Diary, dedicada a questões matemáticas, enigmas e poesia.

Arthur Cayley
O matemático inglês Arthur Cayley é considerado líder da escola britânica de matemática pura que surgiu no século 19

Era um quebra-cabeça, uma recreação matemática, apresentada desta forma:

"Quinze jovens estudantes saem para passear todos os dias da semana, de segunda a domingo, de forma ordenada, formando cinco filas de três colegiais cada uma. Como devemos organizá-las todos os dias da semana para que nenhuma dupla de colegiais compartilhe a mesma fila por mais de um dia?"

Esta abordagem chamou a atenção de diversos matemáticos reconhecidos, entre eles o britânico Arthur Cayley (1821-1895), que publicou rapidamente uma solução. Kirkman apresentaria outra e, a partir de então, surgiriam diversas resoluções.

Kirkman idealizou o problema das colegiais exatamente enquanto escrevia seu artigo sobre os sistemas triplos.

"Temos n elementos, 1, 2, 3 até n, e a ideia é criar coleções de três números deste conjunto, chamadas de blocos, de forma que cada par de elementos apareça exatamente em um trio", explica Ibáñez.

O que Kirkman pede no seu problema é que, para 15 pessoas ou elementos, possamos desenvolver um sistema triplo separado em sete grupos (um para cada dia da semana), de forma que, em cada um deles, estejam todos os elementos — no caso, as colegiais.

Os quadrados de Room

Cayley é considerado um dos fundadores da escola britânica de matemática pura, que surgiu no século 19.

Em 1850, ele decidiu prestar atenção ao problema das 15 colegiais e chegou a uma solução por meio do que hoje é conhecido como quadrados de Room — que viriam a ser documentados pelo matemático australiano Thomas Gerald Room (1902-1986).

O professor explica que, em um quadrado de Room, temos n+1 símbolos.

Imagine 8 números, de 1 a 8.

Como escolhemos oito símbolos, fazemos uma tabela de 7x7: sete linhas e sete colunas.

Mas é preciso atender a três condições:

  1. Cada quadrado está vazio ou tem um par de números. Por exemplo, um quadrado pode ter 35, outro pode ter 86, outro pode ter o 13 ou não ter nada.

  2. Cada símbolo aparece uma única vez em cada linha e em cada coluna. Se pegarmos uma linha, por exemplo, o 1 aparecerá em um dos quadrados, o 2 em outro e assim até o 8. Nas colunas, ocorre a mesma coisa, mas aparecerão formando um par de números.

  3. Cada par não ordenado de símbolos aparece uma única vez. O par 12, por exemplo, aparece uma única vez em toda a tabela, o 13 aparece uma única vez, e assim até o final, até o par 78.

Um exemplo seria este:

Quadrado de Room
Quadrado de Room

O que Cayley fez foi usar esse tipo de quadrado de Room e combiná-lo com os sistemas triplos, que Kirkman já estava estudando, para chegar a uma solução para o problema das colegiais.

Cayley distribuiu as 15 estudantes da seguinte forma: ele indicou as sete primeiras com letras de "a" até "g", e as outras oito com números, de 1 a 8.

Os números servem para formar um quadrado de Room, conforme ilustrado acima, e as letras para fazer sistemas triplos de ordem sete, como este:

Conjuntos de letras
Conjuntos de letras

Esses trios são colocados à esquerda do quadrado de Room, desta forma:

Quadrados de room com números e letras
Quadrados de room com números e letras

A solução

A partir dessa estrutura, surge uma solução.

Vamos transpor o quadro para as 15 colegiais e os sete dias em que elas saem para passear.

Mas antes, vamos dar nomes às letras e aos números da tabela de Cayley:

  • a=Ana

  • b=Bia

  • c=Carol

  • d=Diana

  • e=Emma

  • f=Fany

  • g=Gina

  • 1=Maria

  • 2=Katy

  • 3=Yeny

  • 4=Lola

  • 5=Sofia

  • 6=Gabi

  • 7=Pili

  • 8=Yoli

A solução vem do quadrado de letras e números mais acima. Cada linha desse quadrado nos fornece os grupos de três estudantes de cada um dos sete dias da semana.

Ou seja, na segunda-feira é abc, d35, e17, f82 e g64. A solução, com nossas estudantes, seria esta:

A arte da análise combinatória

Tanto Kirkman quanto Cayley "sabiam que havia algo profundo por trás desse problema e, por isso, dedicaram-se a ele".

Ilustração com elementos da ciência
Ilustração com elementos da ciência

"A análise combinatória é a arte de selecionar ou ordenar os elementos de um certo conjunto" — e isso é precisamente o que Cayley nos mostra com sua solução. O problema das colegiais é de organização.

"As estudantes e como agrupá-las para ir ao colégio em cada dia são uma metáfora de estrutura matemática, na verdade, combinatória, que pode ser usada em muitos outros aspectos da nossa vida", afirma Ibáñez.

"Este é o motivo pelo qual a matemática é abstrata — para que ela seja uma ferramenta que possa ser utilizada em contextos muito diferentes, como a física, biologia, química ou medicina."

Segundo ele, a matemática que intervém no problema das colegiais é parte de todo um ramo que é fundamental na teoria de códigos e criptografia, planejamento, geometria, projetos de experimentos estatísticos, teoria da computação e redes de comunicação.

"Tudo o que surge da tentativa de solucionar um quebra-cabeça acabou se convertendo em duas teorias matemáticas: os sistemas triplos de Steiner e a teoria de desenho de blocos, ambas com muitas aplicações práticas", afirma Ibáñez.

Isso acontece porque a matemática "não se contenta" com solucionar o problema.

"Em alguns casos, como este, ela também observa quantas formas distintas de solução existem. E, para o problema das colegiais de Kirkman, demonstrou-se, no início do século 20, que havia 80 soluções distintas."

O problema que gera mais problemas

As colegiais também fizeram surgir novos problemas.

Martin Gardner
Martin Gardner, considerado um mestre da matemática recreativa, popularizou o problema dos 9 prisioneiros, idealizado por Henry Ernest Dudeney com base nas colegiais de Kirkman

"Outra prática habitual na ciência de Pitágoras é expor o problema de forma mais geral", diz Ibáñez.

"Por isso, o problema das colegiais foi proposto para grupos com outras quantidades de estudantes."

A solução para todos os casos só chegou em 1968, quando os matemáticos Ray-Chaudhuri e R. M. Wilson publicaram a "solução completa para o caso geral".

Ainda assim, o problema continua em aberto, pois os sistemas triplos de Steiner ou, de forma mais geral, o desenho de blocos são um ramo "muito ativo" da matemática.

"Um quebra-cabeça como este, que, em princípio, era uma questão pequena, tornou-se uma teoria com centenas de problemas abertos, pesquisas, artigos e livros", afirma Ibáñez.

E, enquanto tentavam resolvê-lo, muitos matemáticos usaram e desenvolveram técnicas diferentes.

O matemático americano Martin Gardner, por exemplo, publicou na revista Scientific American uma solução geométrica para o problema das colegiais: um círculo, com números e triângulos sobre ele, que oferece uma resposta diferente à medida que é girado.

Voltando à questão que poderia te dar o desejado aumento de salário, a resposta é designar um número para cada um dos convidados e criar um sistema triplo, que levará, por exemplo, a sete mesas:

Mesas
Mesas

E, se você quiser agradecer a alguém pelo merecido aumento de salário, sem dúvida os agradecimentos vão para Thomas Kirkman e, claro, para o professor Ibáñez.

*Gráficos: Manuella Bonomi e Ana Lucía González

Este texto foi publicado originalmente em https://www.bbc.com/portuguese/geral-63711028