Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Puzzles: Set 8

Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8

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.

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

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?

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?

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.

Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates.

© Copyright 2008—2017, Gurmeet Manku.