Olimpíadas ⇒ (POTI) Combinatória - Casa dos Pombos Tópico resolvido

[Deleted User 24633]

Quarenta estudantes participaram de uma olimpíada de matemática. A prova consistia de cinco problemas ao todo. Sabe-se que cada problema foi resolvido corretamente por pelo menos 23 participantes. Prove que deve existir dois participantes tais que todo problema foi resolvido por pelo menos um deles dois.

[Ittalo25]

4322.png (29.83 KiB) Exibido 625 vezes

Supondo o contrário, ou seja, que para qualquer par de estudantes existe pelo menos uma questão que eles não resolveram.

Dá para usar o método de contagem dupla. A tabela não importa muito, é só para didática.

Pares de X's em cada linha significam que os 2 estudantes não resolveram a questão da linha.

Dá para contar essa quantidade de pares de 2 jeitos:

Por linhas: Cada linha tem no máximo 17 X's, ou seja, a quantidade máxima de pares de X's em cada linha é [tex3]{17 \choose 2} [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]{17 \choose 2} [/tex3]

, dando um total máximo de [tex3]5\cdot {17 \choose 2}=680 [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]5\cdot {17 \choose 2}=680 [/tex3]

Por colunas: Cada par de estudantes errou pelo menos 1 questão, ou seja, contando por colunas a quantidade de pares de X's, o valor mínimo é: [tex3]{40 \choose 2 }=780 [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]{40 \choose 2 }=780 [/tex3]

Mas então o valor mínimo é maior que o valor máximo, contradição.