Problema
(Indicado a partir do 7º ano do E. F.)
Em uma competição de queda de braço, cada competidor que perde duas vezes é eliminado. Isso significa que um competidor pode perder uma disputa (uma “luta”) e ainda assim ser campeão.
Em um torneio com [tex]100[/tex] competidores, qual é o número máximo de “lutas” que serão disputadas, até se chegar ao campeão?
Solução
Observamos facilmente que
- em cada disputa temos um vencedor e um perdedor, não há empates,
- e para que haja um vencedor do torneio, todos os outros competidores devem ter perdido exatamente duas vezes.
Assim, podemos contar o total de partidas do torneio pelo número de derrotas.
Para tanto, veja que
- o campeão do torneio ou não foi derrotado ou teve apenas uma derrota
- e os demais [tex]99[/tex] competidores foram eliminados com duas derrotas cada.
Dessa forma, temos duas possibilidades:
-
[tex]\textcolor{#800000}{(1)}[/tex] O campeão não teve derrotas e, neste caso, o número de lutas do torneio foi [tex] \boxed{2 \times 99 = 198} \, .[/tex]
[tex]\textcolor{#800000}{(2)}[/tex] O campeão teve uma derrota e, neste caso, o número de lutas do torneio foi [tex] \boxed{2 \times 99 +1= 199} \, .[/tex]
Até aqui, podemos concluir que o número máximo não é maior do que [tex]199 \, .[/tex]
Vamos, agora, assegurar que é possível que o campeonato se encerre com [tex]199[/tex] lutas.
Observe que, como cada competidor perde pelo menos uma luta, podemos ter uma primeira rodada assim:
[tex] \underbrace{ \boxed{c_1\text{ vence }c_2} \, ; \, \boxed{c_2\text{ vence }c_3} \, ; \, \boxed{c_3\text{ vence }c_4} \, ; \, \cdots \, ; \boxed{c_{99}\text{ vence }c_{100}} \, ; \, \boxed{c_{100}\text{ vence }c_1}}_{\textcolor{red}{\text{100 partidas}}}[/tex]
Após essa primeira rodada, temos [tex]100[/tex] lutas e cada competidor tem exatamente uma derrota.
Suponhamos, sem perda de generalidade, que o competidor [tex]c_1[/tex] seja o campeão. Como ele já perdeu uma luta na primeira rodada, ele deverá vencer as demais lutas que participar. Mais do que isso, os demais competidores devem ter a sua segunda derrota.
Assim, nas rodadas seguintes, teríamos [tex]99[/tex] partidas nas quais [tex]c_1[/tex] vence e sagra-se campeão.
[tex] \underbrace{ \boxed{c_1\text{ vence }c_2} \, ; \, \boxed{c_1\text{ vence }c_3} \, ; \, \boxed{c_1\text{ vence }c_4} \, ; \, \cdots \, ; \, \boxed{c_1\text{ vence }c_{99}} \, ; \, \boxed{c_1\text{ vence }c_{100}}}_{\textcolor{red}{\text{99 partidas}}}[/tex]
Neste caso, o torneio foi finalizado com, exatamente, [tex]\fcolorbox{black}{#eee0e5}{$100 + 99 = 199$} \, [/tex] disputas.
Solução elaborada pelos Moderadores do Blog.