Java Reference
In-Depth Information
the person holding the hot potato is eliminated, the circle closes ranks, and the
game continues with the person who was sitting after the eliminated person
picking up the hot potato; the last remaining person wins. A common assump-
tion is that M is a constant, although a random number generator can be used
to change M after each elimination.
The Josephus problem arose in the first century A . D . in a cave on a moun-
tain in Israel where Jewish zealots were being besieged by Roman soldiers.
The historian Josephus was among them. To Josephus's consternation, the
zealots voted to enter into a suicide pact rather than surrender to the Romans.
He suggested the game that now bears his name. The hot potato was the sen-
tence of death to the person next to the one who got the potato. Josephus
rigged the game to get the last lot and convinced the remaining intended vic-
tim that the two of them should surrender. That is how we know about this
game; in effect, Josephus cheated. 1
If M = 0, the players are eliminated in order, and the last player always
wins. For other values of M, things are not so obvious. Figure 13.1 shows that
if N = 5 and M = 1, the players are eliminated in the order 2, 4, 1, 5. In this
case, player 3 wins. The steps are as follows.
In the Josephus
problem, a hot
potato is repeatedly
passed; when pass-
ing terminates, the
player holding the
potato is elimi-
nated; the game
continues, and the
last remaining
player wins.
1.
At the start, the potato is at player 1. After one pass, it is at player 2.
2.
Player 2 is eliminated. Player 3 picks up the potato, and after one
pass, it is at player 4.
3.
Player 4 is eliminated. Player 5 picks up the potato and passes it to
player 1.
4.
Player 1 is eliminated. Player 3 picks up the potato and passes it to
player 5.
5.
Player 5 is eliminated, so player 3 wins.
figure 13.1
The Josephus
problem: At each step,
the darkest circle
represents the initial
holder and the lightly
shaded circle
represents the player
who receives the hot
potato (and is
eliminated). Passes
are made clockwise.
1
2
3
1
3
1
3
3
3
5
4
5
4
5
5
(a) (b) (c) (d) (e)
1. Thanks to David Teague for relaying this story. The version that we solve differs from the
historical description. In Exercise 13.11 you are asked to solve the historical version.
 
Search WWH ::




Custom Search