Proofs & Lower Bounds
📋 What it is
A lower bound proves that NO solution can be faster than a certain number of moves — so you know the true best.
🗣️ Coach says
Finding a fast solution is half the job; PROVING nothing’s faster is the other half. A lower-bound argument shows “every solution must take at least X moves” — so if your solution takes exactly X, it’s provably the best possible.
🧠 Memory hook
A lower bound says “you can’t beat X.” Match it and you’ve proven you’re optimal.
😂 Giggle
Why did the river-crossing puzzle need a plan?
Because you can't ferry everyone across at once!
😲 Whoa!
For Tower of Hanoi, mathematicians proved the lower bound equals 2^N − 1 exactly — so the obvious solution isn’t just good, it’s provably the fastest one that can ever exist.
✅ Quick check: Your solution takes 7 moves and the proven lower bound is 7. Can anyone ever do better?
Say your answer out loud first — then reveal.
No — the lower bound proves 7 is the minimum, so 7 moves is provably optimal; no faster solution exists.
A lower bound sets the floor; matching it proves optimality.
🧪 Try it! (2 minutes)
For a 3-disc Hanoi, argue WHY you must move the biggest disc at least once and the others more — feel the bound build.