Minha ideia era algo como uma indução: provar que só existem três avós (ou menos). Com quatro fica fácil, e a partir daí, vemos que somos obrigados a repetir as avós já usadas.
Em 28 de abril de 2013 06:07, Rogerio Ponce <[email protected]> escreveu: > Ola' pessoal, > achei conveniente explicar melhor a solucao... > > Problema: > Existem 20 alunos em uma escola. > Quaisquer dois deles possui uma avo' em comum. > Prove que pelo menos 14 deles possui uma avo' em comum. > > Solucao: > Seja Antonio um dos 20 alunos. > Sejam Maria e Nair suas avos. > Portanto, qualquer outro aluno tem uma avo' Maria, ou Nair, ou Maria e > Nair simultaneamente. > > Assim, podemos encaixar cada aluno em um dos grupos A, B e C, definidos > da seguinte forma: > - grupo A: o aluno tem uma avo' Maria, e uma avo' Nair. > - grupo B: o aluno tem uma avo' Maria, e uma outra avo' que nao e' Nair. > - grupo C: o aluno tem uma avo' Nair, e uma outra avo' que nao e' Maria. > > Dessa forma, Antonio pertence ao grupo A, e existem 4 possibilidades: > 1) os grupos B e C sao vazios: > neste caso, tanto Maria quanto Nair sao avos dos 20 alunos. > > 2) apenas o grupo C e' vazio: > neste caso, Maria e' avo' dos 20 alunos. > > 3) apenas o grupo B e' vazio: > neste caso, Nair e' avo' dos 20 alunos. > > 4) nenhum grupo e' vazio: > neste caso, seja Bernardo um aluno do grupo B, e seja Odete a sua outra > avo' ( aquela que nao e' Nair). > Acontece que qualquer que seja o aluno "c" do grupo C, "c" e Bernardo > possuem uma avo' em comum. > Como uma avo' de "c" e' Nair, a outra, aquela que nao pode ser Maria, tem > que ser Odete. > Portanto, todos os alunos do grupo C sao netos de Odete. > > Agora, seja Camilo um aluno do grupo C. > Entao, conforme acabamos de provar, Camilo tem as avos Nair e Odete. > Acontece que qualquer que seja o aluno "b" do grupo B, "b" e Camilo > possuem uma avo' em comum. > Como uma avo' de "b" e' Maria, a outra, aquela que nao pode ser Nair, tem > que ser Odete. > Portanto todos os alunos do grupo B sao netos de Odete. > > Desse modo, apenas 3 mulheres - Maria, Nair e Odete - sao as unicas avos > de todos os alunos. > Como os 20 alunos possuem ao todo 40 avos, uma das 3 mulheres tem que ser > avo' pelo menos 14 vezes, ou seja, tem que ser avo' de pelo menos 14 alunos > (principio das casas de pombos). > > Assim, examinadas as possibilidades, sempre podemos afirmar que pelo menos > 14 alunos possuem uma avo' em comum. > > []'s > Rogerio Ponce > > -- /**************************************/ 神が祝福 Torres
