Se existe uma pessoa com pelo menos n conhecidos, nada temos a provar.
Se não, escolha uma pessoa qualquer: ela conhece no máximo n-1 pessoas.
Elimine ela e os conhecidos e fique com >= (m-2)n + 1 pessoas, repita o
passo m-1 vezes e você terá obtido um conjunto de m pessoas que não se
conhecem.
[ ]'s
PS: Já que você está estudando isso, pesquise sobre Teoria de Ramsey.
Eu não sei em que tópico este problema se enquadra, por isso coloquei no
assunto a disciplina que tem relação com ele. Não consegui fazer:
"Existem (m-1)n + 1 pessoas na sala. Mostre que ou existem m pessoas que não
se conhecem mutuamente, ou existe uma pessoa que conhece pelo menos n
outras."
[]'s
David
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
