A.I.M. - Загадки

Offtop:

Итак, у нас есть 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,
и второй и третий бит вместе определяют, какая из них верна.