Torneio de Boxe

Um torneio eliminatório de  boxe  foi organizada. Temos 114 participantes e por isso temos 57 partidas na primeira rodada do torneio. Na segunda rodada, os 57 lutadores restantes foram emparelhado, resultando em 28 jogos, um lutador ganhou por WO (isto é, não tem que lutar nessa rodada). Os 29 lutadores restantes foram então emparelhado, e assim por diante.

(a) Quantos jogos ao todo foram necessários para determinar um vencedor do torneio?

(b) Quantos jogos seria necessário se n pessoas participaram no torneio (onde n representa um inteiro fixo, mas não especificado número)?

Vamos definir uma função F(n) que devolve o número de lutas necessárias para descobrir o vencedor do torneio com n participantes:

F(n) : número de lutas necessárias para descobrir o vencedor do torneio com n participantes.

Observe que quando o n é par então podemos realizar n/2 lutas e restaram n/2 lutadores. Quando n é impar, então podemos realizar n/2 lutas e restaram n/2 + 1 lutadores. Logo, podemos obter a seguinte recursão:

$$F(1) = 0$$
$$F(n) =
\begin{cases}
F(\frac{n}{2}) + \frac{n}{2} & \mbox{se n é par}\\
F(\frac{n}{2}+1) + \frac{n}{2} & \mbox{se n é ímpar}\\
\end{cases}
$$

Testando alguns casos da recursão acima, podemos notar que F(n) = n-1, uma vez que, cada luta elimina um lutador e precisamos eliminar n-1 lutadores para encontrar o vencedor do torneio.

Podemos provar este fato resolvendo a recorrência acima:

Suponha n = $2^k$. Logo, podemos escrever a recorrência da seguinte maneira: $$F(2^0) = 0$$
$$F(2^k) = F(2^{k-1}) + 2^{k-1}$$
Utilizando o método da substituição: $$ F(2^k) = F(2^{k-1}) + 2^{k-1} \\ F(2^{k-1}) = F(2^{k-2}) + 2^{k-2} \\ F(2^{k-2}) = F(2^{k-3}) + 2^{k-3} \\ \vdots \\ F(2^{1}) = F(2^{0}) + 2^{0} \\ $$ Somando tudo temos: $$ F(2^k) = F(2^{0}) + 2^{0} + 2^{1} + 2^{2} + \ldots + 2^{k-1} \\ F(2^k) = 2^{k} - 1\\ $$ Desfazendo a substituição, temos: $$ F(n) = n - 1\\ $$