One classic puzzle has many different forms, but the basic strategy is the same.
Once upon a time there was a crazy king who had a very wise minister with him. The king had a habit of playing a strange game on a circular table.
The game was played as follows: The king told his minister a different number everyday - let's say he says 5. Then minister would then arrange five people and ask them to sit in a circular table with five chairs. Starting from a specific person, the king would then kill every second person on the table, until only one remained at the end, to which he would give 1,000 gold coins.
For example, if there were five people on the table, starting from person 1, he would kill person 2, person 4, person 1, and person 5 (skipping over persons 2 and 4 since they are already dead), leaving person 3 as the survivor and winner.
Now the wise minister was so clever as to calculate the winner beforehand as soon as king said the number, and asked his man to sit at particular seat so as to not be killed and also win some gold.
How did the minister decide the winner?
Answer
This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2\cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$
No comments:
Post a Comment