Festa com 11 pessoas. Todas astutas e com raciocínio veloz. Os participantes notam fato curioso: se formarem um grupo com cinco pessoas quaisquer, há sempre alguém entre os restantes que conhece todas as cinco pessoas do grupo – e estas também conhecem a pessoa ‘de fora’, ou seja, a ‘amizade’ entre eles é mútua.

Quando os convivas percebem isso, eles concluem: há alguém na festa que conhece todos os 11 presentes! Por que isso é verdade?

Para responder, vamos ‘brincar’ com o problema, imaginando exemplos simples e concretos, para ver se há um padrão. Mãos à obra! 

Primeiro, com o que já sabemos, podemos garantir que todo mundo na festa conhece alguém. Vejamos o porquê! Escolha uma pessoa e forme um grupo com outras quatro quaisquer. Necessariamente, alguém de fora desse grupo conhece essas cinco pessoas. Então, esse ‘alguém de fora’ tem que conhecer a pessoa que escolhemos. Portanto, todo mundo na festa conhece, pelo menos, mais uma pessoa.

Com essa informação, sabemos agora que temos ‘grupinhos de dois’ que se conhecem entre si. Será que teríamos ‘grupinhos de três’ com essa propriedade? Vamos além: qual seria o tamanho do maior ‘grupinho’ em que todos se conhecem mutuamente? 

Digamos que esse grupo maior tenha N pessoas. Se N for maior ou igual a seis, então, conseguiremos provar que há alguém que conhece todo mundo. Para isso, bastaria formar um grupo com os cinco que não são parte do ‘grupinho de seis’ que se conhecem entre si.

Como sabemos que há alguém de fora do grupo de cinco que conhece todos eles, então, tem que ser alguém do grupinho de seis. Portanto, essa pessoa conhece todo mundo na festa.

E se o grupo tiver menos que seis pessoas? Nesse caso, N estaria entre dois e cinco. Assim, podemos ‘completar’ esse grupo com outras pessoas, para formar um grupo de cinco pessoas – lembremos que, se N = 5, não precisaremos juntar mais ninguém. 

Fora desse grupo, há alguém que conhece todos eles – em particular, os tais N que se conhecem entre si. Então, podemos formar um grupo com N + 1 pessoas no qual todo mundo se conhece mutuamente.

Mas, inicialmente, supusemos que N é o número de pessoas do maior grupo no qual todos se conhecem – e que N está entre dois e cinco. Portanto, acabamos de mostrar que ele pode aumentar em uma unidade. Mas isso é uma contradição! 

Conclusão: o maior grupo de pessoas no qual todos se conhecem tem seis ou mais pessoas. Usando o argumento anterior, concluímos que há alguém que conhece todo mundo na festa.