задачка

[avva]

Отличная задачка от IBM.

Перевод условия: Алиса и Боб играют против казино следующую игру: в каждом раунде Алиса выбирает бит 0/1, потом Боб, потом казино; все выборы публичные. Алиса и Боб выиграли раунд, если все три выбора одинаковые, и проиграли в обратном случае. При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному.

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

При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.

Нужно доказать, что в игр в n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.

Я пока что знаю, как обеспечить 5 побед, а 6 не могу. Буду еще думать.

Прошу не спойлерить - если у вас есть полное решение, дайте ссылку на свой журнал или поместите его на pastebin.com и дайте ссылку туда - это занимает ровно минуту без регистрации.

Update: AAAAAAAAAAAAAAAAAAAAAA!

Comments

[alexeybobkov]

При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.

Ничего не понимаю. Почему? И как в этой стратегии учитывается то, что Боб знает выбор казино?

[alexeybobkov]

А, всё понятно. Прочитал в оригинале)

[korchy.livejournal.com]

Из оригинала не очень ясно, Боб договаривается о стратегии с Алисой уже зная, что украдет ходы казино? Вроде же после кражи договариваться уже ни о чем нельзя.

[avva.livejournal.com]

Это действительно не очень понятно, вы правы. Я исходил из того, что они договариваются, зная, что он украдет. Ваше второе замечание не очень понятно: если бы после кражи они могли договориться, он бы просто передал ей ходы казино, и они бы вдвоем их повторяли и выигралы все раунды. Вся сложность в том, что Боб знает заранее ход казино в каждом раунде, а Алиса не знает.

[kaathewise.livejournal.com]

Это очень напоминает одну известную задачку с карточным фокусом, но там попроще сделать 2/3.

[avva.livejournal.com]

Да, я над той задачкой долго думал лет 10 назад. Но она действительно немного другая.

[ile-eli.livejournal.com]

ну так откройте непосвященным, что за задачка.

[metaguest.livejournal.com]

Интересно что в оригинале Боб просто украл информацию из сейфа, а у Вас подкупил работников.

[ext-2087110.livejournal.com (from livejournal.com)]

Отличная задачка, и правда.
5 из 8 или 6 из 10 - тривиально. а вот 6 из 9 что-то в голову никак не лезет.

[huzhepidarasa.livejournal.com]

А как сделать 5 из 8? У меня почти получается, но не совсем. Что-то я не понимаю.

Упыды: понял уже.

[kaathewise.livejournal.com]

Меня смущает, что они пишут "Alice strategy is too big to be sent explicitly". Ведь достаточно прислать такой же набор битов, как и у Боба -- по 9 бит в 512 строчках. Так даже можно будет автоматически проверить, что все правильно -- достаточно убедиться, что для одинаковых начал Боба и казино начала Алисы тоже совпадают (всего-то построение префиксного дерева из менее чем 512 * 9 вершин).

Или я чего-то не понимаю?

[avva.livejournal.com]

Кажется, вы правы. Возможно, они имеют в виду то, что таккой набор будет не столько стратегией Алисы, сколько приложением ее стратегии; саму стратегию, как функцию от всех возможных префиксов казино и Боба, труднее описать.

Но это еще связано у меня вот с каким сомнением. Тот факт, что они не просят прислать стратегию Алисы, заставляет меня думать, что у них есть простой способ проверить корректность решения только по решению Боба, но я не могу понять, что это может быть за способ. Проверить сам факт сушествования стратегии для Алисы по решению Боба кажется сложной задачей (и если бы они так поступали, то наверняка действительно скорее попросили бы прислать набор Алисы).

Поэтому я склоняюсь к тому, что у них есть на уме какая-то особенно простая и интуитивная стратегия поведения Алисы, к которой подходит какой-то конкретный набор Боба (или один из класса наборов). Что-то вроде примера для 50% - Боб задает правильное значение четных раундов на нечетных - сложнее, но ненамного. Увы, ничего такого я не смог придумать. Я тоскую, потому что типичные стратегии, которые я рассматривал, в которых биты Боба кодируют всякие относительно сложные факты для Алисы, к таким не относятся - если бы такая стратегия была верна, мне непонятно, как они бы проверили мое решение без описания "моего" поведения Алисы.

[alexcohn.livejournal.com]

Тонкость в том, что "стратегия" Алисы ни на что не влияет (кроме конечного результата, конечно). 9х512 бит Боба достаточно; остается показать, что 6 из них в каждой строчке соответствуют 6 битам казино и предсказуемы.

[huzhepidarasa.livejournal.com]

оффтопик: скажите, не могли бы вы разызкать в гугле человека, который убрал sweep-to-switch-tabs gesture из билда хрома для телефонов, и врезать ему хорошенько, от души?

[kaathewise.livejournal.com]

Кстати да.

[fyysik.livejournal.com]

Анатолий, а вы имеете какое-то отношение к гуглевским серч-алгоритмам и интерфейсу серча?

[pesec.livejournal.com]

Только догадка (http://pesec.livejournal.com/76593.html).

[kaathewise.livejournal.com]

В задаче требуется, чтобы 6 выигрышей было в любом случае, то есть, можно считать, что когда Алисе нужно угадать, она никогда не угадывает. При таком рассмотрении, ваше решение аналогично приведенному про четные/нечетные.

[chitatel-lj.livejournal.com]

По моему, решил.
Нерешаемых наборов придумать не смог.
Математически доказать верность решения знаний нету.
http://chitatel-lj.livejournal.com/889.html

[thaere.livejournal.com]

По-моему, решение есть до 8 побед, но надо подумать.

[vigourik.livejournal.com]

Навскидку:
В первых 3х раундах Боб должен выдать число из 3х цифр, которое Алисе нужно, например, вычесть из 6ти значного числа, которое образуется цифрами Алисы и Казино. Вот эти самые получившиеся выигрышные 6 цифр она и фигачит в следующих раундах. :)

Но вычитания, похоже, не хватит. 6 знаков - это 64, а 3 - всего лишь 8. :(

[vigourik.livejournal.com]

Второй вариант: Алиса с Бобом могут договориться какие первые 3 цифры выдаст Алиса. Первые 3 цифры казино Боб тоже знает. И у него есть 3 цифры (8 вариантов) для того, чтобы определить операцию с этими 6ю цифрами для получения искомых 6 цифр выигрышных раундов. :)

[mperv.livejournal.com]

А правда, что при этом получается кодирование 3мя битами любых 6и?

ВСЕ ТОТ ЖЕ НЕ МАТЕМАТИК

[Андрей Чернобровкин (from livejournal.com)]

Хорошо, иначе - он каждый нечетный нечетный(пардон за масло масленое) раунд ставит то что должно быть в следующем нечетном четном, т.е. в 1ом что ставить в 3ем а 5ом что в 7мом, и того гарантия 2 верных на нечетных раундах.

Re: ВСЕ ТОТ ЖЕ НЕ МАТЕМАТИК

[mperv.livejournal.com]

У нас всего девять ходов. Я думаю, для Вас не составит большого труда, написать на каждый из ходов как ходит Алиса и как ходит Боб. Еще обычно вторым шагом полезно попытаться придумать вариант казино на котором стратегия Боба и Алисы даст плохой результат, но мне кажется, что Вам для осознания ошибки хватит первого шага.

[levtsn.livejournal.com]

я только из английской понял

боб делает правильный ход если ход алисы правилен,
или следующий ход казино если ход алисы не правилен.
я так понимаю она его ходы видит
вроде как 75% успех

[yoksel-moksel.livejournal.com]

Я так понимаю, что задача не надеяться на случайные угадывания Алисы, а гарантировать не менее 6 побед

[raindog-2.livejournal.com]

Это немного измененный (упрощенный?) вариант старой задачи, уже забыл, кто ее придумал, но я с ней когда-то долго повозился, лет 6 назад, пока решил. Вот вариант задачи, как я ее знал:

Антон и Борис идут в казино и там им предлагают игру. Они одновременно и независимо делают предсказание и бросают (честную) монетку. Если они оба угадали - выигрывают очко. Если хотя бы один не угадал - ничего не выигрывают. И так и продолжают бросать монетку много раз, N. Они могут договориться перед игрой о стратегии.

Но теперь вот что - они узнают, что на Антона перед самым началом игры сойдет озарение, и он сможет точно предсказать результаты заранее по всей серии N. Какую наилучшую стратегию выбрать А и Б и сколько процентов очков могут они набрать, в среднем? Можно ли создать стратегию, которая даст 70% очков?