Задача о шляпах

Головоломка, привлекшая впоследствии внимание Питера Уинклера (Peter Winkler) из Bell Labs и других ученых американского континента, стала предметом оживленных дискуссий в научных кругах — как среди исследователей из компаний высокотехнологичного сектора, так и на математических и кибернетических отделениях университетов.

Постановка задачи такова: три человека один за другим входят в комнату, и на голову каждому из них надевается красная (К) или синяя (С) шляпа, в зависимости от того, как выпадет монетка — орлом или решкой. Уже находясь в комнате, человек видит цвета шляп двух других играющих, но не цвет собственной шляпы. Игроки не могут никаким образом общаться между собой, однако каждый из них может вслух предположить, какого цвета его шляпа. Если хотя бы один из троих угадает, и никто не выскажет неверное предположение, каждый из игроков получит по $1 млн. Если никто из игроков не угадает цвета своей шляпы, или хотя бы один выскажет неверное предположение, игроки уходят с пустыми руками.

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

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

На самом же деле, существует стратегия, дающая игрокам 75-процентный шанс на успех. По ней игрок, видя цвета шляп своих коллег по команде, должен сделать следующие выводы: если цвета шляп у них одинаковы, то цвет его шляпы — другой. Если же шляпы разного цвета, игрок не должен высказывать свое предположение.

Перечислив все возможные комбинации цветов шляп игроков, легче понять смысл стратегии. Для трех человек существует восемь различных сочетаний цветов: ККК, ККС, КСК, СКК, ССК, СКС, КСС и ССС. Первая комбинация означает, что на всех трех игроков надеты красные шляпы, вторая — что на двух надеты красные, а на оставшегося — синяя и т.д.

В шести из восьми возможных сочетаний на двоих из трех игроков надеты шляпы одного цвета, и эти игроки не будут высказывать свое предположение, так как два других по отношению к каждому из них игрока будут иметь шляпы разного цвета, а оставшийся игрок назовет свой цвет шляпы — не такой, как у товарищей по игре. В двух из восьми случаях, у всех троих игроков шляпы одного цвета, и все три выскажут ошибочное предположение. Так что в 6 случаях из 8 игроки получат свои деньги, что составляет 75-процентную вероятность.

При увеличении количества игроков до 7, развитие данной стратегии (по принципу "в большинстве случаев никто не высказывается неверно, в какой-то раз все не правы") позволит выиграть деньги с вероятностью 7/8, с 15 игроками шансы на успех составят 15/16.

Исследователи задались вопросом — могут ли возникать такого рода ситуации в реальной жизни, скажем, на фондовом рынке? Будет ли справедлива вышеизложенная стратегия, когда членам группы доступны лишь не зависящие друг от друга части информации, и каждый из них владеет информацией о других — но не о себе?

Кроме того, идею, лежащую в основе такого рода стратегий, можно выразить в терминах корректирующих кодов, используемых в компакт-дисках, модемах, мобильных телефонах и огромном количестве другой электроники. Сюда относится и контрольная цифра на конце штрих-кода, представляющая сумму всех предыдущих цифр. Области применения корректирующих кодов разнообразны — возможно, именно эта идея приблизит идеальное "цифровое будущее", когда компьютеры и бытовая техника станут удобной повседневностью, а о программных ошибках будут вспоминать как о "темных временах" прогрессивного человечества.

from: http://www.cnews.ru

red. lent.