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.

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 182 |

5 | awoo | 180 |

6 | tourist | 176 |

6 | sus | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

9 | -is-this-fft- | 170 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2021 22:31:39 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

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.

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

N = 1N = 2N = 3Sierpiński_triangleYet 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.