Daniel Erman Solves Josephus Survival Circle via Cyclic Bit Shifts

The Josephus Problem - Numberphile — Numberphile

Numberphile

Eliminating the remainder beyond the largest power of two guarantees victory to seat 2ℓ + 1 because the sword holder never relinquishes control in a power-of-two group, an outcome calculable by moving the leading binary bit to the end.

AI-assisted summary of The Josephus Problem - Numberphile — original source. Check the original for full context.

Source published:

Key ideas

  • The classic Josephus elimination problem guarantees that surviving seats are always odd numbers, as every even seat is eliminated in the very first rotation. (1:52)
  • Whenever the total number of people in the circle is a pure power of two ($n = 2^a$), seat 1 is mathematically guaranteed to survive. (4:30)
  • For any arbitrary group size expressed as $n = 2^a + \ell$, eliminating $\ell$ people reduces the circle to an exact power of two, making seat $2\ell + 1$ the ultimate winner. (6:37)
  • In binary representation, the winning position $W(n)$ can be determined instantly by performing a one-bit cyclic left shift, moving the leading '1' to the least significant digit. (11:55)

Detailed notes

## Background Published on YouTube by the educational channel Numberphile on October 28, 2016, this video features mathematician Daniel Erman from the University of Wisconsin–Madison. Supported by the Mathematical Sciences Research Institute (MSRI) and created by Brady Haran, the presentation explores the historical mathematics puzzle known as the Josephus Problem.

## TL;DR Daniel Erman introduces the Josephus Problem, a puzzle based on an ancient suicide pact where soldiers arranged in a circle eliminate their neighbors until a lone survivor remains. By tabulating small test cases by hand, Erman demonstrates that winning seats are always odd and reset to position 1 whenever the group size is a pure power of two. He establishes the general closed-form formula $W(n) = 2\ell + 1$ by decomposing $n$ into $2^a + \ell$, proving it works for the historical 41-person scenario to identify seat 19. Finally, he reveals an elegant computational shortcut where the winning position can be found simply by cyclically shifting the leading binary bit of $n$ to the end.

## Atmosphere & style The presentation feels casual, collegiate, and infectious, capturing the spirit of an engaging one-on-one tutorial sketched out with Sharpies on brown butcher paper. Host Brady Haran provides curious, playful interjections that mirror the viewer's learning curve, transitioning from lighthearted jokes about staying out of even-numbered seats to genuine excitement when his manual calculations succeed. Erman radiates infectious enthusiasm as an educator, seamlessly turning a dark historical anecdote into an accessible, rewarding exploration of pattern recognition and binary arithmetic.

## Bulletin - [01:52](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=112s) The classic Josephus elimination problem guarantees that surviving seats are always odd numbers, as every even seat is eliminated in the very first rotation. - [04:30](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=270s) Whenever the total number of people in the circle is a pure power of two ($n = 2^a$), seat 1 is mathematically guaranteed to survive. - [06:37](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=397s) For any arbitrary group size expressed as $n = 2^a + \ell$, eliminating $\ell$ people reduces the circle to an exact power of two, making seat $2\ell + 1$ the ultimate winner. - [11:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=715s) In binary representation, the winning position $W(n)$ can be determined instantly by performing a one-bit cyclic left shift, moving the leading '1' to the least significant digit.

## Key takeaways - [00:00](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=0s) The Josephus Problem originates from a historical suicide pact among Jewish soldiers avoiding Roman capture, where Josephus needed to calculate the single surviving position to surrender instead of dying. - [00:00](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=0s) For an initial example of 7 people, step-by-step clockwise elimination wraps around the circle and leaves person 7 as the sole survivor. - [01:52](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=112s) Gathering data for small values reveals that the winning seat is always an odd number because all even-numbered seats are eliminated in the very first cycle. - [02:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=175s) The sequence of winners increases by increments of two ($1; 1, 3; 1, 3, 5, 7\dots$), periodically resetting back to 1. - [04:30](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=270s) The resets to seat 1 occur exclusively when the total number of participants $n$ is a pure power of two ($1, 2, 4, 8, 16$). - [04:30](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=270s) When $n = 2^a$, a complete round eliminates half the participants while returning the sword to person 1, recursively reducing the group until person 1 wins. - [06:37](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=397s) Any positive integer $n$ can be broken down as $2^a + \ell$, where $2^a$ is the largest power of two less than or equal to $n$ and $\ell < 2^a$ is the leftover remainder. - [06:37](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=397s) After exactly $\ell$ eliminations, the circle is reduced to $2^a$ survivors, meaning whoever holds the sword at that exact moment (seat $2\ell + 1$) is guaranteed to win. - [06:37](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=397s) Applying the general formula $W(n) = 2\ell + 1$ to $n = 13$ ($8 + 5$) yields winning seat $2(5) + 1 = 11$, which matches manual simulation. - [10:12](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=612s) For the historical 41-person scenario ($32 + 9$), the formula yields $2(9) + 1 = 19$, identifying seat 19 as the safe position. - [11:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=715s) The problem has a direct binary shortcut: expressing $n$ in binary and shifting the leading '1' to the far-right end directly yields the binary value of the winning seat. - [11:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=715s) Applying the binary cyclic shift to 41 (`101001`) shifts the leading 1 to the end, producing `010011`, which equals 19 in decimal.

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=0s) The Historical Legend and the Small Example

Daniel Erman introduces the famous mathematical puzzle known as the Josephus Problem, which takes its inspiration from a grim historical story. According to the legend Erman was told, a company of Jewish soldiers found themselves surrounded by the Roman army and resolved to avoid capture through a collective suicide pact. Arranging themselves in a circle, the first man used his sword to kill the person directly to his left. The next remaining living person then executed the person to his left, continuing in a lethal cycle until only a single survivor remained, who was expected to commit suicide rather than surrender. However, the soldier Josephus secretly preferred being captured to dying. Because openly expressing that preference would have caused the other soldiers to turn on him immediately, Josephus faced a life-or-death calculation: he had to figure out where to sit in the circle so that he would be the final person left alive, allowing him to surrender instead of taking his own life.

```mermaid flowchart TD accTitle: The Josephus Elimination Process for 7 People accDescr: Elimination order for seven soldiers showing how person 7 is the sole survivor. subgraph Round1["Round 1"] A["1 kills 2"] --> B["3 kills 4"] B --> C["5 kills 6"] C --> D["7 kills 1"] end subgraph Round2["Round 2"] D --> E["3 kills 5"] end subgraph Round3["Final Round"] E --> F["7 kills 3"] F --> G["7 Survives!"] end ```

To illustrate how tricky the problem becomes as the circle wraps around, Erman works out a small case with seven people. Person 1 executes 2, person 3 executes 4, and person 5 executes 6. At this stage, because there is no person 8, the cycle wraps back to the front: person 7 kills person 1. The turn then advances to the next survivor, person 3, who kills person 5. Finally, person 7 eliminates person 3, leaving 7 as the winner. In the historical account, Josephus was dealing with a circle of 41 people, but the general mathematical challenge is to determine the winning seat $W(n)$ for any arbitrary group of $n$ people.

- Erman notes that in high school, this puzzle was one of the key milestones that taught him how to approach math problems when nobody has shown you the answer beforehand. - He credits his former professor, Phil Hanlon, with steering him toward mathematics and teaching him the foundational strategy of gathering data by hand to look for patterns.

---

[01:52](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=112s) Gathering Data and Spotting Odd Winners

Following Hanlon's method, Erman sets up a table of data, defining $n$ as the total number of seats and $W(n)$ as the winning seat number. From the initial demonstration, it is already established that for $n = 7$, $W(7) = 7$. Testing smaller values by hand, Erman examines $n = 5$: 1 kills 2, 3 kills 4, 5 kills 1, and 3 kills 5, leaving 3 as the victor ($W(5) = 3$). Filling in $n = 6$, person 1 executes 2, 3 executes 4, 5 executes 6, 1 executes 3, and 5 executes 1, making 5 the winner ($W(6) = 5$).

| $n$ (seats) | $W(n)$ (winner) | |:---:|:---:| | 1 | 1 | | 2 | 1 | | 3 | 3 | | 4 | 1 | | 5 | 3 | | 6 | 5 | | 7 | 7 | | 8 | 1 |

Immediately, a striking pattern emerges: the winning seat is always an odd number. Erman explains why this happens almost effortlessly: during the very first pass around the circle, every person in an even-numbered seat is struck down. Brady Haran jokingly interjects to clarify the practical survival rule: “So you DON'T want to sit in an even seat?”, to which Erman adamantly replies, “Don't sit in an even seat, no no no.”

---

[02:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=175s) Tabulating Results and Predicting the Sequence

Erman proceeds to systematically compute the earliest values to establish a baseline: - For $n = 1$, the lone individual survives by default ($W(1) = 1$). - For $n = 2$, 1 kills 2, so 1 wins ($W(2) = 1$). - For $n = 3$, 1 kills 2, then 3 kills 1, leaving 3 ($W(3) = 3$). - For $n = 4$, 1 kills 2, 3 kills 4, and 1 kills 3, giving 1 ($W(4) = 1$). - For $n = 8$, after 1 kills 2, 3 kills 4, 5 kills 6, and 7 kills 8, the remaining circle $\{1, 3, 5, 7\}$ sees 1 kill 3, 5 kill 7, and finally 1 kill 5, leaving 1 ($W(8) = 1$).

Writing out the winners reveals an escalating series of odd numbers that periodically resets: $1; 1, 3; 1, 3, 5, 7; 1, 3, 5, 7, 9\dots$ Brady attempts to anticipate the pattern by asking whether $n = 13$ resets back to 1. Erman responds, “NO! Good guess actually! But it is not a one.” The sequence climbs by twos on each step, and Erman demonstrates that it will not reset at 13 or 14—in fact, for $n = 14$, the winner is 13. He emphasizes that even if they cannot immediately calculate a distant value like $n = 178$, observing this behavior allows them to form testable predictions.

---

[04:30](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=270s) Powers of Two and the First Theorem

Returning to Brady's hypothesis about when the sequence resets, Erman points out that the resets to seat 1 occur exclusively when $n$ is a pure power of two ($n = 1, 2, 4, 8, 16$). He reflects on how Professor Hanlon pushed his students when they felt frustrated by not yet having a total formula: “If you know something... Prove it, and make sure you really understand that one thing, and that often unlocks the rest.”

Following this advice, Erman formulates a formal conjecture: “If $n$ is a pure power of two, then the winning seat is one.” To prove this, he sets up the case for $n = 16$. As person 1 starts, a complete pass around the circle eliminates every even seat up to 16, with 15 executing 16. At that moment, exactly half the people have died, leaving 8 people, and the turn returns cleanly to person 1. Relabeling the survivors effectively resets the game into an 8-person circle where person 1 still holds the sword. Repeating the exact same cycle reduces 8 people to 4, then 4 to 2, and finally 2 to 1, with person 1 retaining the turn at every transition. Because the sword never leaves person 1's cycle, seat 1 is guaranteed to win whenever $n$ is a power of two.

---

[06:37](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=397s) The General Formula: $n = 2^a + \ell$

Having resolved the behavior for pure powers of two, Erman turns to the numbers lying between them, where the winning seat climbs by increments of two before resetting. He notes that any positive integer can be uniquely represented as a sum of distinct powers of two via its binary expansion. By isolating the single largest power of two that fits inside $n$, any number can be written as: $$n = 2^a + \ell$$ where $2^a$ is the largest power of two less than or equal to $n$, and $\ell$ is the leftover remainder (with $\ell < 2^a$). For instance, taking $n = 77$, the largest power of two is $64$, leaving a remainder of $13$ (which itself is $8 + 4 + 1$).

```mermaid flowchart LR accTitle: Decomposition of n into Power of Two and Remainder accDescr: Flow diagram showing how eliminating L people reduces the circle to a power of two where the next person wins. A["Total People: n = 2^a + L"] -->|"Eliminate L people (2L eliminated/active)"| B["L eliminations complete"] B --> C["Power of Two (2^a) people remain"] C --> D["Next person to strike: Seat 2L + 1"] D --> E["Seat 2L + 1 wins the entire game"] ```

Erman explains that the remainder $\ell$ directly controls which odd seat survives. He illustrates this by testing $n = 13$, which decomposes into $2^3 + 5$ (so $2^a = 8$ and $\ell = 5$): - Execute exactly $\ell = 5$ steps: 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, and 9 kills 10. - Exactly 5 people have been killed, leaving $13 - 5 = 8$ people remaining in the circle. - Since 8 is a pure power of two, the dynamics of the previous theorem take over: whoever holds the sword at this precise instant will win the game. Brady remarks, “The first killer,” and Erman confirms: “The first killer! So now, if we go from here I claim that eleven is going to win.” - Tracing it out: 11 kills 12, 13 kills 1, 3 kills 5, and 7 kills 9, cycling back to 11 with 4 people left; 11 kills 13 and 3 kills 7, leaving 2 people; 11 strikes the final blow and wins.

Erman formalizes this into the general theorem: if $n = 2^a + \ell$ with $\ell < 2^a$, then after $\ell$ kills, the turn falls on person $2\ell + 1$. Because there are exactly $2^a$ soldiers remaining at that point, that person will sweep the rest of the game, proving that the winning seat is always: $$W(n) = 2\ell + 1$$ For $n = 13$, where $\ell = 5$, the formula yields $2(5) + 1 = 11$, precisely matching the manual calculation.

[10:12](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=612s) Applying the Formula to the 41-Person Cave Problem

Having established that whenever the group size is a pure power of two, the person holding the sword first wins, Brady Haran eagerly tests his understanding on the original historical riddle. In the legend, Josephus was trapped with 40 fellow soldiers, making a total of $n = 41$ people. Brady breaks down the number using Daniel Erman’s framework $n = 2^a + \ell$: the largest power of two less than or equal to 41 is 32 ($2^5$), leaving a remainder of $\ell = 9$. Using the formula $W(n) = 2\ell + 1$, Brady calculates two lots of 9 plus 1, arriving at position 19 as the winning seat.

To verify the arithmetic, Daniel sketches out a circle of 41 numbered seats on paper, joking along the way as the numbers crowd together near the end. As Daniel crowds the digits, Brady quips, “Look at that, this is a lesson about planning ahead, people.” They simulate the elimination step-by-step: person 1 eliminates person 2, person 3 eliminates person 4, stripping away all even numbers along the way. After person 40 is eliminated, person 41 eliminates person 1. The cycle continues around the circle until person 19 executes person 35, leaving position 19 as the final survivor and confirming Brady's calculation.

```mermaid flowchart LR accTitle: Josephus Formula Calculation for 41 People accDescr: Flow diagram showing how 41 is decomposed into a power of 2 plus remainder, yielding seat 19 via the formula 2l + 1. subgraph Inputs["Decomposition"] A["n = 41"] --> B["2^5 = 32"] A --> C["Remainder ℓ = 9"] end subgraph Formula["Evaluation"] C --> D["2ℓ + 1"] D --> E["2(9) + 1 = 19"] end E --> F["Winning Seat: 19"] ```

- Total group size: $n = 41$ (Josephus plus 40 soldiers). - Largest power of two: $2^a = 32$, with $\ell = 9$ (since $41 = 32 + 9$). - Winning seat formula: $2\ell + 1 = 2(9) + 1 = 19$. - Full-sentence quote: Brady proudly exclaims, “I was right!” when 19 survives the simulation, to which Daniel replies, “There we go, nineteen!”

---

[11:55](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=715s) The Binary Shortcut and Closing Credits

Daniel points out an elegant alternative method: interpreting the problem using binary notation. Any integer can be expressed as a sum of powers of two, meaning 41 is written as $32 + 8 + 1$, or $2^5 + 2^3 + 2^0$. In standard binary representation, with digits corresponding to powers of two from $2^5$ down to $2^0$, 41 translates to `101001`.

```mermaid flowchart LR accTitle: Binary Cyclic Bit Shift for Josephus Problem accDescr: Diagram illustrating the cyclic left bit shift where the leading 1 of 41 in binary moves to the end, resulting in 19. subgraph Binary41["Binary of 41"] B1["1"] --- B2["01001"] end subgraph Shift["Bit Shift Operation"] B1 -.->|"Shift leading bit to the end"| S1["1"] B2 --> S2["01001"] end subgraph Binary19["Resulting Binary"] S2 --- S1 S2 --> R["010011_2 = 19"] end ```

Daniel reveals a fast arithmetic trick: to determine the winning position $W(n)$, simply take the leading binary digit (the initial `1`) and cycle it to the very end of the binary string. Moving the leading `1` of `101001` to the far right produces `010011`. Converting `010011` back to base ten gives $2^4 + 2^1 + 2^0 = 16 + 2 + 1 = 19$, matching the exact winning chair. Daniel highlights how this cyclic shift provides a direct leap from $n$ to $W(n)$, remarking that the underlying structure would have been instantly visible had the values been recorded in binary from the start.

- Binary of 41: $2^5 + 0\cdot2^4 + 2^3 + 0\cdot2^2 + 0\cdot2^1 + 2^0 = 101001_2$. - Cyclic shift rule: Strip the leading `1` and append it to the right: $101001 \to 010011$. - Base-10 conversion of shifted binary: $2^4 + 2^1 + 2^0 = 16 + 2 + 1 = 19$. - Full-sentence quote: Daniel explains, “The way to find the winning solution if this is n, the winning solution in binary is you take the leading digit and you put it at the end.” - Full-sentence quote: Wrapping up the binary demonstration, Daniel enthuses, “So if you're writing your numbers in binary code, the pattern would've been even more quickly apparent.” - Filming location: Mathematical Sciences Research Institute (MSRI), which supports both high-level mathematical research and outreach initiatives like Numberphile.

## Notable quotes > [04:30](https://www.youtube.com/watch?v=uCsD3ZGzMgE&t=270s) If you know something... Prove it, and make sure you really understand that one thing, and that often unlocks the rest. — Phil Hanlon

## Mentioned Daniel Erman, Brady Haran, Josephus, Phil Hanlon, University of Wisconsin-Madison, Mathematical Sciences Research Institute (MSRI), Numberphile

## Video description The Josephus Problem, featuring Daniel Erman from University of Wisconsin-Madison. Winning at Dots and Boxes: https://youtu.be/KboGyIilP6k More links & stuff in full description below ↓↓↓

Correction: Around 9:40 that should be L less than 2^a NOT 2a --- Sorry, typo in editing! But you got the point hopefully.

Support us on Patreon: http://www.patreon.com/numberphile

NUMBERPHILE Website: http://www.numberphile.com/ Numberphile on Facebook: http://www.facebook.com/numberphile Numberphile tweets: https://twitter.com/numberphile Subscribe: http://bit.ly/Numberphile_Sub

Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): http://bit.ly/MSRINumberphile

Videos by Brady Haran

Brady's videos subreddit: http://www.reddit.com/r/BradyHaran/

Brady's latest videos across all channels: http://www.bradyharanblog.com/

Sign up for (occasional) emails: http://eepurl.com/YdjL9

Numberphile T-Shirts: https://teespring.com/stores/numberphile Other merchandise: https://store.dftba.com/collections/numberphile

[Source](https://www.youtube.com/watch?v=uCsD3ZGzMgE)

中文简报

Daniel Erman通过循环位移求解约瑟夫幸存之环问题 淘汰超过最大2的幂的余数即可确保第2ℓ + 1位胜出，因为持剑者在2的幂人数的群体中永远不会失去掌控权，这一结果可以通过将最高二进制位移至末尾计算得出。 Daniel Erman介绍了约瑟夫问题，这是一个源自古代自杀协议的谜题：围坐成圈的士兵依次淘汰邻座，直到仅剩一名幸存者。通过手动列出小型测试案例，Erman证明了获胜位置始终为奇数，并且只要群体总人数恰为2的纯幂次，获胜位置就会重置为第1位。他将$n$分解为$2^a + \ell$，建立了通用闭合公式$W(n) = 2\ell + 1$，并证明该公式适用于历史上的41人场景以确定第19号位。最后，他揭示了一种极为优雅的计算捷径，即只需将$n$的最高二进制位循环移至末尾，便能求出获胜位置。 在经典的约瑟夫淘汰问题中，幸存位置必然是奇数，因为所有偶数位置在第一轮轮转中就会被全部淘汰。 (1:52) 每当圈中总人数恰为2的纯幂次（$n = 2^a$）时，第1位在数学上就必然能够幸存。 (4:30) 对于任意表示为$n = 2^a + \ell$的群体规模，淘汰$\ell$人即可使圈中人数缩减至恰好为2的幂，从而使第$2\ell + 1$位成为最终赢家。 (6:37) 在二进制表示中，通过执行一次一位循环左移，将最高位的“1”移动到最低位，即可立即求得获胜位置$W(n)$。 (11:55)

Source quotes

[4:30] Phil Hanlon: If you know something... Prove it, and make sure you really understand that one thing, and that often unlocks the rest.

Original transcript

[0:00] So it's called the Josephus Problem. [0:01] It's based on something from history. [0:04] There was a group of Jewish soldiers who were surrounded by the Roman army [0:07] and they didn't want to get captured, so they decided to come up with a system- [0:12] - to avoid getting captured or suicide. [0:14] So they'd sit in a circle, and the first man would kill the guy to the left of him [0:18] The next remaining living person would kill the next remaining living person with their sword. [0:23] And they'd go around like this, till there's only one person left, [0:26] and the last person would have to commit suicide of course, rather than get captured. [0:29] And the story - at least the story I was told, I'm not sure if this is historically accurate - [0:33] Was that Josephus preferred captured to suicide, [0:37] but he worried that if he said this, the other soldiers would turn on him. [0:40] And so he wanted to figure out: WHERE should he sit within the circle- [0:44] - in order to be the last man living. [0:46] And then he would surrender, rather than kill himself. [0:48] That was the problem [0:49] It's a little tricky, so let's do a smaller example. [0:51] Let's say there are seven people. [0:53] And so just to be clear, the way it works is: person number one kills number two. [0:58] Person number three kills four, [1:00] Five kills six, [1:02] But now things gets a little of harder to kind of see in advance [1:05] Because seven, there is no eight, so seven kills one, [1:09] Three kills five, [1:12] Seven kills three. [1:14] So seven's the winner; seven is the last one left over. [1:17] For Josephus, there were 41 people. He needed to figure out where to sit. [1:20] The mathematical problem is if there were n people. [1:22] Where's the winning seat? [1:23] When I learned this problem I was in high school, [1:25] And it was one of the first problems that got me to understand how you approach- [1:30] - difficult and- and... [1:32] Math problems where you don't know the answer in advance, or someone hasn't shown it to you in advance. [1:36] And it was a professor of mine [1:37] his name was Phil Hanlon [1:38] who played a big role in, kind of, leading me to math. [1:43] And he suggested: what we should do is we should gather data. [1:46] Just... [1:47] Take various values of n and just do it by hand [1:50] and start looking for a pattern. [1:52] I don't know, maybe we should just do that? [1:53] n is the number of seats, and w of n will be the winning seat. [1:59] And what we know so far is that: n is seven, w of n it turns out is also seven. [2:04] And so what I would do is I'd start doing some other values [2:06] So, I don't know, why don't I do five? [2:07] One kills two, [2:09] three kills four, [2:10] five kills one, [2:12] three kills five. [2:14] The winner is three. [2:15] I guess there was no reason for me to skip six, so why don't we fill in six. [2:19] One kills two, three kills four, five kills six... [2:22] ... one kills three and five kills one. [2:24] The winner is five. [2:26] So [2:26] If you're watching you might already start to notice some patterns. [2:29] For instance, they're always odd. I mean, that's maybe the first thing you notice [2:33] And you can start asking "why are they always odd?" And maybe you can already see that- [2:36] - in the first loop around, all the even people get killed. [2:39] So [2:40] So you can - even with a tiny amount of experiment - start to see some patterns. [2:44] - *Brady* So you DON'T want to sit in an even seat? - Don't sit in an even seat, no no no. [2:48] And maybe we're even getting some glimmers of other patterns [2:51] But before I really try to phrase those, I'd like to fill in the table a little bit more. [2:55] So let's do some. [2:55] So if there's only one person... [2:57] well... [2:58] That person's the winner, so that one was easy. [3:00] If there's two people: one kills two. One is the winner [3:05] If there's three people: one kills two, three kills one. Three is the winner [3:11] If there's four people: one kills two, three kills four, one kills three. [3:17] If there's eight people: one kills two, three kills four, five kills six, seven kills eight, [3:23] one kills three, five kills seven, one kills five. [3:27] The winner is one. [3:28] Alright so it was one, one, three, one, three, five, seven. [3:36] One, three, five, seven, nine. [3:40] And you could keep going, but maybe you can see the pattern now? [3:43] - *Brady* Is thirteen a one? - NO! Good guess actually! [3:46] But it is not a one. So let's do thirteen. [3:48] *Brady* This is good, I don't know then, I can't see the pattern. [3:51] So as you see it's jumping by two each time, but then it resets at some point [3:55] and [3:56] And I want to go back to this, so we'll see what thirteen is quickly [4:04] So we didn't reset that, and I claim we won't reset it the next one either. [4:07] Fourteen will be thirteen [4:09] and here, by the way, we're be starting to make predictions. [4:11] It's worth noting we've- [4:12] Even though we maybe can't say exactly what like 178 would be- [4:17] - we're starting to see well enough so we can make a prediction. [4:20] So... [4:21] so you could guess. Is it really true that fourteen is going to give you thirteen? [4:24] We could do it out, and you'll see in fact that's what you'll get [4:29] So we're getting some understanding... [4:30] But I want to go back to this point you had, you asked if it's going to reset and go back to one there [4:35] And the answer was no, and it's worth looking. [4:39] Because this is the next thing I was going to do. [4:41] Where do we get the ones? [4:42] So if you look for a sec, there's something very special about the numbers that give you ones. [4:47] It's the powers of two. [4:49] And so maybe you can now guess that if i put in a sixteen, I would get a one back. [4:54] And that'll be right, and that's actually going to be a real key in unlocking this. [4:58] The professor I was learning this from made a really big point out of this. [5:03] And I thought, you know, well [5:05] I don't know what the general answer is yet! [5:07] And he made a big point: If you know something... [5:09] Prove it, and make sure you really understand that one thing, and that often unlocks the rest. [5:14] So [5:15] So he really pushed us when I was first doing this, to try to state a conjecture and then prove a theorem- [5:21] based on what we just saw here. [5:23] And so that's what I want to do, so here's the conjecture: [5:25] If n is a pure power of two, then the winning seat is one. [5:32] I want to think about this for a second and maybe see why this might be true. [5:36] So let's do the next biggest power of two, maybe the biggest one I can bother writing down. [5:40] So let's do sixteen [5:41] So I want to do one pass through the circle. [5:46] - *Brady* Take out all the evens. - Take out all the evens. [5:49] And now, fifteen has just killed sixteen. [5:52] So I'll put a little dot here so we'll remember it's number one's turn again. [5:55] And it's number one's turn again, and we've removed all the evens. [6:00] And what's left is therefore exactly half as many. [6:03] So if i relabel at this point [6:05] You can see that there's a power of two to start with. [6:08] I pass through the circle once, I get rid of all the evens, I have half as many. [6:12] And I'm back at number one's turn. [6:14] So now if I do this again, the same thing ought to happen. [6:17] Right? I should kill all the evens on the new labeling [6:23] And now there are four people left, and it's STILL number one's turn [6:27] So you go through again... [6:29] Kill those guys, there's two people left, it's still number one's turn- [6:33] - and that one kills that, and it's still number one's turn and that chair wins. [6:37] So let's say we believe that. We know what happens to two to the n. [6:39] So how do we explain what happens between the pure powers of two? [6:43] If you see the pattern, you know- we know what happens at eight, and we know what happens at four... [6:48] ... but between them it goes up by twos until at this point, if I added two to seven, I'd have a nine [6:54] Which would be too big anyway, so that's our reset [6:57] But we knew it was going to reset because it's a pure power of two. [6:59] So how do we explain this jumping by two phenomena inbetween? [7:03] So what I'm going to do- I'm gonna just mention that: [7:05] For any number- [7:06] - you can write it as a big power of two plus something else [7:12] Take the biggest power of two you can subtract from a number- [7:14] And then what's left should be smaller than that. [7:16] When you express a number in binary notation- [7:19] - ou choose zeroes or ones, and that gives it out as a sum of a bunch of powers of two... [7:23] ... and you just choose the biggest one. [7:25] So 77. The biggest power of two I can get is 64. [7:29] And then, what is it, it's 64 + 13. [7:32] So then for 13, the biggest power of two is 8 + 4 + 1. Did I do this right? [7:40] 72... 77, there you go. And these are all powers of two! [7:43] And this is unique. This is the unique way to write 77 as a sum of powers of two. [7:50] Where no powers repeated, that's a key point. [7:53] So if you wanted to take a general number, take the biggest power of two - 64 - and then the remaining part. [8:00] *Mumble* Twelve... Thirteen. [8:01] I'm going to call this part two to the a, and the remaining part I'm going to call l [8:06] And I claim that this l is going to tell us which of those odd number between are going to show up. [8:12] So let's see how. How about we do thirteen. [8:14] n is thirteen. [8:16] This is the binary expansion, but using our new method the eight will be the two to the a- [8:21] - and the five (which is the four plus one) that'll be the l. [8:24] And here's the thing that's going to happen with the l: [8:26] I'm going to do five steps. [8:28] So 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 9 kills 10. [8:35] So now I've dropped... [8:38] l people. [8:40] And it's number eleven's turn. [8:42] Now watch what happens, how many people are left? Well what's left is a power of two. [8:46] And we know who wins in a power of two, it's whoever starts! [8:50] *Brady* The first killer. [8:51] The first killer! So now, if we go from here I claim that eleven is going to win. [8:55] And just watch, it's going to be. [8:55] 11 kills 12, 13 kills 1, 3 kills 5, 7 kills 9 [9:00] Back to eleven, and now there's only four people left. [9:03] 11 kills 13, 3 kills 7... [9:05] Back to eleven, two people... Eleven wins. [9:08] And so this is really the key to the final answer. [9:11] Which is [9:12] If you've written your number as two to the a plus l- [9:15] - after l steps, whosever turn it is is going to win. [9:19] Because it's going to be their turn and there'll be a power of two left. [9:22] And so the winning seat will be two l plus one. [9:26] If you write it in this way, because that's whose turn it is after l steps. [9:29] The theorem or the claim, is that if you've written n in this way... [9:33] So if n is two to the a plus l, where l is less than two to the a. [9:38] It has to be strictly smaller [9:39] So in other words: two to the a is the biggest power that sat inside of n. [9:43] Then the winning seat is going to be 2 l plus one. [9:47] So we've already seen it was true here, right? [9:49] l was five and the winning seat was eleven, which is two times five plus one. [9:54] And if you start going back through you'll see it's the same thing for all the answers. [9:58] We've already illustrated the mechanisms, which is after l steps- [10:03] It's the turn of person 2 l plus one, and after l steps, there are a power of two number of people left. [10:11] and... [10:12] Everyone knows that the power of two people, the first person who kills, that's who's going to be the winner [10:16] *Brady* Let's see if Brady has learned! [10:18] *chuckle* Yeah! Alright! Let's do it [10:21] *Brady* - I think I follow. Now in the Josephus problem... [10:24] - Yep! [10:25] - ... There was Josephus and 40 soldiers. [10:27] - That's right. Oh yeah! We got to go back and do that! [10:29] - Alright so we got 41 people... [10:31] - So n is 41 [10:33] - Alright, now I think - expressing that in the way you told me to - it's going to be 32 + 9? [10:40] - There you go, 32 + 9 [10:42] - So... [10:43] Two lots of nine... plus one... [10:46] - Mhm [10:47] - ... is nineteen [10:51] - There we go [10:51] - So we want to sit in position nineteen. [10:53] - There you go. You want to sit in the nineteenth chair. [10:56] So here we go we're going to do n = 41 [10:58] - Alright. Put them in, in the cave, waiting their fate. [11:04] - Not a very good circle but... [11:09] - It's getting smaller now... [11:10] - I know. [11:12] *Brady and Daniel chuckles* [11:14] *Daniel chuckles* [11:15] Should I redo this? [11:17] - Nah you're okay. [11:18] *Daniel mumbles* 40... 41... [11:19] - Okay there we are. So we got a little tight at the end [11:21] - Look at that, this is a lession about planning ahead, people. [11:25] Okay so let's do it. So one kills two... [11:29] - We're losing our even numbers. [11:31] - Yep. [11:32] Okay now... 41 kills 1. [11:35] *Daniel mumbles* three kills five... [11:50] And 19 kills 35 and there we go! [11:53] - Alright. [11:53] I was right! [11:54] - There we go, nineteen! [11:55] Oh and one other thing in this problem which is kind of fun... [11:58] So this formula I wrote can be interpreted in binary notation. [12:02] When we wrote a number as a sum of powers of two... [12:05] This can be re-expressed in binary notation. [12:08] So what was this... 32 + 8 + 1 [12:11] So that's... [12:12] 2⁵ + 2³ + 2⁰ [12:15] And binary notation... [12:17] The digits correspond to the various powers of two, and all the digits are either zero or one. [12:23] So 41 in binary notation would be one copy of 2⁵, [12:27] zero of 2⁴, [12:29] one of 2³, [12:31] zero 2², zero 2¹ and one 2⁰ [12:35] Here's the trick for the Josephus problem. [12:37] Which I won't justify but it's super cool, and you can try it own your own. [12:40] The way to find the winning solution if this is n- [12:44] - the winning solution in binary is you take the leading digit- [12:48] - and you put it at the end. [12:50] So in other words I claim that if I write [12:53] *Mumbles* Zero... One... [12:55] So I take this part and then I add the first digit to the end. [12:57] That number in binary code is... Well let's see... [13:01] It's 2⁰ + 2¹ + (I skipped 2² and I skipped 2³) and I add 2⁴ [13:10] So it's 2⁴ + 2¹ + 2⁰ [13:14] Which is [13:15] 16 + 2 + 1 [13:18] Which is nineteen, which is exactly what the winning seat was. [13:21] and... [13:22] And so there's this super efficient way in binary code to jump straight from the number n- [13:28] - to the winning number w of n. [13:30] So if you're writing you numbers in binary code, the pattern would've been even more quickly apparent [13:35] Isn't that cool?! [13:36] *Brady agrees and chuckles* [13:38] Isn't that cool? [13:38] - Yeah [13:40] This video was filmed at the Mathematical Sciences Research Institute (MSRI) [13:45] That's the building behind me. [13:46] If you'd like to find out more about them, link's in the video description. [13:49] They do some really important serious mathematics here, and they're also a big supporter of math outreach... [13:55] ...as evidenced by this video.