Seven Cups, Two at a Time

Question

Seven espresso cups sit upside down on the counter. A move consists of flipping exactly two cups (any two, they may include cups you've flipped before). Can some sequence of moves leave all seven upright? Prove your answer.

Accepted Answer

Impossible. Let d be the number of upside-down cups. One move flips two cups, and there are only three cases: both were down (d to d - 2), both were up (d to d + 2), or one of each (d unchanged). In every case d changes by an even number, so the parity of d is invariant. We start at d = 7 (odd) and want d = 0 (even). No sequence of moves crosses from odd to even, so the goal is unreachable, regardless of cleverness, length, or repetition. ∎ This is the minimal member of the impossibility-by-invariant family: to prove a configuration unreachable, you do not search the move tree, you exhibit a quantity every legal move conserves that differs between start and target. Here the conserved quantity is d bmod 2; for the mutilated chessboard it's a color count; for sliding puzzles it's a permutation parity. Worth saying out loud in an interview: the converse also holds in this puzzle. From any even d you can finish (pair up the down cups and flip each pair), so parity is the complete obstruction, the reachable set is exactly "states with d even relative to the start." Closing the loop, invariant for impossibility, construction for possibility, is what separates a complete answer from a hal

Seven Cups, Two at a Time

Problem

Your answer

Hints