The Josephus Problem - Numberphile

Channel:Numberphile · Length:13:57 · Published:2016-10-28 · Views:6991131

Watch on YouTube

Summary

Numberphile with Daniel Erman on the Josephus problem, where people in a circle are eliminated in turn. It shows how the survivor's position follows a neat pattern tied to powers of two and binary.

Why HN recommends it

HN cites it as an excellent example of solving small cases to find a pattern, and as a favorite puzzle with an elegant binary solution.

There is an excellent numberphile video on Josephus problem — HN, 2018

Algorithms & data structures · Recreational & visual math

Subtitles (excerpt)

So it's called the Josephus Problem. It's based on something from history. There was a group of Jewish soldiers who were surrounded by the Roman army and they didn't want to get captured, so they decided to come up with a system- - to avoid getting captured or suicide. So they'd sit in a circle, and the first man would kill the guy to the left of him The next remaining living person would kill the next remaining living person with their sword. And they'd go around like this, till there's only one person left, and the last person would have to commit suicide of course, rather than get captured. And the story - at least the story I was told, I'm not sure if this is historically accurate - Was that Josephus preferred captured to suicide, but he worried that if he said this, the other soldiers would turn on him. And so he wanted to figure out: WHERE should he sit within the circle- - in order to be the last man living. And then he would surrender, rather than kill himself. That was the problem It's a little tricky, so let's do a smaller example. Let's say there are seven people. And so just to be clear, the way it works is: person number one kills number two. Person number three kills four, Five kills six,

On Hacker News

I really like the Josephus Problem ([Numberphile‘s Video on YT]( [VIDEO] )) because of the binary twist, really enjoyed Veritasium‘s [3x+1]( [LINK] ) and my favorite is your described [100 Prisoners Riddle]( [LINK] ) too — hostcontroller, 2022-08
Taking a break from sitting at the desk and going for a walk and thinking about the problem has worked surprisingly well for me many times. It was something I first read about in a Poincare's article on how Mathematical ideas are generated. Coming to general methods of problem solving in recreational math, I always look for symmetry and transforming the problem from one problem space to another a… — yantrams, 2018-06
When I interviewed at my current company, I was pretty stressed about the interview and watched some Numberphile videos the night before to take my mind off things. Weirdly enough one of the problems discussed in the interview was about the Josephus problem which has a neat solution in binary [0]. I don’t recall if I ever asked the interviewer whether they also watched the video recently or how t… — leipert, 2022-06
Simple examples may be useful. Exploring them, proving stuff about them it is how one may carve a foothold to solve a harder problem. Example: The Josephus Problem - Numberphile [VIDEO] — d0mine, 2019-12

Related videos