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:
> 
> 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.
>
A minha solucao anterior estah errada (grande novidade...) mas ninguem deve
ter lido (grande novidade...). Fica como exercicio achar o erro, mas acho
que ninguem vai se dar ao trabalho (grande novidade...). Enfim, aqui vai a
solucao corrigida:

A observacao que resolve o problema eh a seguinte:
Se existirem mais de 3 avos, entao um deles eh avo de todos os alunos.
Dem:
Suponhamos que o aluno A tem os avos X e Y.
Se X e Y forem avos de todos os alunos, entao acabou.

Caso contrario, existirah um aluno B cujos avos sao, digamos, X e Z.

Cada aluno que eh neto de W, o quarto avo, deve ter o outro avo em comum com
A. Seja C um tal aluno.

Se o avo comum a A e C for Y, entao C e B nao terao nenhum avo em comum.
Logo, C deve ser neto de X.

Isso significa que nenhum aluno pode ser neto de Y e Z, pois um tal aluno
nao teria nenhum avo em comum com C, cujos avos sao X e W.

Conclusao: todos os alunos sao netos de X.
-----

Se existirem apenas 2 avos ou se existirem 4 ou mais avos, entao um destes
avos serah avo de todo mundo.

Suponhamos, portanto, que existem apenas 3 avos: X, Y e Z.
Entao, teremos apenas 3 tipos de aluno: XY, XZ e YZ (o significado dessa
notacao eh obvio). 
Chamemos de n(XY), n(XZ) e n(YZ) o numero de alunos de cada um dos 3 tipos e
suponhamos s.p.d.g. que n(XY) >= n(XZ) >= n(YZ).

Como n(XY) + n(XZ) + n(YZ) = 20, devemos ter n(YZ) <= 6, pois se n(YZ) >= 7,
entao n(XY) + n(XZ) + n(YZ) >= 21 > 20 ==> contradicao.

Isso quer dizer que n(XY) + n(XZ) = 20 - n(XY) >= 20 - 6 = 14.

Ou seja, existem pelo menos 14 alunos que sao netos de X.


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