Белый дом США озадачил пользователей интернета головоломкой из теории игр

Заместитель технического директора администрации президента США Эд Фелтен (Ed Felten) опубликовал своё первое обращение, задав читателям блога Белого дома головоломку из сферы теории игр. На запись Фелтона обратило внимание издание «Медуза».

Эд Фелтен

Вспоминая о том, как в декабре 2014 года Барак Обама стал первым президентом США, написавшим компьютерную программу, Фелтен рассказал и о собственных успехах в программировании. Он начал кодить в 1977 году, задолго до времён, когда дети имели широкий доступ к вычислительным машинам, а написание программ в стиле «Hello World» стало доброй традицией начинающих программистов.

Фелтен подчеркнул, что компьютерная наука не ограничивается написанием кода, и предложив читателям решить головоломку «на тему кооперации». По его словам, это упрощённая версия задачи, которую он узнал от одного из своих студентов.

Элис и Боб играют в игру. Они в одной команде, поэтому они выигрывают или проигрывают вместе. Перед началом игры они могут договориться о выборе стратегии.

Когда игра начинается, Элис и Боб расходятся по двум звуконепроницаемым комнатам — они не могут общаться друг с другом. Каждый из них бросает монетку и записывает, что выпало: решка или орёл (никакого жульничества: это должен быть честный бросок, и они должны позже рассказать правду). Потом Элис пытается угадать, что выпало у Боба, и записывает догадку на бумажку. То же самое делает и Боб.

Если хотя бы одна из догадок окажется верной, Элис и Боб выигрывают. Если они оба ошиблись, они проиграли.

Загадка вот в чём: вы можете придумать стратегию, по которой Элис и Боб будут гарантированно выигрывать каждый раз?

Фелтен привёл пример неработающей стратегии: если Алиса и Боб будут всегда ожидать выпадения орла друг у друга, то в 25% случаев они будут ошибаться, так как решка или орёл выпадают с равной вероятностью. Представитель Белого дома пообещал, что будет публиковать подсказки в своём твиттере.

Часть пользователей пожаловались на сложность задачи, в то время как те, кто владеет математикой, заявили, что уже нашли верное решение.

For some reason this question is bloody difficult (I blame Monday morning) https://t.co/pZ94BdwQa6 Of course, great initiative from the US.

— Adam Bennett (@iateyourmic) May 18, 2015

This was fun. Took me longer to read the post, than to solve the problem, but then again, I am a mathematician: https://t.co/mfu22rwldB

— fabs(); (@raspofabs) May 18, 2015

Эд Фелтен занял свой пост 11 мая 2015 года. До этого он работал профессором компьютерных наук в Принстонском университете. За свою карьеру Фелтон опубликовал более сотни научных работ и две книги на тему юридического регулирования сферы технологий.