T03 Hanoi4
Considere o problema das torres de Hanoi com 4 torres. Neste problema, Hanoi4(\(N\)), temos $N$ discos, a saber, discos $1,\dots,N$, e $4$ torres em vez de $3$. A regra que seguimos é a mesma: um disco maior não pode ficar sobre um disco menor. A menos dessa regra, o disco no topo de uma torre pode ser movido para o topo de qualquer outra torre. Vamos indexar as torres com os inteiros \(p\) com $0\leq p < 4$. Inicialmente, temos os $N$ discos na torre $0$. O objetivo é passar todos esses $N$ discos para a torre $1$, com um número pequeno de movimentos.
Exemplo. Suponha $N=3$. A seguinte solução faz $5$ movimentos:
Configuração inicial:
0: 3 2 1
1:
2:
3:
Movimento: 1 3
0: 3 2
1:
2:
3: 1
Movimento: 2 2
0: 3
1:
2: 2
3: 1
Movimento: 3 1
0:
1: 3
2: 2
3: 1
Movimento: 2 1
0:
1: 3 2
2:
3: 1
Movimento: 1 1
0:
1: 3 2 1
2:
3:
Acima, por exemplo, o movimento "1 3" significa mover o disco $1$ (que está na torre $0$) para a torre $3$.
Seja $U_N$ o número mínimo de movimentos para resolver Hanoi4($N$).
(i) Prove que, para todo $n\geq1$,
\(
U_{\binom{n+1}2}\leq2U_{n\choose2}+T_n,
\)
onde $T_n$ é o número mínimo de movimentos para resolver o problema original das torres de Hanoi com $3$ torres e $n$ discos. Assim, $T_n=2^n-1$.
(ii) Prove que, para todo $n\geq1$,
\(
U_{n+1\choose2}\leq(n-1)2^n+1.
\)
(iii) Suponha que temos $55$ discos e apenas 3 torres (isto é, o problema de Hanoi original). Seja $T$ o número de movimentos necessários nesse caso. Quantos dígitos na base $10$ tem o número $T$? Calcule a estimativa superior para $U_{55}$ em (ii) acima.