и в заключение
Oct. 9th, 2013 11:38 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaТеперь у меня есть "интуитивное" решение задачи про Алису, Боба и Казино. То самое, которого так долго ждали большевики и в поисках которого я вместе, кажется, с немалым числом читателей этого дневника бились головой об стенку в последние несколько дней. То самое, по поводу которого я уже решил было, что оно не существует.
Это не мое решение. Его придумал коллега из Гугла. Мне досадно, что все трюки, которые оно использует, я тоже пытался применить, но оно их все соединяет с еще большей хитроумностью и извращенностью, которые от меня ускользнули. Что я могу сказать - в Гугле работают умные люди.
(додумался бы я до этого решения, если бы еще несколько дней бился головой об стенку? Не знаю, но скорее нет, чем да)
Да, кстати, хоть оно, мягко скажем, не тривиальное, но действительно работает. Я проверил не только на глазок, но и программой, которую я написал для проверки решений.
Ну что, хотите узнать? Дальше идут одни спойлеры!
СПОЙЛЕРЫ
СПОЙЛЕРЫ
СПОЙЛЕРЫ
Итак, у нас есть 9 битов Казино, которые мы обозначим A-BCD-EFG-HI. Для простоты предположим, что в первом бите всегда есть ошибка, этого невозможно избежать в любом случае.
1. Сначала опишем "базовый алгоритм", который все уже пробовали. В своем бите A Боб обозначает наиболее частый бит среди BCD, и Алиса играет его в BCD. Если у нее есть одна ошибка, Боб использует свой бит на месте ошибки, чтобы передать самый частый бит среди EFG. Если там есть одна ошибка, то Боб использует этот бит, чтобы закодировать HI вместе, предполагая, что они одинаковы.
Этот алгоритм сработает, если BCD не все одинаковы, EFG не все одинаковы, и HI = 00 или 11. Кроме того, если BCD или EFG все одинаковы, он тоже сработает с легкими модификациями, и тогда даже не нужно, чтобы HI были одинаковы. Например, если BCD одинаковы, то у нас после BCD есть еще две ошибки в запасе: мы можем использовать E для большинства FGH, и тем же способом бит ошибки внутри FGH для I (а если бита ошибки нет, то и не надо, наплевать на I). А если EFG одинаковы, то у нас есть одна ошибка в запасе на HI, так что просто пользуемся H чтобы просигналить I.
2. Таким образом, мы пользуемся "базовым алгоритмом", и он работает во всех случаях, кроме HI=01 или HI=10. Более того, в этом случае мы можем предположить, что BCD не одинаковы и EFG не одинаковы, иначе базовый алгоритм все равно работает.
3. Теперь рассмотрим случай, когда HI=01, а EFG - любая неодинаковая комбинация, кроме 010 и 101. Таких комбинаций есть четыре, так что возможности для EFG-HI такие: 001-01, 110-01, 011-01, 100-01. Мы отклонимся от базового алгоритма следующим образом:
- в случаях 001-01 и 110-01 Боб специально делает ошибку во втором бите (F). Эта ошибка говорит Алисе (которая не ошиблась в этом бите, и поэтому знает, что это не "ошибочный бит" Боба в базовом алгоритме), что следующий бит противоположен плану, по которому она шла, и вдобавок в конце идет 01.
- в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.
- в обоих случаях после специальной ошибки Боба Алиса без дополнительных ошибок заканчивает игру.
4. У нас остались следующие неохваченные комбинации EFG-HI. Во-первых, 010-01 и 101-01, а во-вторых любые (но не все одинаковые) значения EFG, плюс HI=10. Все остальные варианты мы рассмотрели.
5. В этих оставшихся случаях мы меняем стратегию на BCD, и пользуемся трюком, который позволяет сделать две ошибки, но вытащить целых три бита. Это делается следующим образом. У нас есть два способа сделать две ошибки на BCD и закодировать там два бита:
- дать в бите A неправильное большинство для BCD, чтобы Алиса сделала две ошибки, и использовать эти два бита Боба.
- дать в бите А правильное большинство, Алиса делает одну ошибку (и Боб имеет в ней свой бит), но Боб делает еще одну дополнительную ошибку, причем он может выбрать одно из двух правильных мест, и этот выбор дает ему еще один бит.
Наконец, выбор одной из этих двух стратегий дает нам третий бит. После того, как Алиса ответила свои BCD согласно биту A Боба, она может определить, перешли ли мы на стратегию "две ошибки", на какую из двух, и узнать все три бита.
6. Эти три бита теперь дают нам возможность определить EFG-HI без единой ошибки. Первый бит определяет, верно ли, что EFG=010 или 101. Если это так, то второй бит скажет, какая из этих версий верна, а третий определит, HI=10 или HI=01. Если это не так, то обязательно HI=10, а для EFG осталось четыре возможности 001, 110, 011, 100,
и второй и третий бит вместе определяют, какая из них верна.
Уф. Ну как? Прекрасно, верно ведь?
Это не мое решение. Его придумал коллега из Гугла. Мне досадно, что все трюки, которые оно использует, я тоже пытался применить, но оно их все соединяет с еще большей хитроумностью и извращенностью, которые от меня ускользнули. Что я могу сказать - в Гугле работают умные люди.
(додумался бы я до этого решения, если бы еще несколько дней бился головой об стенку? Не знаю, но скорее нет, чем да)
Да, кстати, хоть оно, мягко скажем, не тривиальное, но действительно работает. Я проверил не только на глазок, но и программой, которую я написал для проверки решений.
Ну что, хотите узнать? Дальше идут одни спойлеры!
СПОЙЛЕРЫ
СПОЙЛЕРЫ
СПОЙЛЕРЫ
Итак, у нас есть 9 битов Казино, которые мы обозначим A-BCD-EFG-HI. Для простоты предположим, что в первом бите всегда есть ошибка, этого невозможно избежать в любом случае.
1. Сначала опишем "базовый алгоритм", который все уже пробовали. В своем бите A Боб обозначает наиболее частый бит среди BCD, и Алиса играет его в BCD. Если у нее есть одна ошибка, Боб использует свой бит на месте ошибки, чтобы передать самый частый бит среди EFG. Если там есть одна ошибка, то Боб использует этот бит, чтобы закодировать HI вместе, предполагая, что они одинаковы.
Этот алгоритм сработает, если BCD не все одинаковы, EFG не все одинаковы, и HI = 00 или 11. Кроме того, если BCD или EFG все одинаковы, он тоже сработает с легкими модификациями, и тогда даже не нужно, чтобы HI были одинаковы. Например, если BCD одинаковы, то у нас после BCD есть еще две ошибки в запасе: мы можем использовать E для большинства FGH, и тем же способом бит ошибки внутри FGH для I (а если бита ошибки нет, то и не надо, наплевать на I). А если EFG одинаковы, то у нас есть одна ошибка в запасе на HI, так что просто пользуемся H чтобы просигналить I.
2. Таким образом, мы пользуемся "базовым алгоритмом", и он работает во всех случаях, кроме HI=01 или HI=10. Более того, в этом случае мы можем предположить, что BCD не одинаковы и EFG не одинаковы, иначе базовый алгоритм все равно работает.
3. Теперь рассмотрим случай, когда HI=01, а EFG - любая неодинаковая комбинация, кроме 010 и 101. Таких комбинаций есть четыре, так что возможности для EFG-HI такие: 001-01, 110-01, 011-01, 100-01. Мы отклонимся от базового алгоритма следующим образом:
- в случаях 001-01 и 110-01 Боб специально делает ошибку во втором бите (F). Эта ошибка говорит Алисе (которая не ошиблась в этом бите, и поэтому знает, что это не "ошибочный бит" Боба в базовом алгоритме), что следующий бит противоположен плану, по которому она шла, и вдобавок в конце идет 01.
- в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.
- в обоих случаях после специальной ошибки Боба Алиса без дополнительных ошибок заканчивает игру.
4. У нас остались следующие неохваченные комбинации EFG-HI. Во-первых, 010-01 и 101-01, а во-вторых любые (но не все одинаковые) значения EFG, плюс HI=10. Все остальные варианты мы рассмотрели.
5. В этих оставшихся случаях мы меняем стратегию на BCD, и пользуемся трюком, который позволяет сделать две ошибки, но вытащить целых три бита. Это делается следующим образом. У нас есть два способа сделать две ошибки на BCD и закодировать там два бита:
- дать в бите A неправильное большинство для BCD, чтобы Алиса сделала две ошибки, и использовать эти два бита Боба.
- дать в бите А правильное большинство, Алиса делает одну ошибку (и Боб имеет в ней свой бит), но Боб делает еще одну дополнительную ошибку, причем он может выбрать одно из двух правильных мест, и этот выбор дает ему еще один бит.
Наконец, выбор одной из этих двух стратегий дает нам третий бит. После того, как Алиса ответила свои BCD согласно биту A Боба, она может определить, перешли ли мы на стратегию "две ошибки", на какую из двух, и узнать все три бита.
6. Эти три бита теперь дают нам возможность определить EFG-HI без единой ошибки. Первый бит определяет, верно ли, что EFG=010 или 101. Если это так, то второй бит скажет, какая из этих версий верна, а третий определит, HI=10 или HI=01. Если это не так, то обязательно HI=10, а для EFG осталось четыре возможности 001, 110, 011, 100,
и второй и третий бит вместе определяют, какая из них верна.
Уф. Ну как? Прекрасно, верно ведь?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-10-09 08:55 pm (UTC)no subject
Date: 2013-10-10 02:20 pm (UTC)no subject
Date: 2013-10-09 09:19 pm (UTC)no subject
Date: 2013-10-09 09:38 pm (UTC)no subject
Date: 2013-10-09 10:41 pm (UTC)no subject
Date: 2013-10-09 11:09 pm (UTC)no subject
Date: 2013-10-10 03:45 am (UTC)no subject
Date: 2013-10-10 08:22 am (UTC)no subject
Date: 2013-10-09 11:50 pm (UTC)no subject
Date: 2013-10-10 06:31 am (UTC)no subject
Date: 2013-10-11 01:20 am (UTC)Поспрашиваю
no subject
Date: 2013-10-10 12:04 am (UTC)с моим АДД я не смогла вникнуть даже в условия.
мне вспомнилась поездка с мамой в отпуск на новенькой вольве, мама купила, 81го года. или 80го. мы жили в какой-то каролине на море, я злилась и скучала по гэтсби. потом поехали обратно.
где-то на юге в никуде зашли в дайнер, там был паззл, с тремя уровнеми. на каждом столике по паззлу. мама решила первые два уровня за минуту, я за десять. мама принялась за третий.
вышли мы из дайнера через три часа. мама решила паззл третьего уровня, я понятно плюнула.
так и живем.
у мамы айкью конечно 180, а у меня наверное 80, я не считала чтобы не огорчаться.
no subject
Date: 2013-10-10 12:52 am (UTC)no subject
Date: 2013-10-10 04:24 am (UTC)в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.
Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?
Я могу привести конкретные две комбинации казино, как их Алиса отличит?
101001101
101001111
Я тоже три дня думал, и по-моему придумал, на выходных напишу, время будет )
no subject
Date: 2013-10-10 05:47 am (UTC)Правильно так:
"в случаях 011-01 и 100-01 Боб похожим образом делает ошибку И в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01."
> Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?
Эту информацию Алиса получит после бита F, в котором Боб сделает ошибку в случае, если HI равно 01 и не сделает ошибку, если HI равно 11.
no subject
Date: 2013-10-10 05:52 am (UTC)no subject
Date: 2013-10-10 05:58 am (UTC)no subject
Date: 2013-10-10 05:54 am (UTC)no subject
Date: 2013-10-10 05:51 am (UTC)Вот комбинации Боба для ваших примеров:
К 101001101: Б 000011101
К 101001111: Б 001011111
(биты нумеруются 1-9 слева направо)
В первом случае Алиса начинает отвечать 0 на биты 5-7, согласно указанию Боба в третьем бите. Но тут она видит, что в пятом бите Боб сделал ошибку, а она нет. Значит, надо изменить догадку на противоположную и отвечать 1 на биты 6-7, и 01 в конце.
Во втором случае Алиса начинает отвечать 1 на биты 5-7. В пятом бите Боб делает ошибку, но и Алиса тоже ошибается; поэтому она не меняет догадку, продолжает отвечать 11 на биты 6-7, и пользуется битом Боба для битов 8-9.
no subject
Date: 2013-10-10 05:59 am (UTC)no subject
Date: 2013-10-10 06:32 am (UTC)no subject
Date: 2013-10-10 06:52 am (UTC)до того места нигде не написано, что Боб поступает иначе, как в вашем примере
К 101001101: Б 000011101
но я понял модификацию, буду думать дальше, т.к. мои похожие 'решения' все имели прореху
no subject
Date: 2013-10-10 06:34 am (UTC)no subject
Date: 2013-10-10 06:16 am (UTC)no subject
Date: 2013-10-10 06:20 am (UTC)Потому что её бит совпал с битом казино.
no subject
Date: 2013-10-10 06:24 am (UTC)no subject
Date: 2013-10-10 07:05 am (UTC)То есть, в случаях EFG 011 и 100 Боб говорит неправильный преобладающий в EFG бит, Алиса угадывает первый из битов (E), но Боб не подтверждает её выбор. "Эта ошибка говорит Алисе, что следующие два бита противоположны плану" - то есть, следующие два бита она угадывает вопреки тому, что показал Боб ранее. И имеет дополнительную информацию о том, что HI = 01.
no subject
Date: 2013-10-10 07:15 am (UTC)no subject
Date: 2013-10-10 04:33 am (UTC)Тот факт, что перебором на компьютере её решить проще, чем "вручную", является очень сильным тому свидетельством.
no subject
Date: 2013-10-10 11:16 pm (UTC)http://xkcd.com/356/
no subject
Date: 2013-10-11 07:16 am (UTC)no subject
Date: 2013-10-11 07:26 am (UTC)no subject
Date: 2013-10-11 08:48 am (UTC)Мне для того, чтобы начать хоть сколько-нибудь прилично играть, всегда не хватало именно "переборного терпения". Я знаю, что сильные игроки совсем не считают игру переборной, но мне кажется, так происходит не потому, что они вообще перебором не занимаются совсем, а потому, что они научились не замечать этот процесс сознательно (а кое-где "выучили" значительные объемы оного, например, в дебютах).
Из-за этого, например, опыт шахматной игры не переносится ни на какую сколько-нибудь похожую область деятельности; оттуда нельзя позаимствовать интересные идеи (во всяком случае, я о таком не слышал).
no subject
Date: 2013-10-11 02:02 pm (UTC)Перебор в шахматах важен, но сильный игрок может играть и почти без перебора. Гроссмейстер имея секунду на ход все равно будет играть сильно. И обратный пример: сам наблюдал, как сильный гроссмейстер по шашкам не мог просчитать простую позицию в поддавках, хотя эти игры совпадают как графы. На мой взгляд, в шахматоподобных играх работает распознавание типичных патернов. То-есть, грубо говоря, при такой-то пешечной структуре, такой-то план должен быть эффективным. А дальше следует проверка гипотезы частичным перебором. Кроме того опытный игрок сразу видит стандартные последовательности ходов, подобно тому как мы сразу распознаем знакомое слово, а не читаем его по слогам.
С последним абзацем я пожалуй соглашусь: опыт шахматной игры отчасти переносится на другие игры. Другие полезные применения мне неизвестны.
no subject
Date: 2013-10-13 02:12 am (UTC)А по поводу переноса идей в шахматной игры - опять же непонятно что Плахов подразумевает под "хоть сколько-нибудь похожая область деятельности". Шашки и го - достаточно похожая область деятельности? При создании программ для этих игр ряд методов, изобретенных для шахмат весьма пригодился.
В общем, эта атака на шахматы больше похожа на личную неприязнь и непонимание, чем на что-то имеющее смысл.
no subject
Date: 2013-10-10 09:47 pm (UTC)Дальше Боб может на каждом "ошибочном" варианте (то есть когда казино будет выкидывать "непопулярный" бит), зная о выборе Алисы, передавать ей биты в обратном порядке - то есть вариант №10, №9, etc.
Алгоритм Алисы:
1) Выбрать что-то.
2) Запомнить выбор Боба
3) Выбирать выбор Боба, пока число отложенных битов не совпадёт с числом оставшихся раундов. Тогда использовать отложенные биты.
4) Если Алиса ошибается (кроме раунда1), то запоминать ответ Боба и помечать его как №10, №9 и т.д. и увеличивать число запомненных битов.
Рассчитывать вероятность победы затрудняюсь, но примерная оценка:
если из 9 вариантов 5 правильных будут сначала, значит из оставшихся 4 боб сможет передать 2.
Если из 9 вариантов правильные будут с конца, то увы, будет только 5 гарантированных побед.
ЗЫ Пребываю в сомнении, что лучше, передавать следующий вариант, или последний...
no subject
Date: 2013-10-16 08:07 pm (UTC)Если результат 2/3 - это не асимптотический предел, а реально достижимый на небольших сериях, каков же тогда максимальный процент угадывания при N стремящемся к бесконечности?
no subject
Date: 2017-03-14 05:38 am (UTC)