Better Split Towers of Hanoi

Surpreendentemente, nossa solução de dividir (split) as torres gera muito mais movimentos que a solução de intercalar elas. 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

Você 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ós 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, você poderia dividir o par restante?