Задача: игра в карты «в уме»
Чтение философского эссе Скотта Ааронсона навеяло стилизованную задачку «как бы про знания». Тема, мягко говоря, не нова, но знакомы с ней далеко не все, и результат может показаться неожиданным.
Миша, Петя и Коля играют в некую карточную игру «колодой» из трех карт - А, Б и В. Правила их игры мы оставим за скобками, но отметим, что игра, как обычно, начинается с раздачи, причем в результате раздачи колода случайным образом распределяется между игроками (то есть каждый получает по одной карте). Нетрудно, разумеется, физически перетасовать колоду из трех карт и раздать по карте каждому из трех игроков. Представим, однако, что игроки забыли колоду карт, и что у них нет при себе ни ручки, ни бумаги, зато есть стандартная игральная кость (кубик с гранями, подписанными от 1 до 6), которой можно пользоваться как генератором случайных чисел. Представим также, что вокруг нет никого, кто мог бы выступить в роли ведущего. Смогут ли три игрока сыграть между собой в карты в уме, как иногда продвинутые люди играют в уме в шахматы?
Понятно, что для начала игрокам придется как-то так раздать воображаемую колоду, чтобы каждый игрок выяснил свою карту, но ничего полезного не узнал про чужие, и чтобы при этом гарантировалось, что все розданные карты - разные.
Задача состоит в том, чтобы предложить по возможности простой и практичный протокол устного обмена информацией между игроками, с помощью которого они смогли бы реализовать случайную сдачу карт. Мы исходим из того, что игроки аккуратны, честны, обладают неплохой памятью и достаточно сообразительны, чтобы четко следовать предложенному протоколу. Игрокам разрешается общаться между собой как вслух (когда каждый слышит то, что говорят другие), так и перешептываясь (когда друг друга слышат двое, а третий их не слышит).
Задача сформулирована для стилизованной колоды из всего трех карт. Я не против обсудить обобщение на колоды любых разумных размеров (например, 36 карт), но это будет уже другая задача. И я, кстати, не утверждаю, что запрошенный протокол вообще существует, хотя бы для минималистской трехкарточной колоды. Если вы считаете, что нужного протокола не существует, - попробуйте убедительно доказать это.
Ответы принимаются, комментарии скрыты.
Убедительные решения предложили: fiviol, xmyruj, madam_y, ...