13:58
The Josephus Problem - Numberphile
Numberphile
Overview
This video explores the Josephus Problem, a mathematical puzzle with historical roots in a story about Jewish soldiers. The problem involves people sitting in a circle, eliminating every second person until only one remains. The video demonstrates how to find the 'winning seat' through experimentation and pattern recognition, revealing a connection to powers of two and binary representation. It presents a formula to solve the problem for any number of people, illustrating its application with the historical case of Josephus and 41 soldiers.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- The Josephus Problem originates from a story of Jewish soldiers facing Roman capture.
- Soldiers sat in a circle and eliminated every second person until one remained.
- Josephus supposedly wanted to find his optimal position to be the last survivor and surrender.
- The core mathematical problem is to determine the winning seat for 'n' people.
Understanding the historical context and the basic setup of the problem helps in grasping its origins and the motivation behind seeking a mathematical solution.
Seven people in a circle: 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 1, 3 kills 5, 7 kills 3. Winner is 7.
- To solve the problem, gather data by calculating the winner for various numbers of people ('n').
- The winning seat number is consistently odd, as all even-numbered people are eliminated in the first round.
- Calculating winners for small 'n' (1, 2, 3, 4, 5, 6, 7, 8) reveals a pattern that isn't immediately linear.
- Experimentation is a key strategy for approaching complex mathematical problems without prior knowledge.
This empirical approach demonstrates a fundamental problem-solving technique in mathematics: collecting data to identify patterns, which is crucial for formulating hypotheses.
For n=8, the sequence of eliminations leads to person 1 winning. The winners for n=1 to 8 are: 1, 1, 3, 1, 3, 5, 7, 1.
- A key observation is that when 'n' is a power of two (2, 4, 8, 16...), the winner is always person number 1.
- This occurs because after eliminating all even numbers, exactly half the people remain, and the turn returns to person 1.
- This process repeats until only person 1 is left.
- Understanding the solution for powers of two is presented as a crucial step to unlocking the general solution.
Identifying the special case of powers of two provides a solid anchor point and a proven sub-solution, which is a common strategy in tackling more complex mathematical problems.
For n=16, after the first round, 8 people remain, and it's person 1's turn. This halving process continues, always returning to person 1's turn, until person 1 wins.
- Any number 'n' can be expressed as the sum of the largest power of two less than or equal to 'n', plus a remainder 'l' (n = 2^a + l).
- The remainder 'l' indicates how many people are eliminated before the circle reduces to a power of two.
- After 'l' eliminations, the person whose turn it is will be the winner because the remaining number of people is a power of two.
- The winning seat is calculated as 2*l + 1.
This formula provides an efficient, direct method to calculate the winner for any given number of people, transforming the problem from an empirical exercise to an analytical one.
For n=13, the largest power of two is 8 (2³). So, 13 = 8 + 5. Here, l=5. The winning seat is 2*5 + 1 = 11.
- The formula n = 2^a + l has a direct parallel in binary number representation.
- A shortcut exists: write 'n' in binary, move the leading '1' to the end of the binary string, and convert back to decimal.
- This binary manipulation directly yields the winning seat number.
- This method offers a quick and elegant way to solve the Josephus Problem.
Connecting the mathematical solution to binary representation reveals a deeper structure and provides an extremely efficient computational shortcut, highlighting the elegance of number theory.
For n=41: Binary is 101001. Move the leading '1' to the end: 010011. This binary number converts to decimal as 16 + 2 + 1 = 19, which is the winning seat.
Key takeaways
- The Josephus Problem is a classic puzzle illustrating how to find a winning position in a process of elimination.
- Empirical data collection and pattern recognition are powerful tools for solving mathematical problems.
- Powers of two play a critical role in the Josephus Problem, simplifying the solution significantly.
- Any number 'n' can be decomposed into a power of two plus a remainder, which is key to the general solution.
- The formula for the winning seat is derived from this decomposition: 2*l + 1, where 'l' is the remainder.
- The problem has an elegant solution using binary representation: cyclically shifting the bits of 'n' yields the winner's position.
Key terms
Josephus ProblemElimination processWinning seatPowers of twoEmpirical dataPattern recognitionBinary representationRemainderCyclic shift
Test your understanding
- What is the fundamental setup of the Josephus Problem?
- Why are powers of two significant in solving the Josephus Problem?
- How can any number 'n' be expressed to help find the winning seat?
- What is the formula for the winning seat based on the remainder 'l'?
- How does the binary representation shortcut work for finding the winning seat?