Strategy OptimizationDifficulty 69 questionsby Marco DeLuca
Puzzles where you must find the optimal strategy — the approach that minimizes time, steps, or risk. Brute force won't cut it; you need to think about what the best possible move looks like.
Instructions
For each problem, describe the optimal strategy and explain why it's better than the alternatives. Just giving the answer earns partial credit — showing why your approach is optimal earns full credit.
Question 1 of 9
You have two buckets — one holds 3 liters and the other holds 8 liters. You need exactly 5 liters of water, and there is unlimited water available. What is the shortest method?
A farmer needs to move a wolf, a goat, and a cabbage across a river. His boat can carry only himself and one item at a time. If left alone together, the wolf will eat the goat and the goat will eat the cabbage. What is the minimum safe sequence of crossings?
You may ask yes/no questions to identify one number from 1 to 100, and the responder answers truthfully. What strategy minimizes the worst-case number of questions, and what is that number?
You are playing a game where you take turns removing 1, 2, or 3 stones from a pile. The player who takes the last stone wins. The pile starts with 21 stones and you move first. What is the winning strategy?
A dealer lays 20 cards face down. Exactly one card is marked, but you don't know which. You may flip over exactly one card before making your final guess. What is the best strategy, and what is your probability of identifying the marked card?
Four people need to cross a bridge at night with one flashlight. At most two people can cross at once, moving at the slower person's speed. Crossing times: 1, 2, 7, and 10 minutes. What is the minimum total time for everyone to cross?
A jar contains 100 red marbles and 100 blue marbles. You may divide them between two boxes however you like. Then a box is chosen at random (50/50), and one marble is drawn uniformly from that box. How should you distribute the marbles to maximize the chance of drawing a red marble?
You and an opponent alternately choose numbers from 1 to 9 (no repeats). The first player to own any three numbers that sum to 15 wins. What hidden structure makes this game easier to analyze, and what is the best opening move?
100 prisoners are told: each day, one prisoner will be taken to a room with a single light bulb and switch. They may toggle it or leave it. Prisoners are chosen randomly (with repeats). They may plan a strategy beforehand but cannot communicate after. How can they eventually determine with certainty that all 100 have visited the room at least once?