?

Log in

задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [окт. 6, 2013|08:33 pm]
Anatoly Vorobey
[Tags|]

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

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

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

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

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

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

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

Update: AAAAAAAAAAAAAAAAAAAAAA!
СсылкаОтветить

Comments:
[User Picture]From: alexeybobkov
2013-10-06 06:46 pm
При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.

Ничего не понимаю. Почему? И как в этой стратегии учитывается то, что Боб знает выбор казино?
(Ответить) (Thread)
[User Picture]From: alexeybobkov
2013-10-06 06:53 pm
А, всё понятно. Прочитал в оригинале)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: korchy
2013-10-06 07:04 pm
Из оригинала не очень ясно, Боб договаривается о стратегии с Алисой уже зная, что украдет ходы казино? Вроде же после кражи договариваться уже ни о чем нельзя.
(Ответить) (Thread)
[User Picture]From: avva
2013-10-06 07:06 pm
Это действительно не очень понятно, вы правы. Я исходил из того, что они договариваются, зная, что он украдет. Ваше второе замечание не очень понятно: если бы после кражи они могли договориться, он бы просто передал ей ходы казино, и они бы вдвоем их повторяли и выигралы все раунды. Вся сложность в том, что Боб знает заранее ход казино в каждом раунде, а Алиса не знает.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: kaathewise
2013-10-06 07:07 pm
Это очень напоминает одну известную задачку с карточным фокусом, но там попроще сделать 2/3.
(Ответить) (Thread)
[User Picture]From: avva
2013-10-06 07:09 pm
Да, я над той задачкой долго думал лет 10 назад. Но она действительно немного другая.
(Ответить) (Parent) (Thread)
From: metaguest
2013-10-06 11:30 pm
Интересно что в оригинале Боб просто украл информацию из сейфа, а у Вас подкупил работников.
(Ответить) (Thread)
From: ext_2087110
2013-10-07 12:37 am
Отличная задачка, и правда.
5 из 8 или 6 из 10 - тривиально. а вот 6 из 9 что-то в голову никак не лезет.



(Ответить) (Thread)
From: huzhepidarasa
2013-10-08 01:08 pm
А как сделать 5 из 8? У меня почти получается, но не совсем. Что-то я не понимаю.

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

Edited at 2013-10-09 06:38 (UTC)
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
(Удалённый комментарий)
[User Picture]From: kaathewise
2013-10-07 05:54 am
Меня смущает, что они пишут "Alice strategy is too big to be sent explicitly". Ведь достаточно прислать такой же набор битов, как и у Боба -- по 9 бит в 512 строчках. Так даже можно будет автоматически проверить, что все правильно -- достаточно убедиться, что для одинаковых начал Боба и казино начала Алисы тоже совпадают (всего-то построение префиксного дерева из менее чем 512 * 9 вершин).

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

Edited at 2013-10-07 07:34 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2013-10-07 04:18 pm
Кажется, вы правы. Возможно, они имеют в виду то, что таккой набор будет не столько стратегией Алисы, сколько приложением ее стратегии; саму стратегию, как функцию от всех возможных префиксов казино и Боба, труднее описать.

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

Поэтому я склоняюсь к тому, что у них есть на уме какая-то особенно простая и интуитивная стратегия поведения Алисы, к которой подходит какой-то конкретный набор Боба (или один из класса наборов). Что-то вроде примера для 50% - Боб задает правильное значение четных раундов на нечетных - сложнее, но ненамного. Увы, ничего такого я не смог придумать. Я тоскую, потому что типичные стратегии, которые я рассматривал, в которых биты Боба кодируют всякие относительно сложные факты для Алисы, к таким не относятся - если бы такая стратегия была верна, мне непонятно, как они бы проверили мое решение без описания "моего" поведения Алисы.
(Ответить) (Parent) (Thread) (Развернуть)
From: huzhepidarasa
2013-10-07 01:47 pm
оффтопик: скажите, не могли бы вы разызкать в гугле человека, который убрал sweep-to-switch-tabs gesture из билда хрома для телефонов, и врезать ему хорошенько, от души?
(Ответить) (Thread)
[User Picture]From: kaathewise
2013-10-07 01:56 pm
Кстати да.
(Ответить) (Parent) (Thread)
[User Picture]From: fyysik
2013-10-07 07:04 pm
Анатолий, а вы имеете какое-то отношение к гуглевским серч-алгоритмам и интерфейсу серча?
(Ответить) (Thread)
From: pesec
2013-10-08 04:34 am
Только догадка.
(Ответить) (Thread)
[User Picture]From: kaathewise
2013-10-08 06:05 am
В задаче требуется, чтобы 6 выигрышей было в любом случае, то есть, можно считать, что когда Алисе нужно угадать, она никогда не угадывает. При таком рассмотрении, ваше решение аналогично приведенному про четные/нечетные.
(Ответить) (Parent) (Thread) (Развернуть)
From: chitatel_lj
2013-10-08 09:01 am
По моему, решил.
Нерешаемых наборов придумать не смог.
Математически доказать верность решения знаний нету.
http://chitatel-lj.livejournal.com/889.html
(Ответить) (Thread)
[User Picture]From: thaere
2013-10-08 11:43 am
По-моему, решение есть до 8 побед, но надо подумать.
(Ответить) (Thread)
[User Picture]From: vigourik
2013-10-08 05:36 pm
Навскидку:
В первых 3х раундах Боб должен выдать число из 3х цифр, которое Алисе нужно, например, вычесть из 6ти значного числа, которое образуется цифрами Алисы и Казино. Вот эти самые получившиеся выигрышные 6 цифр она и фигачит в следующих раундах. :)

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

Edited at 2013-10-08 17:41 (UTC)
(Ответить) (Thread)
[User Picture]From: vigourik
2013-10-08 05:58 pm
Второй вариант: Алиса с Бобом могут договориться какие первые 3 цифры выдаст Алиса. Первые 3 цифры казино Боб тоже знает. И у него есть 3 цифры (8 вариантов) для того, чтобы определить операцию с этими 6ю цифрами для получения искомых 6 цифр выигрышных раундов. :)
(Ответить) (Thread)
[User Picture]From: mperv
2013-10-08 07:23 pm
А правда, что при этом получается кодирование 3мя битами любых 6и?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: Андрей Чернобровкин
2013-10-09 10:51 am

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

Хорошо, иначе - он каждый нечетный нечетный(пардон за масло масленое) раунд ставит то что должно быть в следующем нечетном четном, т.е. в 1ом что ставить в 3ем а 5ом что в 7мом, и того гарантия 2 верных на нечетных раундах.
(Ответить) (Thread)
[User Picture]From: mperv
2013-10-09 11:49 am

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

У нас всего девять ходов. Я думаю, для Вас не составит большого труда, написать на каждый из ходов как ходит Алиса и как ходит Боб. Еще обычно вторым шагом полезно попытаться придумать вариант казино на котором стратегия Боба и Алисы даст плохой результат, но мне кажется, что Вам для осознания ошибки хватит первого шага.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: levtsn
2013-10-10 03:00 am
я только из английской понял

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

Edited at 2013-10-10 03:03 (UTC)
(Ответить) (Thread)
[User Picture]From: yoksel_moksel
2013-10-10 12:58 pm
Я так понимаю, что задача не надеяться на случайные угадывания Алисы, а гарантировать не менее 6 побед
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: raindog_2
2013-10-11 12:36 am
Это немного измененный (упрощенный?) вариант старой задачи, уже забыл, кто ее придумал, но я с ней когда-то долго повозился, лет 6 назад, пока решил. Вот вариант задачи, как я ее знал:

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

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