The Queue Puzzle
Solution


All the queues described are counting games. Given a set of objects numbered 1 to N, but arranged in a ring, the counting game skips M-1 clients and "serves" the M-th client, that is, eliminates that client. Again, M-1 clients are skipped over, and the M-th one eliminated. When the counting reaches the last object, the count continues with the first remaining object; that is, the objects are treated as though they were in a ring.

The counting for the queues is down using the rhythm of a counting rhyme. Each stressed syllable counts one object, and the last object counted is eliminated.

Josephus should place himself in position 31. This problem is ascribed to Flavius Josephus, a Jewish Roman historian who was supposedly in a group of 41 zealots who had decided to die. They agreed to sit in a circle, and starting from a fixed position, every third man counted would be killed, and the last would kill himself. By figuring rapidly, Josephus positioned himself in the last spot, and hence was able to survive.

Back to The Queue Puzzle.


Last revised on 01 April 2000.