on 30.04.04 20:56, [EMAIL PROTECTED] at [EMAIL PROTECTED] 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 =========================================================================
