Неожиданное заочное знакомство

29.06.2025 г. я получил письмо от неизвестного мне до тех пор Акакия Меликидзе (Akakii Melikidze, akakii.fx@gmail.com) такого содержания: «Уважаемый Анатолий Абрамович! Мне «попалась» статья: Мазин М.А., Шалыто А.А. Преступники и автоматы // Мир ПК. 2004, № 9, с. 82-84 (https://www.osp.ru/pcworld/2004/09/168726). В ней Вы пишите: «Эта задача известна как «Задача о преступниках». Авторы узнали ее от Н.Н. Шамгунова трехкратного чемпиона Урала по программированию, который на сайте https://is.ifmo.ru опубликовал восемь задач на сообразительность (https://is.ifmo.ru/reflections/problems/), среди которых обсуждаемая задача шестая».

В при этом не было указано, когда Шамгунов опубликовал на Вашем сайте эту задачу, а также не были указаны источник и ее автор.

Хочу поделиться с Вами подробностями этой задачи, которые могут быть Вам интересны.

1. Эта задача имеет много вариантов, но, условно говоря, все они делятся на две группы: базовый вариант и различные его усложнения. Автор базового варианта неизвестен, но есть утверждения, что его слышали от датского специалиста по компьютерным наукам по имени Peter Bro Miltersen ещё в 90-х годах прошлого века. Я лично сомневаюсь в этом, так как, во-первых, публикации от имени самого Miltersen`а с упоминанием этой задачи отсутствуют, а, во-вторых, Miltersen является автором очень похожей задачи (https://en.wikipedia.org/wiki/100_prisoners_problem). Вероятно, именно по это причине и возникла путаница.

2. Первое упоминание этой задачи в Интернете, скорее всего, было в 2002 г. на сайте IBM: https://research.ibm.com/haifa/ponderthis/challenges/July2002.html.

После этого эта задача начала жить своей жизнью. Так, в частности, в 2003 г. ее рассказали по радио.

Вот страница выпуска радиопередачи 2020 г. (https://www.cartalk.com/radio/puzzler/prisoners-and-light-switch), в котором этот выпуск 2003 г. был повторен. К сожалению, я не смог найти ссылку на оригинальный выпуск, но уверен, что он был в 2003 г. – я слушал эту передачу в прямом эфире, и хорошо помню эту задачу еще с тех пор.

При этом отмечу, что формулировки задачи несколько различаются, но при этом во всех формулировках, которые мне попадались, ключевым условием было то, что заключенных для допросов выбирают в случайном порядке, а график допросов может быть нерегулярным – в один день несколько допросов, а в другой – ни одного. К сожалению, в формулировке, опубликованной Шамгуновым, это условие было изменено, и Вы со своим соавтором решали задачу про регулярные допросы. В оригинальной (нерегулярной) постановке задачи Ваше решение (главарем считается преступник, попавший в карцер в первый день), разумеется, не работает.

Также надо иметь в виду, что если математизировать «популярное» изложение задачи, которое было дано в радиопередаче: «But, given enough time, everyone will eventually visit the switch room as many times as everyone else», то получится условие: существует такой момент времени, такой что в этот момент число допросов всех заключенных равны между собой. Так вот, в такой формулировке задача не имеет решения. В 2003 г. после того, как услышал ее по радио, я доказал, что решения у этой «популярной» версии нет, и забыл про эту задачу. Но потом, по прошествии лет, задача снова попалась, уже в правильной – оригинальной формулировке.

Правильное условие: для каждого заключенного и любого наперед заданного целого числа N существует такой момент времени t, в который число его допросов равно N. Это условие выполняется для конечного числа заключенных. Обобщение этого условия и всей задачи на счетное число заключенных также весьма интересно.

Много интересных аспектов рассматриваемой задачи (в том числе автоматный подход) освещено в работе: van Ditmarsch H. et al. One Hundred Prisoners and a Lightbulb // Logic and Computation. 2010. https://cdn.aaai.org/ocs/1234/1234-7399-1-PB.pdf

Обобщение на N комнат приведено в работе: Kane D.M., Kominers S.D. Prisoners, Rooms, and Light Switches // The Electronic Journal of Combinatorics. 2021. V. 28. Issue 1. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p27.

Замечательные иллюстрации к рассматриваемой задаче можно найти здесь: https://www.ou.nl/documents/40554/3634475/INF_Webinar_Logische_Puzzels.pdf».

На следующий день пришло еще одно письмо от Акакия: «Я сейчас в процессе изучения Вашего сайта https://is.ifmo.ru/, а конкретнее – изучаю работы по генерации автоматов при помощи генетических алгоритмов.

Дело в том, что некоторые из моих задач требуют работы с парсерами – синтаксическими анализаторами. Все, кто когда-либо писал парсеры, думаю, знает, что это действительно впечатляющая работа. Изначально возникла такая мысль: можно ли сделать систему, которая рисует исходный текст и результат парсинга, и попробовать обучиться этим парам, чтобы потом парсить новые строки уже самостоятельно?

Трансформеры, да и вообще любой генеративный подход на основе нейросетей, как мне кажется, очень плохо подходят для этой задачи. Это именно автоматная задача.

Вот конкретный пример: представьте, что мы создаем библиометрическую систему, которая ставит задачу просмотреть набор научных статей и понять, кто на кого ссылается. Как понять, что часть текста в списке одной статьи литературы является ссылкой на другую часть текста – заголовок другой статьи? Сейчас это делают очень сложные парсеры – они учитывают не только разнообразие форматов ссылок/заголовков, но и то, что и там, и там неизбежны ошибки. Парсеры сейчас пишутся вручную. Вот и родилась мысль: можно ли научить систему парсить, обучая ее на примерах?

Зная, как работают парсеры – их связь с автоматами, – я примерно понял, что нужно делать: запускать рост автоматов и наблюдать за близостью получаемых строк, которые производят (у строк квадратичные по сложности функции, измеряющие близость, кажется), и затем применить процедуру «генетического отбора». Не знаю, на самом деле сработало бы это – до сих пор не было времени на то, чтобы серьезно заняться экспериментами. И вот недавно набрел на работы Вашей группы по генетическим алгоритмам для генерации автоматов. В общем, у меня много желаний во всем разобраться, но времени мало.

Акккию родился в 1977 г. Он учился физике в Тбилисском государственном университете и в МФТИ. Акакий PhD Принстонского университета по физике. Он завоевывал первые призы на грузинской олимпиаде студентов по физике, а также на олимпиаде по физике в МФТИ. Имел Princeton University Joseph Henry Prize. Member of the American Physical Society.

Пусть у него все будет хорошо, и он будет счастлив.

01.07.2025.