Re: [obm-l] Problema - Matemática Discreta

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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
=========================================================================