|
|
| {{subiu_orn | }} |
{{subiu_num | }} |
{{subiu_orn | }} |
{{subiu_caps | }}
{{subiu_linha | }}
|
|
A roda de 6 pessoas onde um trio sempre aparece
Com 6 pessoas, sempre há 3 conhecidos ou 3 estranhos entre si; com 5, a garantia some. Para 5 contra 5, a conta segue aberta.
|
Seis convidados, quinze pares, um trio garantido
|
| ▼ |
| |
|
Numa festa cheia de gente que você mal conhece, dá para garantir que algum trio já se conhece? Dá, desde que a roda tenha pelo menos 6 pessoas, e a garantia vale para qualquer festa do planeta.
Faça a conta das duplas. Seis pessoas formam 15 pares possíveis. Cada par está num de dois estados: os dois se conhecem ou nunca se viram. Não existe terceira opção, e ninguém escolhe como os pares vão cair.
Mesmo assim, a saída é certa. Seja qual for a mistura, sempre aparecem três pessoas que se conhecem todas entre si, ou três que são estranhas todas entre si. Em muitas festas aparecem os dois trios de uma vez.
Com 5 pessoas, a garantia some. Existe um jeito de arrumar as amizades de uma roda de 5 em que nenhum trio fecha, nem de conhecidos, nem de estranhos. Basta um arranjo desses para derrubar a regra, e ele existe.
O 6 tem nome. Na matemática, ele é o número de Ramsey R(3,3), lido como "erre de três e três": o menor tamanho de grupo que obriga o aparecimento de um trio de um tipo ou de outro. O primeiro 3 conta os conhecidos, o segundo conta os estranhos.
Troque o trio por um quinteto e a pergunta muda de tamanho. Qual é a menor festa que garante 5 conhecidos entre si ou 5 estranhos entre si? Esse valor se chama R(5,5), e ninguém sabe qual é. Os matemáticos cercaram o número por baixo e por cima, e o cerco ainda deixa folga.
O motivo não é preguiça nem falta de computador. Uma festa de 43 pessoas tem 903 pares, e cada par pode cair de dois jeitos. O total de arranjos possíveis é um número com 272 algarismos, grande demais para qualquer máquina testar um por um.
A saída, então, tem que ser prova no papel, como a que resolve o caso do 6 em quatro linhas. A mesma ideia que funciona com seis pessoas emperra quando a festa cresce, e é aí que a matemática trava há quase um século.
Quem descobriu que a festa sempre esconde um trio, em que artigo a pergunta nasceu e até onde chegou o cerco ao R(5,5) está logo abaixo, na resposta.
Continue lendo ↓
|
|
|
|
I A resposta de ontem
O lógico de Cambridge que provou a festa
|
|
Frank Plumpton Ramsey, matemático, filósofo e economista inglês de Cambridge, provou o princípio da festa em 1928. O resultado saiu no artigo On a Problem of Formal Logic (Sobre um problema de lógica formal), publicado em 1930 nos Proceedings of the London Mathematical Society (Atas da Sociedade Matemática de Londres).
A festa não aparece no artigo. Ramsey estudava lógica: queria um método para decidir se certas frases matemáticas são verdadeiras. No caminho, precisou de um lema (resultado auxiliar, usado como degrau para outro) que diz o seguinte: todo conjunto grande o bastante, dividido em duas cores, esconde um pedaço de uma cor só.
A versão das seis pessoas é o caso mais simples desse lema. Ramsey provou que o número existe para qualquer tamanho de trio, quarteto ou quinteto, mas não calculou nenhum deles. A prova garantia a existência e não dizia o valor.
Ramsey teve pouco tempo. Aos 19 anos, ainda aluno, ajudou na tradução para o inglês do Tractatus Logico-Philosophicus (Tratado lógico-filosófico), de Ludwig Wittgenstein. Em 1928 publicou um estudo sobre poupança que John Maynard Keynes elogiou em público. Faleceu em janeiro de 1930, aos 26 anos, depois de uma cirurgia, antes de ver o artigo impresso.
O lema ficou esquecido até 1935. Naquele ano, os húngaros Paul Erdős e George Szekeres chegaram à mesma ideia por outro caminho, num artigo sobre pontos no plano publicado na revista Compositio Mathematica. Erdős espalhou o assunto pelo mundo, e o ramo inteiro ganhou o nome de teoria de Ramsey.
A roupa de festa veio depois. Em 1953, o problema das seis pessoas caiu na prova Putnam, o concurso universitário de matemática dos Estados Unidos, com pontos e linhas coloridas. A tradução para conhecidos e estranhos pegou e virou o jeito clássico de apresentar o teorema.
|
Ramsey provou que o número existe para qualquer tamanho de grupo; calcular quanto ele vale virou o trabalho de quase um século.
|
O cerco ao R(5,5)
Robert Greenwood e Andrew Gleason calcularam os primeiros valores em 1955, no Canadian Journal of Mathematics (Revista Canadense de Matemática). Mostraram que R(3,3) vale 6 e que, para 4 conhecidos ou 4 estranhos, a festa mínima tem 18 pessoas.
Para o quinteto, o piso veio em 1989, quando Geoffrey Exoo, da Universidade Estadual de Indiana, montou uma festa de 42 pessoas sem nenhum quinteto de uma cor só. Logo, R(5,5) vale pelo menos 43.
O teto caiu em etapas. Em 2024, Vigleik Angeltveit e Brendan McKay provaram, com ajuda de computador, que R(5,5) vale no máximo 46. O valor exato está em 43, 44, 45 ou 46, e ninguém sabe qual, porque falta um método que descarte os casos sem testar todos.
|
|
|
|
|
II O Enigma do dia
Quinze pares e duas cores
|
|
Prove que, em qualquer grupo de 6 pessoas, existem 3 que se conhecem todas entre si ou 3 que são estranhas todas entre si. Pergunta extra: monte uma roda de 5 pessoas em que nenhum dos dois trios aparece.
|
O enigma pede prova, sem testar festa por festa. Testar uma a uma daria trabalho demais: com 15 pares e dois estados por par, são 32.768 arranjos possíveis para seis pessoas.
Comece trocando pessoas por desenho. Cada pessoa vira um ponto, e cada par vira uma linha entre dois pontos. Os matemáticos chamam o desenho de grafo (conjunto de pontos ligados por linhas).
Agora pinte as linhas. Azul para quem se conhece, vermelho para quem nunca se viu. Um trio de conhecidos vira um triângulo com os três lados azuis; um trio de estranhos vira um triângulo com os três lados vermelhos.
O enigma, na linguagem do desenho, fica assim: em seis pontos com todas as 15 linhas pintadas, sempre existe um triângulo de uma cor só. Na pergunta extra, com cinco pontos e 10 linhas, você precisa pintar sem formar nenhum.
A primeira pista é olhar para uma pessoa só. Ela tem 5 linhas saindo dela, uma para cada outra pessoa. Com duas cores e 5 linhas, uma das cores aparece pelo menos 3 vezes.
A regra por trás da pista é o princípio da casa dos pombos: se 5 cartas vão para 2 gavetas, alguma gaveta recebe pelo menos 3. Nenhuma divisão escapa, porque 2 mais 2 dá só 4.
A segunda pista está nas três pessoas do outro lado dessas 3 linhas. Olhe as linhas entre elas e pergunte o que acontece se uma for da mesma cor das três primeiras.
Para a pergunta extra, a pista é o equilíbrio. Na roda de 5, cada pessoa tem 4 linhas. Se alguém tiver 3 da mesma cor, o raciocínio acima volta a funcionar e o trio aparece. Todo mundo precisa ficar com 2 azuis e 2 vermelhas.
Onde a prova tropeça
A primeira armadilha é provar com exemplos. Desenhar três festas e achar um trio em todas não mostra que a próxima também terá.
A segunda é esquecer o trio de estranhos. A prova precisa cobrir os dois lados, e a mesma linha de raciocínio serve para as duas cores.
A terceira aparece na roda de 5: pôr todo mundo como estranho parece esvaziar os trios, mas cria o contrário. Se ninguém se conhece, qualquer trio é de estranhos.
|
Uma pessoa, cinco linhas, duas cores: a prova inteira nasce da gaveta que recebe três cartas.
|
Responda por escrito: a prova em até cinco frases e o desenho da roda de 5 sem trio, dizendo quem conhece quem.
|
| |
|
