задачка

[avva]

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

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

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

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

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

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

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

Update: AAAAAAAAAAAAAAAAAAAAAA!

Comments

[alexeybobkov]

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

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

[alexeybobkov]

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

[avva.livejournal.com]

Неужели я так плохо перевел? :)

[korchy.livejournal.com]

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

[avva.livejournal.com]

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

[kaathewise.livejournal.com]

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

[avva.livejournal.com]

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

[korchy.livejournal.com]

Если они обговаривают стратегию, зная, что Бобу будут известны ходы казино, 6 из 9 решается, как мне кажется, достаточно влоб.

[avva.livejournal.com]

Очень может быть. У меня пока не получилось.

[korchy.livejournal.com]

Поделиться соображениями? Я не знаю, что такое pastebin :)

[bravchick.livejournal.com]

Согласен. Я у себя поместил подсказку для любителей спойлеров
http://bravchick.livejournal.com/67808.html

[alexeybobkov]

Хорошо, но слишком сокращённо :)

[ile-eli.livejournal.com]

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

[kaathewise.livejournal.com]

Вот в таком виде она была на ММО в 2004 году:

Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса --- угадать масть как можно большее число раз.

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

Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем a) 19 карт; б) 23 карты?

[avva.livejournal.com]

Здесь лучше не надо, спасибо :)

[metaguest.livejournal.com]

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

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

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

[southwest]

Как я написал выше, в 'решении' есть проблемы. Я их постараюсь исправить.

[avva.livejournal.com]

Но если исправите, не пишите сюда решение, пожалуйста - я постарался скрыть комментарии выше, не читая, совсем не хочу спойлеров. Напишите у себя и дайте ссылку.

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

Как бы не оказалось, что решение можно получить только вычислительным путем, путем составления множества из 512 9-битных векторов, а решения, суть которого можно объяснить человеку - нет.
Ну, бывают такие задачи.

[kaathewise.livejournal.com]

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

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

[avva.livejournal.com]

Я тоже думал об этом, и даже написал программку, чтобы попробовать несколько вариантов - пока безрезультатно. Тут дело в том, что для такого решения все равно нужно "умом" придумать стратегию Алисы, под которую потом подобрать решение (если получится) - перебирать все возможные стратегии слишком тяжело.

[huzhepidarasa.livejournal.com]

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

[kaathewise.livejournal.com]

Кстати да.

[avva.livejournal.com]

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

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

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