Better Split Towers of Hanoi

Surpreendentemente, a nossa solução de dividir (split) as torres gera muito mais movimentos que a solução de intercalá-las. Como os problemas são simétricos, isto não deveria acontecer.

Quantidade de discosIntercaladaSplit
5 pares 62 movimentos 88 movimentos
6 pares 126 movimentos 183 movimentos
7 pares 254 movimentos 374 movimentos

Consegue deixar o "split" tão eficiente quanto o intercalada?

A fonte de discrepância é uma decomposição ineficiente do problema. Satisfeitos com o fato dele simplesmente funcionar, não procuramos mais por uma solução melhor. Manter os discos da torre intercalada na ordem correta durante cada movimento é desnecessário. De fato, podemos evitar completamente mover a torre intercalada. Uma decomposição melhor do problema divide o par de discos em duas torres coloridas à medida em que eles são removidos da torre intercalada.


Se alguém puder dividir os (n-1) pares de discos previamente, poderia dividir o par restante?