Thursday, July 21, 2016

Josephus Problem


Josephus Problem – Theoretical Problem

The Josephus problem in computer science and mathematics is a theoretical problem associated to a definite counting-out game where people tend to be standing in a circle waiting to be executed. Josephus Flavius was the famous Jewish historian of the first century during the era of the Second Temple destruction. It is said that during the Jewish-Roman war, he together with 41 soldiers had been trapped in a cave and surrounded by the Romans.

According to legend the Jews had decided to form a circle and go around it to kill every third remaining person. The counting started at an indicated point in the circle and continued around the circle in a stated direction wherein after a certain number of people had been skipped, the next person was said to be executed.

 This process was repeated with the ones remaining in the circle beginning with the next person and going in the same direction; skipping the same number of individuals till eventually only a single person was left and was freed. In the Jewish rebellion against Rome, Josephus and his companions had been holding out against the Romans in a cave and with defeat impending, they had decided that like the rebels at Masada, they would die rather than be slaves to the Romans.

Highly Addictive Mystery

They had then planned to arrange them in a circle and one person had been designated as number one which proceeded clockwise killing every seventh person. As per the story, Josephus besides other things was an accomplished mathematician and hence he quickly figured out where he should be, in order to be the last to go.

However when the time came, he joined the Roman side instead of killing himself. The Josephus problem is said to be a highly addictive mystery if ever there seemed to be one. A comparatively well-known arithmetical riddle which tends to crop up frequently in general mathematics as well as in computer science, is part of the family of demolition problems.

The historical dimension of the story tends to pique interest and seems complex in resisting the attraction of obtaining more details on how the hero seemed to save his life during those days.

Medieval Version of Josephus Problem

This historical context enables us to scale the skill of Josephus Flavius in the situation in which he found himself holed in a cave being aware that any flaw would end up in losing his life which is barely favourable to a serene mind in need of solving a cerebral problem which had involved a circle of 41 men.

A Medieval version of the Josephus problem includes 15 Turks together with 15 Christians on board a ship caught in a storm which would sink unless half the passengers were thrown overboard. All 30 of them seemed to stand in a circle and every ninth person is said to be thrown into the sea. In another version the roles of the Turks and the Christian are switched.

In A Foundation for Computer Science, Concrete Mathematics, Graham, Knuth and Patashnik have described and studied a typical variant – Determine where the last survivor tends to stand should there be `n’ people to begin and every second person is removed.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.