Хитрые солдаты в корчме

Предлагаем для вашего математического досуга старинную задачу из книги «В царстве смекалки» Емельяна Игнатьевича Игнатьева:

«В корчме стояло четыре стола, образуя четырёхугольник. Проголодавшиеся, возвращавшиеся с манёвров солдаты остановились там в числе 21 человека пообедать и пригласили к обеду и хозяина. Расселись все так: за тремя из столов сели солдаты — по 7 за каждый стол, а за четвёртым столом сел хозяин».

«Солдаты уговорились с хозяином, что платить по счёту будет тот, кто останется последним при следующем условии: считая в круговую (по часовой стрелке) всех, в том числе и хозяина, освобождать каждого седьмого. Каждый освобождённый уходил из корчмы и последним остался сам хозяин. С кого начали счёт?»

Е. И. Игнатьев даёт только ответ: «надо начинать счёт с 6-го солдата, сидящего по левую руку от хозяина». Метод решения не приводится.

Попробуйте сами, например, аналогично найти, с кого нужно было бы начать, если бы солдат было по 4 за каждым из трёх столов?

Ну а мы попросим вас объяснить, почему это так надо считать. Решение приведём в конце статьи.

Историческая справка

Емельян Игнатьевич Игнатьев (1869–1923) — российский и советский педагог-математик и автор научно-популярных книг. Наиболее известное произведение Игнатьева — «В царстве смекалки», выпущенное в 1908–1911 гг. в трёх томах:

Игнатьев Е. И. В царстве смекалки или арифметика для всех. — Ч. 1–3 — СПб, В. Л. Богушевский, 1908–1911.

Задача похожа на историческую задачу Иосифа Флавия, известную ещё с 1612 года, когда французский математик Баше де Мезириак опубликовал эту задачу в своём сборнике Problem es Plaisants. Сюжет задачи основан на истории, описанной Иосифом Флавием в своём историческом труде «Иудейская война».

Она заключается в следующем: по кругу стоит 41 воин, начиная с первого воина они убивают каждого третьего. Спрашивается, в каком месте нужно встать, чтобы остаться последним выжившим.

Иосиф Флавий (лат. Josephus Flavius, ок. 37 – ок. 100 н. э.) — древнееврейский историк и военачальник. Он известен дошедшими до нас на греческом языке трудами — «Иудейская война» (о восстании 66–71 годов) и «Иудейские древности» (где изложена история евреев от сотворения мира до Иудейской войны).

Решение

Алгоритм решения задачи есть в книге:

Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Математические основы информатики. Concrete Mathematics. A Foundation for Computer Science : [пер. с англ.]. — 2-е изд. — М. : Вильямс, 2009. — 784 с.

Это известная в компьютерной алгебре задача на рекуррентные соотношения. Она часто предлагается как тестовая задача в различных ситуациях, в том числе и на собеседованиях.

Используем известные рекуррентные формулы задачи Иосифа Флавия. В более общей формулировке участвует n воинов, которые считаются по кругу, и убивают каждого k-го. Номер безопасного места, то есть последнего выжившего обозначим J(n, k).

Попробуем смоделировать процесс. Создаём список из 22 элементов (0 — хозяин, 1–21 — солдаты).

Известна такая рекуррентная формула на языке модулярных вычислений:

J(n, k) = (J(n − 1, k) + k) mod n, где J(1, k) = 0.

В классической задаче Иосифа Флавия для n = 22 и k = 7 позиция последнего выжившего вычисляется по формуле J(22,7). Но здесь нужно обратное: зная, что последний — позиция 0 (хозяин), найти стартовую позицию. Если при стандартном начале с позиции 0 последний выживший — это J(n,k), то чтобы последней была позиция x, нужно начать с позиции (x − J(n,k)) mod n. Формула стартовой позиции тоже известна: S = (x − J(n,k)) mod n, где x — желаемый последний выживший.

Тогда для нашей задачи: n = 22, k = 7, x = 0 (хозяин). Вычисляется рекуррентно (попробуйте вручную), что J(22,7) = 16.

J(1,7) = 0,
J(2,7) = (J(1) + 7) mod 2 = (0 + 7) mod 2 = 1,
J(3,7) = (1 + 7) mod 3 = 8 mod 3 = 2, ...
J(21,7) = (2 + 7) mod 21 = 9 mod 21 = 9,
J(22,7) = (9 + 7) mod 22 = 16 mod 22 = 16.

Нам же нужно, чтобы последний был 0. Тогда по формуле:

S = (0 − 16) mod 22 = (−16) mod 22 = 6

То есть начать счёт нужно с позиции 6.

Проверка: если расставить всех участников по кругу (0 — хозяин, 1–21 — солдаты) и начать счёт с 6-й позиции, последовательное удаление каждого 7-го приведёт к тому, что последним останется хозяин.

Ответ: надо начинать счёт с 6-го солдата, сидящего по левую руку от хозяина.