Página 1 de 1
POTI Combinatória
Enviado: 25 Jan 2024, 19:49
por renatinho14
Quarenta estudantes participaram de uma olimp´ıada de matem´atica. 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.
Re: POTI Combinatória
Enviado: 20 Fev 2024, 12:53
por Kakashi
Há estudantes com 3 ou mais problemas resolvidos
Suponha por absurdo que ninguém escreveu mais de 2 soluções na prova, logo há [tex3]40\cdot 2=80[/tex3]
ou menos problemas resolvidos corretamente na Olimpíada.
Como cada problemas foi resolvido por pelo menos [tex3]23[/tex3]
participantes, então há [tex3]23\cdot 5=105[/tex3]
ou mais soluções corretas na prova, o que contradiz nossa hipótese.
Escolhendo [tex3]2[/tex3] estudantes que satisfaçam o enunciado
Suponha que exista um estudante [tex3]A[/tex3]
que fez [tex3]3[/tex3]
problemas. Um dos problemas que ele não fez foram solucionados ao menos [tex3]23+23=46[/tex3]
vezes. Como há apenas [tex3]40[/tex3]
alunos, existe um estudante [tex3]B[/tex3]
que fez ambos.
Então cada problema foi resolvido por [tex3]A[/tex3]
ou [tex3]B[/tex3]
.
Os casos em que existe um estudante fez [tex3]4[/tex3]
ou [tex3]5[/tex3]
problemas são triviais.