Optimality & Move-Counting
📋 What it is
The optimal solution uses the fewest possible moves; counting moves lets you prove you can’t do better.
🗣️ Coach says
Getting an answer is good; getting the SHORTEST answer is the real puzzle. For Hanoi that’s 2^N − 1 moves, and you can prove no solution is shorter. Knowing the minimum tells you when to stop looking for a better path.
🧠 Memory hook
Optimal = fewest moves. If you match the known minimum, you’re done improving.
😂 Giggle
Why did the brainteaser go to the gym?
To get mentally stronger!
😲 Whoa!
Computer scientists prove “lower bounds” — the fewest moves ANY solution could possibly use — so they know when an algorithm is truly the best possible, not just the best they’ve found.
✅ Quick check: You solve a 3-disc tower in 9 moves. Is that optimal?
Say your answer out loud first — then reveal.
No — the optimal is 7 (2³ − 1), so 9 has two wasted moves; you can do better.
Any count above the proven minimum means the solution isn’t optimal.
🧪 Try it! (2 minutes)
Solve a 3-disc tower twice and try to shave off any wasted move until you hit exactly 7.