Puzzles
Optimization & Minimum Steps
These puzzles ask you to find the best possible plan, not just any plan that works. The core skill is proving a lower bound, showing your answer isn't just good but provably optimal, the same kind of thinking that algorithm design and complexity analysis rely on.
1. The Bridge and Torch
Four people must cross a bridge at night, sharing a single torch that can light the way for at most two people at a time. No one may cross without the torch, and a pair crossing together always moves at the slower person's pace. The four take 1, 2, 5, and 10 minutes to cross alone.
Rules
- The torch is required for every crossing
- At most two people cross together
- A pair moves at the slower speed
Your task — Get everyone across in 17 minutes, the fastest time possible.
Difficulty — Medium
Hint 1 — Fastest pair isn't always best.
Hint 2 — Someone must carry the torch back.
Hint 3 — Let the fastest ferry it twice.
Main idea — Pairing the two slowest people together, and using the fastest person as a repeated ferry, avoids wasting the slow walkers' time twice.
Solution
- The 1 and 2 minute people cross together (2 minutes).
- The 1 minute person returns with the torch (1 minute).
- The 5 and 10 minute people cross together (10 minutes).
- The 2 minute person returns with the torch (2 minutes).
- The 1 and 2 minute people cross together again (2 minutes).
Reasoning
The two slowest people must cross together at some point, since any other pairing forces the 10-minute crosser to walk twice.
Using the fastest person to repeatedly ferry the torch back keeps every return trip as cheap as possible. Adding the times, 2 plus 1 plus 10 plus 2 plus 2, gives exactly 17 minutes, the proven minimum for this puzzle.
2. 100 Floors and Two Eggs
You have 2 identical eggs and a 100-floor building. Each egg breaks if dropped from at or above a certain critical floor, and survives if dropped below it. A broken egg cannot be reused.
Rules
- Eggs break identically above the threshold
- A broken egg is gone for good
- Only 2 eggs are available
Your task — Find the minimum number of drops needed, in the worst case, to determine the critical floor.
Difficulty — Hard
Hint 1 — Balance drops used against floors covered.
Hint 2 — Shrink the gap after each break.
Hint 3 — Try starting gaps of 14, 13, 12.
Main idea — Shrinking the gap between drops by one each time balances the cost of an early break against the cost of a late one, so the worst case never exceeds the same fixed number of drops.
Solution
- Drop the first egg from floor 14.
- If it survives, drop it next from floor 14 plus 13, then plus 12, shrinking the gap by one each time.
- The moment the first egg breaks, switch to the second egg and test the remaining floors one at a time upward from the last safe floor.
- This strategy always finds the critical floor within 14 drops.
Reasoning
Every drop either breaks the egg, forcing a one-by-one search with the second egg, or survives, letting the first egg jump further ahead.
Starting the gaps at 14 and shrinking by one each time ensures that a break at any point still leaves exactly enough remaining drops to finish the linear search, since 14 plus 13 plus all the way down to 1 adds up to 105, comfortably covering all 100 floors while keeping the worst case fixed at 14 drops.
3. Minimum Cuts: Cake into 8 Pieces
You have one cake and want to cut it into exactly 8 equal pieces using only straight cuts. You are allowed to stack pieces on top of each other before making another cut.
Rules
- Only straight cuts are allowed
- Pieces may be stacked before cutting
- All 8 final pieces must be equal
Your task — Find the minimum number of straight cuts needed to produce 8 equal pieces.
Difficulty — Easy
Hint 1 — Stack pieces before the next cut.
Hint 2 — One cut can slice many layers.
Hint 3 — Try doubling the pieces each time.
Main idea — Stacking the pieces before each new cut lets a single straight cut pass through every piece at once, doubling the total instead of only adding one.
Solution
- Make one cut through the whole cake, producing 2 pieces.
- Stack the 2 pieces and cut through both at once, producing 4 pieces.
- Stack all 4 pieces and cut through them at once, producing 8 pieces.
Reasoning
Without stacking, each cut adds at most one new piece, so reaching 8 pieces would take 7 cuts.
Stacking lets one cut pass through multiple layers simultaneously, doubling the piece count with every cut, so three cuts, 2 then 4 then 8, reach the target in the fewest cuts possible.
4. 25 Horses: Find the Fastest 3
You have 25 horses and a track that can race only 5 horses at a time. There is no stopwatch, so each race reveals only the finishing order within that group, never exact times.
Rules
- Only 5 horses race at once
- Each race gives order, not times
- You need the fastest 3, in order
Your task — Find the minimum number of races needed to determine the fastest 3 horses overall, in the correct order.
Difficulty — Hard
Hint 1 — Race groups, then race winners.
Hint 2 — Some horses can be eliminated early.
Hint 3 — One careful final race decides it.
Main idea — Racing the group winners against each other, then applying transitive elimination, narrows the field to a small handful of horses that a single final race can fully resolve.
Solution
- Split the 25 horses into 5 groups of 5, and race each group (5 races).
- Race the 5 group winners against each other (a 6th race).
- Use the results to eliminate any horse that two others have already beaten, narrowing the field to a small set of candidates for 2nd and 3rd place overall.
- Race that final small group to fix the exact order of the fastest 3 (a 7th race).
Reasoning
The first five races establish a strict order within each group, so any horse beaten by two others already known to be outside the top 3 can be dropped immediately.
The race among the winners ranks the single fastest horse from each group and shows which groups could still contribute more than one horse to the overall top 3. Applying this transitive reasoning narrows the remaining candidates enough that one more race is always sufficient, for a minimum of 7 races total.
5. Minimum Number of Weighings
You have N identical-looking coins. Exactly one is counterfeit and is either heavier or lighter than the rest, though you don't know which. You have a balance scale with two pans and no weights.
Rules
- Each weighing gives 3 outcomes
- Exactly one coin is counterfeit
- Heavier or lighter is unknown
Your task — Express the minimum number of weighings needed in terms of N, then check the formula for N equal to 12.
Difficulty — Hard
Hint 1 — Each weighing splits into three.
Hint 2 — Count every possibility to distinguish.
Hint 3 — Compare that count to powers of three.
Main idea — Since every weighing only ever produces one of three outcomes, the minimum number of weighings is set by how many times three must be multiplied to cover every coin and every direction it could be off.
Solution
- There are 2 times N possible answers: each of the N coins could be counterfeit, in either the heavier or lighter direction.
- W weighings can distinguish at most 3 to the power of W outcomes.
- The minimum W is the smallest whole number where 3 to the power of W is at least 2N.
- For N equal to 12, 2N is 24, and 3 cubed is 27, the smallest power of three at least 24, so W equals 3.
Reasoning
Each weighing is a three-way experiment, so after W weighings, at most 3 to the power of W distinct outcomes can be told apart.
Since there are 2N possible locations and directions for the counterfeit coin, W must be large enough for 3 to the power of W to cover all of them, giving the formula W equal to the smallest whole number satisfying that inequality. Checking N equal to 12 confirms that 3 weighings, the well known answer to the classic 12-coin puzzle, is the true information-theoretic minimum, not just a clever trick.
6. Jug Problem: Measure Exact Amount
You have a 3-liter jug and a 5-liter jug, neither with any markings, and an unlimited water supply. You need to measure out exactly 4 liters.
Rules
- Jugs have no measurement markings
- You may fill, empty, or pour between them
- Only these two jug sizes exist
Your task — Find a sequence of fills, empties, and pours that leaves exactly 4 liters in one jug.
Difficulty — Medium
Hint 1 — Fill the larger jug first.
Hint 2 — Use the small jug to remove some.
Hint 3 — Repeat the transfer one more time.
Main idea — Repeatedly filling the small jug from the large one and emptying it lets you subtract in steps of 3 from 5, and one more careful transfer lands exactly on 4.
Solution
- Fill the 5-liter jug completely.
- Pour from the 5-liter jug into the 3-liter jug until full, leaving 2 liters in the 5-liter jug.
- Empty the 3-liter jug, then pour the remaining 2 liters into it.
- Fill the 5-liter jug again, then pour into the 3-liter jug, which already holds 2 liters, until it's full. This uses only 1 more liter, leaving exactly 4 liters in the 5-liter jug.
Reasoning
Because 3 and 5 share no common factor besides 1, transferring water back and forth between them can reach every whole number of liters from 0 to 5, including 4.
Tracking exactly how much is left in the 5-liter jug after topping off a partially filled 3-liter jug shows that only 1 more liter is needed to fill it, leaving precisely 4 liters behind.
7. Minimum Moves: Prisoners Crossing
2 guards and 2 prisoners must cross a river using one boat that holds at most 2 people and needs at least one person aboard to row it. On any bank where a guard is present, prisoners must never outnumber the guards there.
Rules
- The boat holds at most 2 people
- At least one person must row it
- Prisoners can't outnumber guards present
Your task — Find the minimum number of crossings needed to get everyone safely across.
Difficulty — Medium
Hint 1 — Send both prisoners across first.
Hint 2 — Carefully choose who brings it back.
Hint 3 — Balance who travels on each trip.
Main idea — Choosing who returns the boat at each step keeps prisoners from ever outnumbering guards on a bank where guards remain, without wasting a single crossing.
Solution
- Both prisoners cross to the far bank.
- One prisoner returns.
- Both guards cross to the far bank.
- One guard returns.
- The returning guard and the remaining prisoner cross together, finishing in 5 crossings.
Reasoning
At every stage of this sequence, prisoners are only left alone on a bank once no guards remain there to be outnumbered, so the safety rule is never broken.
Five crossings move all four people across using the boat's two-person capacity as efficiently as possible, and no shorter sequence can satisfy the safety constraint at every step.
8. Coin Problem: Minimum Number of Coins
Using US coin denominations of 1, 5, 10, and 25 cents, you need to make exactly 63 cents using as few coins as possible.
Rules
- Denominations available: 1, 5, 10, 25
- Any number of each coin is allowed
- The total must equal exactly 63 cents
Your task — Find the minimum number of coins needed to make 63 cents, and explain why always picking the largest coin first works here.
Difficulty — Easy
Hint 1 — Try the largest coins first.
Hint 2 — Check what remains after each pick.
Hint 3 — This shortcut isn't always safe.
Main idea — Greedily taking the largest coin that still fits happens to give the true minimum for these particular denominations, though the same shortcut can fail for other denomination sets.
Solution
- Take two 25-cent coins, using 50 cents, leaving 13 cents.
- Take one 10-cent coin, using 10 cents, leaving 3 cents.
- Take three 1-cent coins to cover the remaining 3 cents.
- Total coins used: 2 plus 1 plus 3, which is 6 coins.
Reasoning
This greedy approach works for US denominations because each coin value fits cleanly enough into the next that no alternative combination ever needs fewer coins.
This is exactly the coin-change problem from computer science: greedy selection is only guaranteed to work for well-behaved denomination systems, and general cases need every combination checked, typically with dynamic programming, to guarantee the true minimum.