Блог пользователя Real_Father_Of_Ash

Is minimum-moves solution to Towers of Hanoi for 3 towers and N disks unique?

Автор Real_Father_Of_Ash, 3 года назад, По-английски

As stated by title, I want to know if there's any formal proof for solution with minimum steps to solve Towers of Hanoi being unique or non-unique.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

Using the fact that for n=1 there's a unique configuration with 1 move, you can prove your claim by induction. At step n, move in its unique way the $$$(n-1)$$$ pile from left to mid then using 1 move take the biggest disk from left to right then uniquely move the $$$(n-1)$$$ pile from mid to right. I guess this will work

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I feel like the inductive step is not correct — it should start with "Assume we have a unique way to move a tower of size n-1 from one pole to another," but then also you have to show that the strategy of 1) move n-1 A->B 2) move bottom A->C 3) move n-1 B->C is the only way to get optimal number of moves. Once you do that, then what you said will show that steps 1, 2 and 3 form a unique solution, but maybe not immediately clear that you have to solve it exactly like that

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can formalize my argument as much as you want I didn’t even try to make it formal I was just giving an intuitive idea for someone who wants to write it formally. However, the strategy of the recursive algorithm is the only strategy to get an answer not just the optimal one (unless for the case n=1) and so uniqueness of each step implies uniqueness of the whole procedure by product rule.

      → Ответить
»
3 года назад, # |
← Rev. 4   Проголосовать: нравится +24 Проголосовать: не нравится

If you draw the graph of transistion under Sierpiński triangle shape then according to wikipedia, you can have these graphs:

N = 1
N = 2
N = 3
Sierpiński_triangle

Yet you can build the graph recursively to enlarge it, meanwhile the graph only have 3 bridges that you can pass through. But since the minimal steps from this peg is full to fullfill the other is a straight path of size $$$2^n - 1$$$, then you only have $$$2$$$ unique paths to do that.

Since for the tower of Hanoi puzzle. Both peg $$$2$$$ and $$$3$$$ are initialy empty hence it is symmetrical. Therefore you can also claim that there is only one unique way to do.

→ Ответить