Geometry With Only a Compass
Using only a compass (and without a straight edge or a ruler), is it possible to identify (a) the midpoint of two points? (b) the center of a circle? (c) all four corners of a square, given two of them?
Heard when I was preparing for IIT-JEE in 1990.
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?
There are n+1 processors named 0, 1, ..., n. Processor i has a counter C(i) that takes values in the range [0, n]. Its initial value is arbitrarily chosen from [0, n]. Processor 0 is said to be privileged if C(0) = C(n). Processor i, where i > 0, is said to be privileged if C(i) ≠ C(i-1). At successive clock ticks, exactly one out of possibly several privileged processors is arbitrarily chosen and its counter is updated as follows: If processor 0 is chosen, we set C(0) ← (C(0) + 1) mod (n+1). Otherwise, we set C(i) ← C(i-1). Prove that after a bounded number of clock ticks, exactly one processor will be privileged. And that this will continue to hold forever.
17 Aug 2011
© Copyright 2008—2017, Gurmeet Manku.