Prisoners in a Circle

#1

The warden takes 100 prisoners and has them stand in a circle. Prisoner 1 is handed a “get out of jail” card. The prisoners are instructed to pass the card clockwise around the circle skipping every other prisoner. Any prisoner that is skipped has to step out of the circle (ex the game starts with Prisoner 1 passing to 3 and 2 being removed from the game). This process continues until there is only one prisoner left. This prisoner wins the card and is released. Which number prisoner do you want to be?

In general there are n prisoners playing and each round k prisoners are skipped, which prisoner do you want to be?

#2

@Thomas was just describing this to me yesterday with soldiers in a circle killing their neighbors! But this version is obviously much better.

#3

Gonna kinda brute force the n=100, k=1 case first.

Summary

After every round of eliminations, with h prisoners remaining, we’ll adjust their numbers down to 1-h, and keep track of the operations so when we’re done we can reverse them to find out what the winning position was.

After round 1, odd prisoners remain, 1 - 99, adjusting them by (i + 1)/2 we get 1-50.

After round 2, odd prisoners 1- 49 remain, adjusting them again by (i+1)/2 we get 1-25.

After round 3, odd prisoners 1-25 remain, same operation and we get 1 - 13.

This time (round 4), prisoner 1 gets skipped (implying that prisoner 1 is only safe if n is a power of 2) so even numbers 2 - 12 remain. Dividing them by 2 we get 1-6.

After round 5, prisoners 1, 3, & 5 remain, (i+1)/2 makes them 1,2,3, then 2 gets skipped, then 1 gets skipped so 3 is the winner. Now let’s reverse the operations to find out what original position this was.

At round 5, 3 was 5, before that it was 10 (round 4), before that 19 (round 3), before that 37 (round 2), and before that it was 73 (round 1). So looks like prisoner 73 is our winner.

#4

It’s always better with prisoners!

Nice, that answer is right Alan. There is a less brute force way as well. The observation of

Summary

Prisoner 1 wins when n is a power of 2 is good

Also, as a clarification for k > 1, if there are k or fewer prisoners remaining, who ever is holding the card wins.

#5

This reminds me of a card trick I learned (and forgot (and learned and forgot …)) a while ago:

and is driven by extremely similar math

#6

Where’s the general solution??

#7

Pretty cool card trick! @ncameron

#8

I’m confused about the general case, if k > n how does the game play? Say k =3 and n = 2 who wins and why?

#9

I gotchu. Well, depending on what happens when k > n.

Summary

Let f(n,k) represent the winning prisoner for the game played with n prisoners and where we skip k of them. Through out this we number the prisoners 0 through n-1 as this makes the solution a little cleaner. Consider what happens on the first turn, we remove k people from the game and shift to the k'\text{th} prisoner to move. Thus we now have the game f(n-k,k) about to played out with the winning seat being shifted k to account for the fact that we started with prisoner k instead of prisoner 0. So we get the relation:

f(n,k) = (f(n-k,k)+k)\text{ mod } n

So all we need now is a base case, which is a bit of a problem as I don’t understand what happens when k > n. My assumption is that in that case the player who ends with the card is the winner in which case we get this function:

f(n,k) = \begin{cases} k \text{ mod } n & \text{if } k > n\\ (f(n-k,k)+k) \text{ mod } n & \text{otherwise} \end{cases}

Which, if you could solve this relation maybe you could get a closed form thing. I suspect you can’t. Although this function is O(n) which isn’t too bad to compute, might be a bit tedious for the prisoner but “no price is too high to pay for the privilege of owning yourself” and all that.

1 Like