Versao relampago:
casa-dos-pombos, 68,68,68,69,69,69,70,70,70,...,100,100,100,101,101,101,
contradicao.
Versao explicada:
Ha 101-67=34 numeros entre 68 e 101 (que sao os possiveis numeros de
amigos) de cada fulano.
Seja xi o numero de estudantes com i amigos (onde i=68,69,...,101). Note
que sao 34 numeros xi, cuja soma eh 102. Queremos provar que algum deles eh
maior ou igual a 4, certo?
Entao suponha por contradicao que todos eles sao menores ou iguais a 3.
Entao a soma eh no maximo 34x3=102, o que soh serah atingido se TODOS forem
iguais a 3. Entao chegamos aa conclusao de que o unico jeito do nosso
teorema furar seria se houvesse 3 alunos com 68 amigos, outros 3 com 69
amigos, e assim por diante, e 3 com 101 amigos, exatamente.
Agora seja yk o numero de amigos do fulano k (k=1,2,3,...,102) -- ou seja,
a lista dos numeros yk seria aquela lista lah em cima. A soma dos yk tem
que ser par (afinal, quando voce soma os yk's, voce estah contando o
"numero de amizades", soh que em dobro, porque cada amizade eh contada duas
vezes -- estamos fazendo a hipotese aqui de que, se A eh amigo de B, entao
B eh amigo de A). Como 68+68+68+69+69+69+...+101+101+101 = 17x169 eh impar,
esta nao eh uma configuracao possivel. Acabou.
Abraco,
Ralph
2012/6/5 Mauricio de Araujo <[email protected]>
> Amigos, gostaria de uma luz para fazer o problema abaixo:
>
> Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove
> que existem quatro
> estudantes com o mesmo n´umero de amigos.
>
> --
> --
> Abraços
> oɾnɐɹɐ ǝp oıɔıɹnɐɯ
> *momentos excepcionais pedem ações excepcionais*
>
>
