As torres de Hanói
-Resolução-

    À primeira vista, não é claro que o jogo possa ter terminado. Contudo, se pensarmos durante alguns segundos, chegaremos à conclusão de que, de facto, tal acontece - embora possa ser impossível chegar ao fim do jogo durante a nossa vida (se o número de discos for suficientemente grande). Para isso, basta usar, de um modo bastante simples, o princípio de indução matemática. Em primeiro lugar, é claro que o jogo termina quando consideramos apenas um disco. Suponhamos agora, como hipótese de indução, que um jogo tem n discos - sendo n um número natural não nulo, escolhido arbitrariamente. Então, para terminar um jogo com n+1 discos, bastará seguir a estratégia seguinte:

    1. Transferir os n discos do topo da torre para uma haste diferente da original.

    2. Mudar o disco da base - o maior - para a haste que sobra e que, nesta altura, é a única que se encontra "vazia".

    3. Transferir a torre de n discos, construída no passo 1, para a haste onde se encontra o disco maior.

    O leitor deve notar que os passos 1 e 3 são possíveis pela hipótese de indução. Deste modo, pelo princípio de indução, o jogo tem solução qualquer que seja o número de discos considerado.

    Para resolver o problema proposto, designemos por an o número mínimo de movimentos para completar um jogo com n discos e comecemos por determinar a1, a2 e a3 - para depois tentarmos generalizar os argumentos usados. Ora, é claro que a1=1. Assim, consideremos um jogo com dois discos. Neste caso, pode convencer-se experimentalmente de que são necessários pelo menos 3 movimentos para reconstruir a torre numa das outras hastes.

    Se a torre for formada por 3 andares, pode convencer-se, também experimentalmente, de que são necessários pelo menos 7 movimentos para reconstruir a torre numa das outras hastes - repare que a estratégia seguida é precisamente a que indicámos acima.

    Assim, a2=3 e a3=7.

    Em geral, consideremos um jogo com n discos, em que n>2. Seguindo a estratégia que indicámos anteriormente, teremos terminado a partida depois de efectuarmos an-1 movimentos no passo 1, 1 movimento no passo 2 e de novo an-1 movimentos no passo 3. Finalmente, seguindo esta estratégia, efectuámos 2an-1+1 movimentos para completar o jogo e, portanto, por definição de an,

an<2an-1+1.

    Porque não a igualdade? Bom, ainda não justificámos que a estratégia seguida é a melhor. Para isso, notemos que, pelas condições impostas, o maior disco da torre só poderá ser numa haste vazia. E, obviamente, isto só será possível depois de termos completado o passo 1. Finalmente, o passo 3 terá de ser executado de qualquer maneira... Deste modo, exigindo que, nos passos 1 e 3, o número de movimentos seja o menor possível, também teremos efectuado o menor número de movimentos para completar o jogo. Deste modo,

an=2an-1+1.

    Podemos assim definir (de modo indirecto) a sucessão a1, a2, ..., an, ... dizendo que a1=1 e que an=2an-1+1 para qualquer número natural n>2. Por outras palavras, esta sucessão satisfaz a recorrência

xn=2xn-1+1,

para n>2, e está sujeita à condição inicial x1=1.
    O método de substituição de diante para trás permite-nos adivinhar o valor exacto de an - de uma maneira directa, sem recorrer a valores determinados anteriormente:

an=2an-1+1=2(2an-2+1)+1=2²an-2+2+1=
=2²(an-3+1)+2+1=2³an-3+2²+2+1=...
=2^n-1a1+2^n-2+...+2²+2+1=2^n-1+2^n-2+...+2²+2+1=
_n-1
= å 2^i
i=0

    Esta soma já nós conhecemos:

_n-1
             å 2ⁱ=2ⁿ-1.
ⁱ⁼⁰

    Assim, o termo geral da sucessão é

an=2ⁿ-1.

    A verificação rigorosa desta igualdade deve ser feita por indução e é deixada ao cuidado do leitor.