Re: [obm-l] PRINCÍPIO DAS CASAS DOS POMBOS!

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 30.04.04 20:56, jorgeluis@edu.unifor.br at jorgeluis@edu.unifor.br wrote:

> OK! Fellipe Rossi e demais colegas! Grato pela resolução enviada e
> aproveitando 
> a mensagem, vejam abaixo outro problema bastante interessante.
> 
> 
> Há 20 alunos na escola. Quaisquer dois deles têm um avô em comum. Prove que há
> 14 deles tais que todos têm um avô em comum.
> 
Tome o aluno A, cujos avos sao X e Y.

Cada um dos 19 alunos restantes eh neto de X ou de Y.
Logo, pelo menos 10 desses alunos devem ser netos de um deles, digamos X.
Isso dah 11 netos a X.

Se X tiver 14 ou mais netos, entao acabou.
Suponhamos, portanto, que X tenha no maximo 13 netos (incluindo A).
Vamos chama-los de A, B1, B2, ..., Br, onde 10 <= r <= 12.

Isso quer dizer que existem pelo menos 7 alunos que nao sao netos de X.
Logo, estes serao netos de Y.
Vamos chama-los de C1, C2, ..., Cs, onde s >= 7.

Consideremos B1 e C1. B1 eh neto de X e C1 eh neto de Y.
Logo, ambos devem ter o outro avo em comum.
Vamos chamar este avo de Z.

Cada Bi (i >= 2) eh neto de X e deve ter um avo em comum com C1.
Esse avo soh pode ser Z, pois o outro avo de C1 e Y e Y <> X.
Logo, cada Bi (i >= 1) eh neto de Z.
Analogamente, cada Cj (j>=1) tambem eh neto de Z.
Isso dah a Z pelo menos r + s >= 10 + 7 = 17 > 14 netos.
E acabou...

A proxima pergunta talvez seja:
Qual o numero maximo de avos que podem existir nestas condicoes?


[]s,
Claudio.


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