IME / ITA ⇒ (IME 1977/1978) Princípio de Dirichlet

[RonaldoJr]

Mostre que, em toda reunião constituída de seis pessoas, uma das hipóteses necessariamente ocorre (podendo ocorrer ambas):

[tex3]1)[/tex3] Existem três pessoas que se conhecem mutuamente (isto é, das três cada duas se conhecem ).

[tex3]2)[/tex3] Existem três pessoas que se desconhecem mutuamente(isto é, três cada duas se conhecem).

Vamos ai galera!

Acho que testar todos os casos meio complicado(não consegui msm), já ouvi falar de uma solução tipo por contradição, tentar "fugir" dessas duas hipoteses e chegar meio que ao "absurdo" , de qlqr forma obrigatoriamente ocorre uma delas, tentei fazer assim não saiu tbm = /...
Se alguem souber, MUITO OBRIGADO!

[Auto Excluído (ID:276)]

Você tem que provar que dado um grupo de 6 pessoas ocorre (1) ou (2) . Usarei a lógica matemática , onde (1) riscado é a negativa de (1) .
Temos que provar que
[tex3]\not{(1)} \, \rightarrow (2)[/tex3] [tex3]\,\,\,\,\,\,[/tex3] Se (1) não ocorrer, então (2) ocorre
e
[tex3]\not{(2)} \, \rightarrow (1)[/tex3] [tex3]\,\,\,\,\,\,[/tex3] Se (2) não ocorrer, então (1) ocorre

Da contrução das hipóteses:

[tex3]\not{(1)} \, \leftrightarrow \mbox{Todos se desconhecem}[/tex3]
[tex3]\not{(2)} \, \leftrightarrow \mbox{Todos se conhecem}[/tex3]

Veja:

Não existem três pessoas que se conhecem mutuamente = Todos se desconhecem
Não existem três pessoas que se desconhecem mutuamente = Todos se conhecem

E além disso

Se todos se desconhecem, então existem três pessoas que se desconhecem mutuamente :

[tex3]\mbox{Todos se desconhecem} \rightarrow (2)[/tex3]

Da mesma forma

Se todos se conhecem, então existem três pessoas que se conhecem mutuamente :

[tex3]\mbox{Todos se conhecem} \rightarrow (1)[/tex3]

Ou seja,

[tex3]\not{(1)} \, \rightarrow \mbox{Todos se desconhecem} \rightarrow (2)[/tex3]

Logo [tex3]\not{(1)} \, \rightarrow (2)[/tex3]

e [tex3]\not{(2)} \, \rightarrow \mbox{Todos se conhecem} \rightarrow (1)[/tex3]

então [tex3]\not{(2)} \, \rightarrow (1)[/tex3]

Como queriamos provar.
Então, necessariamente uma das duas ocorre. Bom, eu não sei se está certo, mas eu a faria desse jeito!

[RonaldoJr]

O fato de ser uma "reunião" não "adiciona" nenhuma condicionante, certo?
Achei meio estranho isso no começo... rsrs

[Auto Excluído (ID:276)]

Claro que não. Muito menos o número de pessoas e quantas ele quiser pegar. Poderia dize a cada 4 , a cada 5 etc. .

[Tassandro]

RonaldoJr,
pedro123,
Usei o Princípio da Casa dos Pombos para essa.
Sejam as pessoas [tex3]P_1,P_2,P_3,P_4,P_5,P_6[/tex3]. Imagine que cada uma delas são vértices de um hexágono. Adote a seguinte convenção: se duas pessoas se conhecem, o segmento que as une é azul, se não, é vermelho.
Note que de cada vértice (pessoa) partem 5 segmentos. Como temos apenas duas opções de cores, pelo PCP, há, no mínimo, 3 segmentos da mesma cor. SPG, suponha que vamos escolher três segmentos da mesma cor partindo da pessoa 1, isto é, vamos admitir que [tex3]P_1[/tex3] conhece [tex3]P_2,P_4[/tex3] e [tex3]P_5[/tex3].
Se [tex3]P_2[/tex3] conhece [tex3]P_5,[/tex3] a demonstração acaba, pois teríamos um triângulo de 3 lados azuis.
Se não, temos:
Caso [tex3]P_4[/tex3] conheça [tex3]P_5,[/tex3], a demonstração também acaba, pelo mesmo motivo de antes.
Se [tex3]P_4[/tex3] não conhecer [tex3]P_5,[/tex3] ou [tex3]P_5[/tex3] conhece [tex3]P_2[/tex3], então a dem. acaba, pois três pessoas se conhecem mutuamente, ou [tex3]P_5[/tex3] não conhece [tex3]P_2,[/tex3] e dem. também acaba, porque nesse caso três pessoas não se conhecem mutuamente.
Abraço.