Principio da Casa dos Pombos

por Perceval Sex 02 Abr 2021, 18:42

(Olimpíada Russa 1997) Uma sala de aula possui 33 alunos. Cada aluno tem uma música e um cantor favorito. Certo dia, cada um deles perguntou aos demais suas músicas e cantores favoritos. Em seguida, cada um falou dois números, o primeiro era a quantidades de alunos que gostavam da mesma música e o segundo, a quantidade de alunos que tinham o mesmo cantor favorito. Sabe-se que cada um dos números de 0 a 10 apareceu entre as respostas. Mostre que existem dois alunos que gostam do mesmo cantor e da mesma música.

por JaquesFranco Seg 27 Set 2021, 14:54

Seja A_{1}, A_{2}, ..., A_{33} os alunos desta classe.

Note que cada A_{n} disse dois números X e Y, para representar a quantidade de alunos que gostavam da mesma música, e para a quantidade de alunos que tinham o mesmo cantor favorito, respectivamente. E no total temos 33 * 2 = 66 números falados.

Mas nos foi dado, que todos os números de 0 a 10 apareceram entre os números falados, agora observe:
. Se um aluno fala X = 10, ou Y = 10. Devemos ter outros 10 alunos que também falaram 10, já que todos eles gostam do mesmo cantor ou da mesma música, logo temos, pelo menos, 11 alunos que falaram X = 10 ou Y = 10.
. Se um aluno fala X = 9, ou Y = 9. Devemos ter outros 9 alunos que também falaram 9 já que todos eles gostam do mesmo cantor ou da mesma música, logo temos, pelo menos, 10 alunos que falaram X = 9 ou Y = 9.
.
.
.
.
. Se um aluno fala X = 1, ou Y = 1. Devemos ter outro aluno que também falou 1, já que ambos gostam do mesmo cantor ou da mesma música, logo temos, pelo menos, 2 alunos que falaram X = 1 ou Y = 1
. Se um aluno fala X = 0, ou Y = 0. Somente ele gosta de um cantor ou de uma música, logo temos, pelo menos, 1 aluno que fala X = 0, Y = 0.

Portanto, contando a quantidade de números falados acima, temos 1 + 2 + 3... 11 = 66 números, que é exatamente a quantidade total de números falados. Logo existe somente 1 cantor, ou música que é escolhido por 11 alunos, somente 1 cantor, ou música que é escolhido por 10 alunos, ...., somente 1 cantor, ou música que é escolhido por somente um aluno.

Portanto no total, temos 1 * 11 = 11 músicas e cantores escolhidos pelos alunos.

Basta agora, dividir em casos:
. Se temos 1 cantor e 10 músicas:
Todos os alunos gostam do mesmo cantor, e como só existem 10 músicas e 33 alunos, o PCP nos garante que teremos pelo menos 3 pessoas gostando da mesma música.

. Se temos 2 cantores e 9 músicas:
Pelo PCP teremos pelos 17 alunos gostando do mesmo cantor, e dentre esses 17 alunos, o PCP nos garante que teremos pelo menos 2 deles gostando da mesma música.

. Se temos 3 cantores e 8 músicas:
Pelo PCP teremos pelos 11 alunos gostando do mesmo cantor, e dentre esses 11 alunos, o PCP nos garante que teremos pelo menos 2 deles gostando da mesma música.

. Se temos 4 cantores e 7 músicas:
Pelo PCP teremos pelos 9 alunos gostando do mesmo cantor, e dentre esses 9 alunos, o PCP nos garante que teremos pelo menos 2 deles gostando da mesma música.

. Se temos 5 cantores e 6 músicas:
Pelo PCP teremos pelo menos 7 alunos gostando do mesmo cantor, e dentre esses 7 alunos, o PCP nos garante que teremos pelo menos 2 deles gostando da mesma música

Os próximos casos são simétricos.
Logo, temos pelo menos dois alunos gostando da mesma música e do mesmo cantor.

Principio da Casa dos Pombos

Principio da Casa dos Pombos

Re: Principio da Casa dos Pombos

Um fórum livre e democrático.