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