Math Detours · Grade 8 · Around the corner · 23

The Josephus problem

Forty-one people in a circle, every second one leaves. Where do you stand to be last? The answer is a binary trick.

Name ____________________Date ____________

Tonight's idea

Put \(n\) people in a circle, numbered 1 to \(n\). Skip 1, remove 2, skip 3, remove 4, and keep going round, always skipping one survivor and removing the next, until one person is left. Call that person \(J(n)\).

1234678910 5 8th1st6th2nd3rd7th4th9th5th removal order: 2, 4, 6, 8, 10, 3, 7, 1, 9 J(10) = 5
Ten people: the first lap removes the even numbers, the second lap removes 3 and 7, then 1 goes, and 9 goes last.

Try \(n = 8\). The first lap removes 2, 4, 6, 8, leaving 1, 3, 5, 7 with the count back at 1: an 8-game shrunk to a 4-game, 1 still first. Halve again: 1 and 5 remain. So 1 survives, and the same halving works for any power of two: \(J(2^m) = 1\).

Now any \(n\). Write \(n = 2^m + L\), where \(2^m\) is the largest power of two not above \(n\). The first \(L\) removals take out 2, 4, …, \(2L\). Exactly \(2^m\) people remain, and the next person to be skipped is \(2L + 1\). From here on it is a power-of-two game in which \(2L+1\) plays the part of "1", so \(2L+1\) survives.

\(J(n) = 2L + 1\), where \(n = 2^m + L\) and \(0 \le L \lt 2^m\).

In binary this is a rotation. \(n\) is a 1 followed by the digits of \(L\), and \(2L+1\) is the digits of \(L\) followed by a 1. Move the leading 1 to the end.

Watch one: \(n = 41\)

The largest power of two not above 41 is 32, so \(L = 41 - 32 = 9\) and \(J(41) = 2 \times 9 + 1 = 19\). In binary, \(41 = 101001_2\). Move the leading 1 to the end: \(010011_2 = 16 + 2 + 1 = 19\). Same answer, no arithmetic.

The problem is named after Josephus, a historian who, as the story goes, survived a count like this in a cave during a Roman siege. The traditional puzzle removes every third person instead, and that version has no formula this neat.

Your turn

  1. Ten people. Run the count by hand and write down the order in which people are removed. Check that the survivor matches the formula.
  2. Find (a) \(J(100)\) and (b) \(J(1000)\).
  3. Write 100 in binary, rotate the leading 1 to the end, and convert back. Does it agree with 2(a)? Then use the rotation alone to find \(J(77)\), and check it with the formula.
  4. For which \(n\) does the last person standing also carry the last number, \(J(n) = n\)? List every such \(n\) below 100, then use the formula to explain the pattern. What do these numbers look like in binary?

Stretch: you and a friend

There are 41 people in the circle, and you and a friend both want to be among the last two left standing. Where should the two of you stand? Hint: after the first 9 removals, 32 people remain and the count starts at 19. Who are the last two in a circle of 32?

Answers

  1. Removed in order: 2, 4, 6, 8, 10, 3, 7, 1, 9. Survivor 5. Formula: \(10 = 8 + 2\), so \(J(10) = 2 \times 2 + 1 = 5\).
  2. (a) \(100 = 64 + 36\), so \(J(100) = 73\). (b) \(1000 = 512 + 488\), so \(J(1000) = 977\).
  3. \(100 = 1100100_2\). Rotating gives \(1001001_2 = 64 + 8 + 1 = 73\), the same. \(77 = 1001101_2\), rotated \(0011011_2 = 16 + 8 + 2 + 1 = 27\). Check: \(77 = 64 + 13\), \(2 \times 13 + 1 = 27\).
  4. \(n = 1, 3, 7, 15, 31, 63\). We need \(2L + 1 = 2^m + L\), so \(L = 2^m - 1\) and \(n = 2^{m+1} - 1\), one less than a power of two. In binary these are all 1s, and rotating a string of 1s changes nothing.

Stretch. Stand at 19 and 35. After 2, 4, …, 18 are removed, 32 people remain and 19 is next to be skipped, so 19 plays "1" in a 32-game. In a circle of 32, each lap removes every second survivor and keeps 1 first: 16 remain, then 8, 4, and finally 2, namely 1 and 17 (the survivor halfway round). Position "17" in the shrunk game is the 17th of the 32 remaining people counted from 19, which is \(19 + 16 = 35\).

← PreviousNext: The shortest path bounces →