Amigos do Orkut

[Molina]

Bom dia.

Este desafio fica para quem quiser de "divertir" um pouco neste feriadão:


Prove que existe pelo menos duas pessoas no Orkut com o mesmo número de amigos.

Devemos considerar que:

# O número de pessoas que utilizam o orkut é n > 1
# A relação "ser amigo" é simétrica (Se X é amigo de Y, então Y é amigo de X)
# A relação "ser amigo" é não-reflexiva (X não é amigo de X)


Confesso que antes de ver esta questão, não tinha parado para pensar que isso acontece mesmo. Minha sugestão é usar provar por indução. Mas antes, verifique que isso é verdade mesmo, pegar por exemplo, 2 pessoas, 3 pessoas, 4 pessoas, 5 pessoas...


Aproveito aqui para deixa o link de nossa comunidade no orkut: http://www.orkut.com.br/Main#Community.aspx?cmm=297062


Boa sorte,

[Douglasm]

Boa tarde Molina. Durante meus estudo de combinatória, esbarrei com a solução desse problema. Ele é baseado no princípio das gavetas de Dirichlet. Observemos que num grupo de n pessoas, um pessoa conhece entre 0 e n-1 pessoas. Observemos também que se há uma pessoa que conhece todas as outras (n-1 pessoas) não há pessoa alguma sem conhecidos (que conheça 0 pessoas). Distribuindo em "gavetas" as pessoas que conhecem 0 pessoas, 1 pessoa, 2 pessoas,...,n-1 pessoas, temos n "gavetas". Mas como não podemos ter a 1ª e a última gaveta ocupadas ao mesmo tempo, isso demonstra que pelo menos 2 indivíduos conhecem o mesmo número de pessoas. Creio que seja isso. Até a próxima!