The Josephus Problem

A politically correct representation of the game: 13 mice surround a sleeping cat
Boris A. Kordemsky: The Moskow puzzles New York, 1972 In the politically correct version, a cat is supposed to eat the thirteen mice dancing around it in such a way that it gobbles up every thirteenth mouse and the white mouse's turn is the last

The aim in the Josephus problem is usually to arrange two equally sized groups of people so that one of them is completely eliminated during counting. Over the centuries, this purely combinatorial game has appeared in many different guises with representatives from different races, nations or religions. A common version involves fifteen Christians and fifteen Turks on a ship which gets into difficulty at sea and can only be saved if half the crew go overboard. The captain arranges it so that by counting every ninth man the Christians are spared.

History

The problem probably dates back to the "decimatio", the collective punishment practised by the Roman army where every tenth man in a detachment was chosen by drawing lots and punished. In literature, it is linked to an event that occurred in the life of the Jewish historian Flavius Josephus – hence the name "the Josephus problem": when the city of Yodfat was besieged by the Roman General Vespasian, the defenders decided to commit collective suicide. Josephus is supposed to have arranged the soldiers in such a way that he and his best friend remained at the end after drawing lots.  

In Japan the Josephus problem appears more frequently in the seventeenth century, such as in the story of a step-mother who looks to favour her own fifteen children over her fifteen step-children in her will.

Mathematics

Through simple trial and error, the task is easy to solve for every concrete case. Hermann Schubert managed a mathematical treatment of the problem and the formulation of a general rule via a recursion formula he had discovered inductively (1895). In the West, elements of this theory are also found in Leonhard Euler (1776). Edmund Busche published a proof of Schubert's method (1896).

JavaScript has been disabled in your browser