Предлагаем для вашего математического досуга старинную задачу из книги «В царстве смекалки» Емельяна Игнатьевича Игнатьева:
«В корчме стояло четыре стола, образуя четырёхугольник. Проголодавшиеся, возвращавшиеся с манёвров солдаты остановились там в числе 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.
Нам же нужно, чтобы последний был 0. Тогда по формуле:
То есть начать счёт нужно с позиции 6.
Проверка: если расставить всех участников по кругу (0 — хозяин, 1–21 — солдаты) и начать счёт с 6-й позиции, последовательное удаление каждого 7-го приведёт к тому, что последним останется хозяин.
Ответ: надо начинать счёт с 6-го солдата, сидящего по левую руку от хозяина.