Find all configurations of 4 points in a plane with only 2 distinct values for distances between pairs of points.
From Mathematical Mind-Benders (160 pages, 2007) by Peter Winkler. The book does not contain a proof that only six configurations exist.
Diagram thanks to AffineMess.
Notes: Detailed explanation of the solution: here (at AffineMess).
Consider a finite but arbitrary number of identical finite state machines (soldiers) arranged in a line. At time t = 0, each soldier is initialized to the quiescent (idle) state, except for the soldier on the far left (the general). The state of each soldier at each discrete time-step t > 0 is dependent on its state and the state of its two neighbors at time t - 1 (except for the two soldiers at either end, each of whose state depends only on itself and its sole neighbor). In addition, if a soldier and its neighbors are in the quiescent state, then the soldier will remain quiescent at the next time-step. The problem is to define a finite set of states and state transition rules for the soldiers such that all soldiers enter a distinguished state (fire) at the same time and for the very first time.
A blind gnome and an evil goblin take turns to play a game. Four tumblers are placed at the corners of a square table. The initial configuration of the tumblers (facing up or facing down) is chosen by the evil goblin. When the blind gnome gets his turn, he is allowed to specify a subset of the four tumblers and flip them simultaneously. To be precise, he may choose "one tumbler", "two diagonally opposites", "two adjacent", "three tumblers" or "four tumblers" lying in front of him, and flip them simultaneously. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues and the evil goblin is allowed to rotate the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?