Problem #20 MEDIUM

Glasses in the Dark

Apple Amazon Game Theory Logic

Problem Statement

You are blindfolded and seated at a round turntable with four identical glasses arranged at the four compass positions. Each glass is either upright (opening facing up) or inverted (opening facing down) in some hidden starting configuration. Each round: you may pick any one or two glasses and flip them however you like, then you must step back. An assistant then silently rotates the turntable by a random unknown number of positions. You win the moment all four glasses face the same direction. Can you guarantee a win? If so, what is your strategy?

Answer & Quick Explanation

Think you've got it? Click below to check your answer.

Yes — win is guaranteed within 5 rounds. Execute the fixed sequence: diagonal flip → adjacent flip → single flip → diagonal flip → single flip. Each step resolves at least one rotation-equivalence class of configurations.

Detailed Editorial Solution

Want to see the step-by-step breakdown? Click below to reveal the editorial.

There are only a handful of rotationally distinct ways to arrange 4 glasses in up/down states. The 5-step strategy is a decision procedure that systematically eliminates each non-winning configuration type. Step 1: Round 1 — Flip a diagonal pair: If both were identical, you've made them opposite; if they were already opposite, now they match. This resolves the 'all alternating diagonal' configuration. Step 2: Round 2 — Flip an adjacent pair: Targets the case where two side-by-side glasses are the remaining mismatch. Step 3: Round 3 — Flip any single glass: Converts a 3-up/1-down (or 3-down/1-up) arrangement toward uniformity, or triggers a win directly. Step 4: Round 4 — Flip a diagonal pair again: Catches any remaining rotationally shifted version of the diagonal-mismatch configuration. Step 5: Round 5 — Flip any single glass: This final step is the catch-all for any configuration that survived rounds 1–4. Step 6: Mathematical proof by exhaustion: all 2^4 = 16 starting configurations, when analyzed for their rotation-equivalence classes, collapse to at most 5 distinct types — one per step. Key Insight: Rotation symmetry reduces 16 raw configurations to only 5 equivalence classes. The strategy needs exactly one move to resolve each class. Since each step either wins or reduces the class, 5 steps are sufficient and necessary.