Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Four Points, Two Distinct Distances

Puzzle

Find all configurations of 4 points in a plane with only 2 distinct values for distances between pairs of points.

Source

From Mathematical Mind-Benders (160 pages, 2007) by Peter Winkler. The book does not contain a proof that only six configurations exist.

Solution

Diagram thanks to AffineMess.

Let the two distances be A and B. There are 4 cases to consider:

  1. AAAAAA: No possible configuration.
  2. AAAAAB: The only possible configuration is two equilateral triangles sharing an edge.
  3. AAAABB: Two cases (resulting in 3 configurations):
    1. All distances from some point to the other 3 points are A. Then some 3 points form an equilateral triangle. Let XYZ be the equilateral triangle. Draw a circle with center X and radius XY. The fourth point W must lie at the intersection of the perpendicular bisector of YZ with the circle. There are two such points. Both are valid configurations.
    2. No point has all 3 distances to other points as A. Then the four points must form a rhombus. Since the other two distances are BB, the configuration must be a square.
  4. AAABBB: Two cases (resulting in 2 configurations):
    1. AAA corresponds to an equilateral triangle. The BBB corresponds to distances of the fourth point to the three points in the triangle. So the fourth point must lie at the intersection of the perpendicular bisectors of the edges of the equilateral triangle, which also happens to be centroid.
    2. AAA corresponds to edges { WX, XY, YZ } while BBB corresponds to edges { XZ, ZW, WY }. This configuration has a unique solution: 4 out of 5 points of a regular pentagon.

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?

8 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.