Ensino Superior ⇒ Exercício principio da casa dos pombos

[LuizF]

olá pessoal! to tentando resolver essa questão e não to conseguindo.
Uma rede de computadores é formada por seis computadores. Cada computador é conectado diretamente a, pelo menos, um dos outros computadores. Mostre que há pelo menos dois computadores na rede que estão diretamente conectados ao mesmo número de outros computadores.

[lucas36]

Olá Luiz,
O problema é um pouco mais complexo pois os "pombos" e as "casas" a princípio não parecem ser facilitadores.
Primeiro, cada computador pode estar conectado á [tex3]0, 1, ..., 5[/tex3] outros computadores, totalizando [tex3]6[/tex3] valores possíveis.
Sejam [tex3]a, b, c, d, e, f[/tex3] as quantidades de computadores conectados aos [tex3]5[/tex3] computadores.
Com isso, [tex3]a, b, c, d, e, f[/tex3] são iguais á [tex3]0[/tex3], ou [tex3]1[/tex3], ou..., ou [tex3]5[/tex3].
Mas veja que se um computador [tex3]C[/tex3] está conectado á todos os outros, isto é, uma das variáveis é igual á [tex3]5[/tex3], então não existe computador q não esteja conectado á nenhum pois este está conectado á [tex3]C[/tex3].
Reciprocamente, se um computador [tex3]C'[/tex3] não está conectado á nenhum, não existe computador conectado á todos pois este não está conectado á [tex3]C'[/tex3].
Dessa forma, os números [tex3]0, 5[/tex3] não podem aparecer simultaneamente nos conjuntos [tex3]a, b, c, d, e, f[/tex3].
Com isso, no máximo [tex3]5[/tex3] valores podem compor os conjuntos [tex3]a, b, c, d, e, f[/tex3], que possuem [tex3]6[/tex3] elementos.
Pelo princípio das Casas de pombos, haverá duas variáveis com o mesmo valor, isto é, dois computadores conectados ao mesmo número de computadores.