Posted by: ardaayvaz | November 9, 2008

Josephus problem

Hi Math 152,

I want to introduce another interesting math problem called Josephus problem.

This problem comes from an actual historical event,  documented by the Jewish historian Flavius Josephus  who lived in the first century.  The story line is that Josephus and his 40 comrade soldiers  were trapped in a cave, surrounded by the Roman Army. Understanding that they won’t be able to run away and they don’t want to surrender, they decide to kill each other before getting caught. So, all 41 men form a circle, and they kill every third men going around the circle. The actual story is that Josephus and another man are left the last two remaining during that process and Josephus convinces the other survivor to surrender to Romans instead of killing themselves.

Thus the mathematical problem that arises from this story is as follows:

Given a group of m men, and given that every nth man around the circle is going to be executed, which position L(n,m) you should choose to be the last survivor?

When I first heard the problem it sounded really easy to me, but apparently it is a more complicated problem that has applications in computer science as well, and the most common method to solve such problem is to use a recursive algorithm.

To find out more about the solution of the problem, you can refer to the following resources:

http://mathworld.wolfram.com/JosephusProblem.html

http://en.wikipedia.org/wiki/Josephus_problem

Advertisements

Responses

  1. Math is full of these wonderfully simple-to-state problems with difficult answers. I hadn’t heard of this one. What wonderful complexity it demonstrates! In the Wolfram link above, it has several links to the list of solutions in Sloan’s Online Encyclopedia of Integer Sequences. This is a delightful place to spend time.

  2. I like logic

  3. […] Josephus problem […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: