WordGPT

The Josephus problem with 41 people

Exercise · Level 4 (Hard)

41 people stand in a circle. Every second person is eliminated, starting by eliminating person 2. Where should you stand to be the last survivor?

J(41)= ?J(41)=\ ?

wordgptpro.com

Solution

  1. With n=2m+Ln=2^m+L and 0≤L<2m0\le L<2^m, the survivor is J(n)=2L+1J(n)=2L+1. Reason: after LL eliminations exactly 2m2^m people are left and it is person 2L+12L+1's turn to be skipped, and with a power of two people the first one always survives.

  2. Here 41=32+941=32+9, so m=5, L=9m=5,\ L=9:

    J(41)=2⋅9+1=19J(41)=2\cdot9+1=19
    (1)
  3. Legend says Josephus used this to survive a suicide pact in 67 AD; standing at position 19 of 41 puts you last.

Answer1919

wordgptpro.com

Need a hint?

Write n = 2m2^{m} + L. The survivor is 2L + 1.

With 41 people and every second one eliminated, the survivor is in position 19 (J(n) = 2L + 1 for n = 2m2^{m} + L).

How to work it out

  1. With n=2m+Ln=2^m+L and 0≤L<2m0\le L<2^m, the survivor is J(n)=2L+1J(n)=2L+1. Reason: after LL eliminations exactly 2m2^m people are left and it is person 2L+12L+1's turn to be skipped, and with a power of two people the first one always survives.

  2. Here 41=32+941=32+9, so m=5, L=9m=5,\ L=9:

    J(41)=2⋅9+1=19J(41)=2\cdot9+1=19
    (1)
  3. Legend says Josephus used this to survive a suicide pact in 67 AD; standing at position 19 of 41 puts you last.

LaTeX source of the formulas on this page
\[ 19 \]
\[ J(41)=2\cdot9+1=19 \]

Questions

What is the answer to: The Josephus problem with 41 people?

With 41 people and every second one eliminated, the survivor is in position 19 (J(n) = 2L + 1 for n = 2m2^{m} + L).

What is the key idea?

After L eliminations the circle shrinks to a power of two, where the first person always survives.

Is there a hint?

Write n = 2m2^{m} + L. The survivor is 2L + 1.

Related problems

More probability and puzzles

    The Josephus problem with 41 people: answer and solution | WordGPT