16
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ How does the king decide where to start killing? $\endgroup$
    – Kevin
    May 22, 2014 at 12:47
  • $\begingroup$ Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday. $\endgroup$
    – PM.
    May 22, 2014 at 13:16

1 Answer 1

Reset to default
19
$\begingroup$

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}$

Improve this answer
$\endgroup$
3
  • $\begingroup$ See also A006257. $\endgroup$
    – SQB
    May 22, 2014 at 13:05
  • $\begingroup$ Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question? $\endgroup$
    – PM.
    May 22, 2014 at 13:22
  • 2
    $\begingroup$ In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 \cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 \cdot 3+1=7$ $\endgroup$
    – Ross Millikan
    May 22, 2014 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.