Задача о чумазых детях

Дети играли на улице, и отец позвал их в дом. Дети собрались около отца. Как легко себе представить, некоторые из них, играя, запачкались; в частности, у некоторых лицо в грязи. Каждый ребёнок может видеть грязь только на лицах других детей, но не на своём собственном. Всё это известно всем, и дети, конечно же, идеальные логики. Отец говорит: «По меньшей мере один из вас испачкался в грязи». И затем: «Те из вас, кто знают, что испачкались, — шаг вперёд». Если никто не делает шаг вперёд, отец повторяет свою команду снова и снова. На определённой итерации все чумазые дети делают шаг вперёд. Когда именно это случится, если испачканы m детей из их общего числа k, и почему?

Оригинальный текст (англ.)[показатьскрыть]

A group of children has been playing outside and they are called back into the house by their father. The children gather round him. As one may imagine, some of them have become dirty from the play. In particular: they may have mud on their face. Children can only see whether other children are muddy, and not if there is any mud on their own face. All this is commonly known, and the children are, obviously, perfect logicians. Father now says: “At least one of you is muddy.” And then: “Will those who know whether they are muddy step forward.” If nobody steps forward, father keeps repeating the request. At some stage all muddy children will step forward. When will this happen if m out of k children in total are muddy, and why?

— van Ditmarsch & Kooi, 2015

При анализе происходящего используется метод математической индукции[1].

• База индукции: если m = 1, то единственный чумазый ребёнок сразу поймёт, что, поскольку остальные дети чистые, то грязен он, и сделает шаг вперёд после первой же соответствующей команды отца. При этом каждый из остальных до этого момента не будет знать, грязен ли сам, и не сделает шаг вперёд.
• Пусть доказано, что для случаев, когда число чумазых детей m не превышает некоторое n, все чумазые дети узнают, что испачкались, ровно к m-й итерации. Тогда в случае n+1 чумазых детей, если к n-й итерации они ещё не знают, испачкались ли они сами, то после этой итерации, видя, что никто не сделал шаг вперёд, каждый из них должен заключить, что число испачканных детей превышает видимое им число чумазых детей n (иначе бы, по предположению индукции, другие чумазые дети сделали бы шаг вперёд), а значит, он сам тоже испачкался.

Это рассуждение демонстрирует, как m детей могут точно понять, что испачкались, к m-й итерации процесса. Однако строгое доказательство того, что никакие другие рассуждения не приведут их к этому выводу раньше, довольно нетривиально[2].

Можно рассмотреть пример m = 2 чумазых детей, Алиса и Боб[3][4].

• До первой команды отца каждый из чумазых детей видит одного другого чумазого ребёнка и понимает, что возможны две ситуации — будем следить за рассуждениями Алисы, Боб рассуждает точно так же:
  • другой ребёнок, Боб, — единственный чумазый, и поскольку Алиса знает, что Боб знает, что есть как минимум один чумазый ребёнок, то Алиса делает вывод, что Боб должен понять, что это он и есть;
  • Алиса и Боб оба чумазые, и тогда для Боба ситуация выглядит так же, как для Алисы, и — заключает Алиса — Боб в этом случае не может быть уверен, что он чумазый.
• Поскольку Алиса не уверена, испачкалась ли она, после первой команды отца она не делает шаг вперёд; Боб поступает так же. Это исключает для Алисы первый из двух вышеупомянутых вариантов, и она приходит к выводу, что она тоже испачкалась, и по 2-й команде отца делает шаг вперёд, как и Боб.

Для m = 3 детей — Алиса, Боб, Кэролайн[4]:

• В начале Алиса видит, что Боб и Кэролайн чумазые. Она знает, что они знают, что есть хотя бы один чумазый ребёнок; более того, она знает, что они знают, что каждый из них знает, что есть хотя бы один чумазый ребёнок, поэтому она понимает, что если сама она чистая, то Боб и Кэролайн проводят те рассуждения, которые были приведены выше для случая двух чумазых детей.
• После первой команды отца никто не делает шаг вперёд. Алиса по-прежнему не знает, чумазая ли она сама, но теперь она знает, что если она чистая, то Боб и Кэролайн (по приведённым для случая m = 2 рассуждениям) знают каждый про себя, что он сам испачкан.
• После второй команды отца никто не делает шаг вперёд, и Алиса понимает, что она не может быть чистой сама, так что по третьей команде она делает шаг вперёд.

В решении задачи и моделировании рассуждений детей ключевую роль играет их знание о том, что́ знают другие участники процесса, и, в частности, тот факт, что когда при очередной команде отца никто не делает шаг вперёд, это равносильно публичному извещению (подобному заявлению отца о том, что есть как минимум один чумазый ребёнок) о том, что до этого момента никто из детей не знал, испачкался он или нет. Также важно, что дети не лгут, рассуждают идеально логично, и эти факты тоже известны всем, то есть могут использоваться в рассуждениях — в том числе в моделировании рассуждений одних участников другими. Рассуждения существенно опираются на то, что каждый из участников знает, что каждый знает, что каждый знает ... содержание начального заявления отца и результаты его команд сделать шаг вперёд, и эта цепочка может быть сделана достаточно длинной. Это так, поскольку эти факты являются общим знанием — верны цепочки «каждый знает, что каждый знает, что...» сколь угодно большой длины. Концепция общего знания важна в эпистемической логике, и задача о чумазых детях — классический пример, который иллюстрирует содержание этого понятия и важность других положений, используемых в решении[5].

Похожая задача, не включавшая, однако, синхронизацию, то есть чётко определённые моменты для обмена информацией (такие как команды отца выйти вперёд), встречалась ещё в комментариях к немецкому переводу 1832 года знаменитого сатирического романа «Гаргантюа и Пантагрюэль». Известной же эта задача (как в варианте без синхронизации, так и с ней) стала в середине XX века вместе с другими задачами, подразумевавшими анализ информированности и рассуждений одних участников другими[1].

Есть множество вариантов условий задачи, логически эквивалентных, но отличающихся антуражем[6]: например, вместо измазанных в грязи детей в условии могут фигурировать неверные жёны, о неверности каждой из которой знают все, кроме её собственного мужа, — в этом случае в первый день делается публичное объявление, что в городе есть неверные жёны, и муж должен наказать жену в ту же ночь, как он поймёт, что она неверна (либо, наоборот, жёны наказывают неверных мужей)[7].

В ещё одном варианте фигурируют голубоглазые островитяне[6] — религия обязует каждого островитянина совершить самоубийство в ближайшую полночь, если он узнает цвет своих глаз, и отправной точкой задачи служит реплика посетителя острова, из которой следует, что на острове есть хотя бы один голубоглазый житель. В этом антураже задачу также формулируют как парадокс: рассуждение по индукции показывает, что если на острове m голубоглазых островитян, то в m-ю полночь все они совершат самоубийство, даже если m велико — но почему, ведь, казалось бы, посетитель не сообщил островитянам ничего нового, ведь они каждый день видят множество голубоглазых соплеменников? Как следует из сказанного выше, разгадка парадокса в том, что до озвученной во всеуслышание реплики посетителя цепочки «любой островитянин знает, что любой знает, что любой знает ..., что на острове есть голубоглазые» не достигали длины, достаточной для выведения информации о цвете собственных глаз[4][2]. При формулировке задачи в этом виде особенно важно аккуратно составить систему правил для туземцев так, чтобы не дать им возможности обойти их и избежать печального исхода[8].

• Hans van Ditmarsch, Barteld Kooi. Muddy Children // One Hundred Prisoners and a Light Bulb. — Springer, 2015. — P. 21—32. — Errata. — ISBN 9783319166940.
• С. Кузнецов. Знание — сила! // Квант. — 2017. — № 6. — С. 21—24.