Mapeamento de conexões no seu próximo baile. unclibraries_commons 

Digamos que você esteja planejando sua próxima festa e agonizando na lista de convidados. Para quem você deve enviar convites? Que combinação de amigos e estranhos é a mistura certa?

Acontece que os matemáticos estão trabalhando em uma versão deste problema há quase um século. Dependendo do que você quer, a resposta pode ser complicada.

Nosso livro, “O fascinante mundo da teoria dos grafos, Explora puzzles como estes e mostra como eles podem ser resolvidos através de gráficos. Uma pergunta como essa pode parecer pequena, mas é uma bela demonstração de como os gráficos podem ser usados ​​para resolver problemas matemáticos em campos tão diversos quanto as ciências, a comunicação e a sociedade.

Nasce um quebra-cabeça

Embora seja bem conhecido que Harvard é uma das melhores universidades acadêmicas do país, você pode se surpreender ao saber que houve uma época em que Harvard tinha um dos melhores times de futebol do país. Mas no 1931, liderado por All-American quarterback Barry Woodtal foi o caso.

Naquela temporada, Harvard jogou o Exército. No intervalo, inesperadamente, o Exército liderou a Harvard 13-0. Claramente chateado, o presidente de Harvard disse ao comandante de cadetes do Exército que, embora o Exército possa ser melhor que Harvard no futebol, Harvard era superior em uma competição mais acadêmica.

Embora Harvard tenha voltado a derrotar o Exército 14-13, o comandante aceitou o desafio de competir contra Harvard em algo mais erudito. Ficou acordado que os dois competiriam - em matemática. Isso levou a Army e Harvard a selecionar times de matemática; o confronto ocorreu em West Point em 1933. Para surpresa de Harvard, o exército venceu.

A competição Harvard-Army acabou levando a uma competição anual de matemática para alunos de graduação da 1938, chamada de Exame de Putnam, nomeado para William Lowell Putnam, um parente do presidente de Harvard. Este exame foi projetado para estimular uma rivalidade saudável em matemática nos Estados Unidos e no Canadá. Ao longo dos anos e continuando até hoje, este exame contém muitos problemas interessantes e muitas vezes desafiadores - incluindo o que descrevemos acima.

Linhas vermelhas e azuis

O exame 1953 continha o seguinte problema (reformulado um pouco): Existem seis pontos no plano. Cada ponto é conectado a todos os outros pontos por uma linha azul ou vermelha. Mostre que há três desses pontos entre os quais apenas linhas da mesma cor são desenhadas.

Em matemática, se houver uma coleção de pontos com linhas desenhadas entre alguns pares de pontos, essa estrutura é chamada de gráfico. O estudo desses gráficos é chamado de teoria dos grafos. Na teoria dos grafos, no entanto, os pontos são chamados de vértices e as linhas são chamadas de arestas.

Os gráficos podem ser usados ​​para representar uma ampla variedade de situações. Por exemplo, neste problema de Putnam, um ponto pode representar uma pessoa, uma linha vermelha pode significar que as pessoas são amigas e uma linha azul significa que elas são estranhas.

Mostre que há três pontos conectados por linhas da mesma cor. Gary Chartrand

Por exemplo, vamos chamar os pontos A, B, C, D, E, F e selecionar um deles, digamos A. Das cinco linhas desenhadas de A para os outros cinco pontos, deve haver três linhas da mesma cor.

Diga que as linhas de A a B, C, D são todas vermelhas. Se uma linha entre quaisquer dois de B, C, D é vermelho, então há três pontos com apenas linhas vermelhas entre eles. Se nenhuma linha entre quaisquer dois de B, C, D for vermelho, então eles são todos azuis.

E se houvesse apenas cinco pontos? Pode não haver três pontos em que todas as linhas entre elas sejam coloridas da mesma maneira. Por exemplo, as linhas A – B, B – C, C – D, D – E, E – A podem ser vermelhas, com as outras azuis.

Pelo que vimos, então, o menor número de pessoas que podem ser convidadas para uma festa (onde cada duas pessoas são amigas ou estranhas), de modo que há três amigos em comum ou três estranhos em comum é seis.

E se quisermos que quatro pessoas sejam amigos em comum ou estranhos em comum? Qual é o menor número de pessoas que devemos convidar para uma festa para ter certeza disso? Esta questão foi respondida. É o 18.

E se quisermos que cinco pessoas sejam amigos em comum ou estranhos em comum? Nessa situação, o menor número de pessoas a convidar para uma festa para garantir isso é - desconhecido. Ninguém sabe. Embora esse problema seja fácil de descrever e talvez pareça bastante simples, é notoriamente difícil.

Números Ramsey

O que temos discutido é um tipo de número na teoria dos grafos chamado número de Ramsey. Estes números são nomeados para o filósofo britânico, economista e matemático Frank Plumpton Ramsey.

Ramsey morreu com a idade de 26, mas obteve em sua tenra idade um teorema muito curioso em matemática, o que deu origem à nossa questão aqui. Digamos que temos outro plano cheio de pontos conectados por linhas vermelhas e azuis. Nós escolhemos dois inteiros positivos, chamados r e s. Queremos ter exatamente r pontos onde todas as linhas entre eles sejam vermelhas ou pontos onde todas as linhas entre elas sejam azuis. Qual é o menor número de pontos com que podemos fazer isso? Isso é chamado um número de Ramsey.

Por exemplo, digamos que nosso avião tenha pelo menos três pontos conectados por todas as linhas vermelhas e três pontos conectados por todas as linhas azuis. O número de Ramsey - o menor número de pontos que precisamos para que isso aconteça - é seis.

Quando os matemáticos analisam um problema, eles freqüentemente se perguntam: isso sugere outra questão? Foi o que aconteceu com os números de Ramsey - e os problemas das festas.

Por exemplo, aqui está uma: cinco garotas estão planejando uma festa. Eles decidiram convidar alguns meninos para a festa, se eles conhecem os meninos ou não. Quantos meninos precisam convidar para ter certeza de que sempre haverá três meninos entre eles, de modo que três das cinco garotas sejam amigas dos três garotos ou não conheçam os três garotos? Provavelmente não é fácil adivinhar a resposta. É 41!

Muito poucos números de Ramsey são conhecidos. No entanto, isso não impede que os matemáticos tentem resolver tais problemas. Muitas vezes, não resolver um problema pode levar a um problema ainda mais interessante. Essa é a vida de um matemático.

Sobre os Autores

Gary Chartrand, Professor Emérito de Matemática, Western Michigan University; Arthur Benjamin, professor de matemática, Harvey Mudd Colégioe Ping Zhang, professor de matemática, Western Michigan University

Este artigo foi originalmente publicado em A Conversação. Leia o artigo original.

Livros relacionados:

at InnerSelf Market e Amazon