Головоломка за $1 млн

Головоломка за $1 млн. Логическая головоломка, представленная впервые в 1998 году в диссертации профессора Тодда Эберта (Todd Ebert) из Калифорнийского университета, не перестает будоражить умы математиков и кибернетиков. Столь пристальное внимание, в частности, объясняется тем, что в основе решения головоломки лежит идея так называемых корректирующих кодов, или кодов с исправлением ошибок, используемых в персональных компьютерах и электронике. Головоломка привлекла внимание ученых американского континента и стала предметом оживленных дискуссий в научных кругах – как среди исследователей из компаний высокотехнологичного сектора, так и на математических и кибернетических отделениях университетов. Постановка задачи такова: три человека один за другим входят в комнату, и на голову каждому из них надевается красная (К) или синяя (С) шляпа, в зависимости от того, как выпадет монетка – орлом или решкой. Уже находясь в комнате, человек видит цвета шляп двух других играющих, но не видит цвет собственной шляпы. Игроки не могут никаким образом общаться между собой, однако каждый из них может вслух предположить, какого цвета его шляпа.

Если хотя бы один из троих угадает, и никто не выскажет неверное предположение – каждый из игроков получит по 1 миллиону долларов! Если никто из игроков не угадает цвета своей шляпы, или хотя бы один выскажет неверное предположение, игроки уходят с пустыми руками.

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

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

Дайте шляпе шанс!

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

Первая комбинация означает, что на всех трех игроках красные шляпы, вторая – что на двух красные, а на оставшемся синяя и т.д.

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

Свет корректирующего кода

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

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