и в заключение
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-10 09:47 pm (UTC)Дальше Боб может на каждом "ошибочном" варианте (то есть когда казино будет выкидывать "непопулярный" бит), зная о выборе Алисы, передавать ей биты в обратном порядке - то есть вариант №10, №9, etc.
Алгоритм Алисы:
1) Выбрать что-то.
2) Запомнить выбор Боба
3) Выбирать выбор Боба, пока число отложенных битов не совпадёт с числом оставшихся раундов. Тогда использовать отложенные биты.
4) Если Алиса ошибается (кроме раунда1), то запоминать ответ Боба и помечать его как №10, №9 и т.д. и увеличивать число запомненных битов.
Рассчитывать вероятность победы затрудняюсь, но примерная оценка:
если из 9 вариантов 5 правильных будут сначала, значит из оставшихся 4 боб сможет передать 2.
Если из 9 вариантов правильные будут с конца, то увы, будет только 5 гарантированных побед.
ЗЫ Пребываю в сомнении, что лучше, передавать следующий вариант, или последний...