For your mathematical recreation, here is an old problem from Yemelyan Ignatyevich Ignatyev’s book In the Realm of Ingenuity:
“Four tables stood in an inn, forming a quadrilateral. 21 hungry soldiers returning from manoeuvres stopped there for dinner and invited the innkeeper to join them. They sat as follows: the soldiers occupied three tables, 7 at each, while the innkeeper sat at the fourth.”
“The soldiers agreed with the innkeeper that the last person remaining would pay the bill under the following rule: count everyone, including the innkeeper, clockwise around the circle, and release every seventh person. Each person released left the inn, and the innkeeper himself was the last to remain. With whom did the counting begin?”
Ye. I. Ignatyev gives only the answer: “The counting must begin with the 6th soldier seated to the innkeeper’s left.” He does not provide a solution method.
Try finding the starting person yourself in a similar case, for example if there were 4 soldiers at each of the three tables.
We will ask you to explain why the counting must begin there. The solution appears at the end of the article.
Historical background
Yemelyan Ignatyevich Ignatyev (1869–1923) was a Russian and Soviet mathematics educator and author of popular-science books. His best-known work, In the Realm of Ingenuity, appeared in three volumes in 1908–1911:
Ignatyev, Ye. I. In the Realm of Ingenuity, or Arithmetic for Everyone. — Parts 1–3. — St Petersburg: V. L. Bogushevsky, 1908–1911.
The problem resembles the historical Josephus problem, known since 1612, when the French mathematician Bachet de Méziriac published it in his collection Problem es Plaisants. Its story is based on an account in Josephus’ historical work The Jewish War.
The problem is as follows: 41 soldiers stand in a circle. Starting with the first soldier, they kill every third person. Where should one stand to be the last survivor?
Josephus (Latin Josephus Flavius, c. 37–c. 100 CE) was an ancient Jewish historian and military commander. He is known for works that survive in Greek: The Jewish War, about the revolt of 66–71, and Antiquities of the Jews, recounting Jewish history from the creation of the world to the Jewish War.
Solution
An algorithm for solving the problem appears in the book:
Donald Knuth, Ronald Graham, Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. [Translated from English.] — 2nd ed. — Moscow: Williams, 2009. — 784 pp.
This is a well-known recurrence problem in computer algebra. It is often used as a test problem in various settings, including interviews.
We will use the familiar recurrence formulas for the Josephus problem. In the more general version, n soldiers are counted around a circle and every kth soldier is killed. Denote the safe position, that of the last survivor, by J(n, k).
Let us model the process by creating a list of 22 elements: 0 is the innkeeper and 1–21 are the soldiers.
The following recurrence is known in the language of modular arithmetic:
J(n, k) = (J(n − 1, k) + k) mod n, where J(1, k) = 0.
In the classical Josephus problem with n = 22 and k = 7, the last survivor’s position is calculated as J(22,7). Here we need the reverse: knowing that the last person is at position 0, the innkeeper, find the starting position. If the standard start at position 0 leaves the survivor at J(n,k), then to leave position x last, counting must begin at (x − J(n,k)) mod n. The formula for the starting position is also known: S = (x − J(n,k)) mod n, where x is the desired last survivor.
For our problem, n = 22, k = 7, x = 0 (the innkeeper). Recursive calculation — try it by hand — gives J(22,7) = 16.
We need the last position to be 0. The formula therefore gives:
Thus, counting must begin at position 6.
Check: arrange all the participants in a circle — 0 is the innkeeper and 1–21 are the soldiers — and begin counting at position 6. Successively removing every 7th person leaves the innkeeper last.
Answer: counting must begin with the 6th soldier seated to the innkeeper’s left.