Aproveitando a dica do Ponce, segue a solução (oficial) do problema.
Este problema, proposto pelo Prof. Andy Liu (Edmonton Canadá) para o Torneio
das Cidades, ano de 1994, foi o problema no. 04 da Prova Junior.
Problema
Existem 20 alunos em uma escola. Quaisquer dois deles possui um avô em comum.
Prove que pelo menos 14 deles possui um avô em comum.
Solução
A idéia é encontrar uma maneira de relacionar convenientemente os alunos com
seus respectivos avôs.
Cada aluno tem dois avôs: um materno, digamos A, e outro paterno, digamos B.
Chamamos de (A,B) um aluno que tem A e B como avôs.
Pelo enunciado do problema tem vários alunos do tipo (A,B).
Também pelo enunciado da questão, qualquer outro aluno pode ser pensado como um
par (X,Y), onde ou X = A ou Y = B.
Suponha que nem todas os alunos possuem um avô em comum.
Isto é, podemos supor que existe pelo menos um aluno tal que B não seja seu avô.
Na nossa notação, esse aluno é do tipo (A,C), com C distinto de B.
De maneira análoga, existe no mínimo um aluno que não tem A como avô.
Como, por hipótese esse aluno tem um avô em comum com um aluno do tipo (A,B) e
(A,C), ele tem de ser, necessariamente, do tipo (B,C).
Por outro lado, os 20 alunos possuem 40 avôs, contando os casos de
multiplicidade.
Pelo Princípio da Casa dos Pombos, no mínimo um dos avôs A, B e C é avô de no
mínimo 14 alunos.
De: [email protected] <mailto:[email protected]>
[mailto:[email protected]] Em nome de PONCE
Enviada em: domingo, 14 de abril de 2013 12:57
Para: [email protected] <mailto:[email protected]>
Assunto: Re: [obm-l] Torneio das Cidades 94
Amigos,
Não puder ler os últimos emails, devido a uma serie de trabalhos e aulas que
tenho diariamente.
Ainda hoje faço um esboço da prova que são 14.
O grande amigo Benedito, poderia ter deixado uma solução, pois este é um tipico
problema que ele
gosta muito e costuma postar na lista, geralmente com problemas de coloração.
U m abraço a todos.
Do amigo
PONCE
On Qui 11/04/13 18:38 , "Vanderlei *" <mailto:[email protected]>
[email protected] sent:
Se puder dar uma dica...
Em 11 de abril de 2013 18:00, PONCE <[email protected]
<mailto:[email protected]> > escreveu:
Jeferson,
O enunciado do problema sugere que voce pense no principio da casa dos pombos.
Com isto na cabeça a prova é relativamente simples.
Qualquer duvida, entre em contato que envio um esboço de uma prova.
PONCE.
On Qua 10/04/13 20:05 , Jeferson Almir <mailto:[email protected]>
[email protected] sent:
Existem 20 alunos em uma escola. Quaisquer dois deles possui um avó em comum.
Prove que pelo menos 14 deles possui um avó em comum.
estou tentando fazer por grafos .. alguma ajuda ou sugestão??
--
Esta mensagem foi verificada pelo sistema de antivrus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�s e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
