?

Log in

No account? Create an account
и в заключение - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

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

Links
[Links:| English-language weblog ]

и в заключение [окт. 9, 2013|11:38 pm]
Anatoly Vorobey
Теперь у меня есть "интуитивное" решение задачи про Алису, Боба и Казино. То самое, которого так долго ждали большевики и в поисках которого я вместе, кажется, с немалым числом читателей этого дневника бились головой об стенку в последние несколько дней. То самое, по поводу которого я уже решил было, что оно не существует.

Это не мое решение. Его придумал коллега из Гугла. Мне досадно, что все трюки, которые оно использует, я тоже пытался применить, но оно их все соединяет с еще большей хитроумностью и извращенностью, которые от меня ускользнули. Что я могу сказать - в Гугле работают умные люди.

(додумался бы я до этого решения, если бы еще несколько дней бился головой об стенку? Не знаю, но скорее нет, чем да)

Да, кстати, хоть оно, мягко скажем, не тривиальное, но действительно работает. Я проверил не только на глазок, но и программой, которую я написал для проверки решений.

Ну что, хотите узнать? Дальше идут одни спойлеры!

[Последний шанс не узнавать и думать самому!]


СПОЙЛЕРЫ



СПОЙЛЕРЫ





СПОЙЛЕРЫ



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


Уф. Ну как? Прекрасно, верно ведь?
СсылкаОтветить

Comments:
[User Picture]From: burrru
2013-10-09 08:55 pm
Да, это изящное решение.
(Ответить) (Thread)
[User Picture]From: vigourik
2013-10-10 02:20 pm
Изящное? Не смешите мои тапки! Изящные решения запоминаются, как стихи Пушкина. А с два раза менять стратегию - стопудово Алиса накосячит! :)
(Ответить) (Parent) (Thread)
[User Picture]From: homotub
2013-10-09 09:19 pm
охуенно. пойду пересплю с этим.
(Ответить) (Thread)
[User Picture]From: machin
2013-10-09 09:38 pm
5 пункт даже пугает извращённостью
(Ответить) (Thread)
[User Picture]From: dmarck
2013-10-09 10:41 pm
Вот да ;)
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-10-09 11:09 pm
Что-то мне это напоминает систему команд x86.
(Ответить) (Thread)
[User Picture]From: spamsink
2013-10-10 03:45 am
Ну да, mod-reg-r/m в практически чистом виде.
(Ответить) (Parent) (Thread) (Развернуть)
From: illy_drinker
2013-10-09 11:50 pm
Вы не помните несколько лет назад обсуждалась физическая задача о теле между которых и стеной двигается другое тело (отражаясь между ними) и один сотрудник гугл (кажется Игорь Н) предложил удивительное красивое решение?
(Ответить) (Thread)
[User Picture]From: avva
2013-10-10 06:31 am
Не помню, кажется...
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: tandem_bike
2013-10-10 12:04 am
Авва, поздравляю. очень респект и за старания и за решение.
с моим АДД я не смогла вникнуть даже в условия.

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

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

вышли мы из дайнера через три часа. мама решила паззл третьего уровня, я понятно плюнула.

так и живем.

у мамы айкью конечно 180, а у меня наверное 80, я не считала чтобы не огорчаться.
(Ответить) (Thread)
[User Picture]From: ripperfrvr
2013-10-10 12:52 am
Алиса делает одну ошибку (и Боб имеет в ней свой бит)
(Ответить) (Thread)
[User Picture]From: southwest
2013-10-10 04:24 am
Не согласен с вашим решением. Цитирую:

в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.

Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?

Я могу привести конкретные две комбинации казино, как их Алиса отличит?
101001101
101001111

Я тоже три дня думал, и по-моему придумал, на выходных напишу, время будет )
(Ответить) (Thread)
From: ger04ka
2013-10-10 05:47 am
Проущена всего одна буква, но реально немного смысл поменялся :)
Правильно так:
"в случаях 011-01 и 100-01 Боб похожим образом делает ошибку И в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01."

> Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?

Эту информацию Алиса получит после бита F, в котором Боб сделает ошибку в случае, если HI равно 01 и не сделает ошибку, если HI равно 11.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: plakhov
2013-10-10 04:33 am
Эта задача напомнила мне высказывание, которое Норвиг приводит насчет игры Судоку: "a denial of service attack on human intellect".

Тот факт, что перебором на компьютере её решить проще, чем "вручную", является очень сильным тому свидетельством.
(Ответить) (Thread)
[User Picture]From: _winnie
2013-10-10 11:16 pm
Благодаря этому багу в человеческом мышлении, мешающему в обычной жизни, появилась сегодняшняя техническая цивилизация.

http://xkcd.com/356/

Edited at 2013-10-10 23:17 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: amarao_san
2013-10-10 09:47 pm
Кстати, решение для 50%+: первым битом Боб сообщает Алисе какой бит будет более популярным среди оставшихся 9 вариантов. Их будет минимум 5.

Дальше Боб может на каждом "ошибочном" варианте (то есть когда казино будет выкидывать "непопулярный" бит), зная о выборе Алисы, передавать ей биты в обратном порядке - то есть вариант №10, №9, etc.

Алгоритм Алисы:

1) Выбрать что-то.
2) Запомнить выбор Боба
3) Выбирать выбор Боба, пока число отложенных битов не совпадёт с числом оставшихся раундов. Тогда использовать отложенные биты.
4) Если Алиса ошибается (кроме раунда1), то запоминать ответ Боба и помечать его как №10, №9 и т.д. и увеличивать число запомненных битов.

Рассчитывать вероятность победы затрудняюсь, но примерная оценка:

если из 9 вариантов 5 правильных будут сначала, значит из оставшихся 4 боб сможет передать 2.

Если из 9 вариантов правильные будут с конца, то увы, будет только 5 гарантированных побед.

ЗЫ Пребываю в сомнении, что лучше, передавать следующий вариант, или последний...
(Ответить) (Thread)
[User Picture]From: gul_kiev
2013-10-16 08:07 pm
Теперь меня в этой задаче вот что занимает.
Если результат 2/3 - это не асимптотический предел, а реально достижимый на небольших сериях, каков же тогда максимальный процент угадывания при N стремящемся к бесконечности?
(Ответить) (Thread)
[User Picture]From: _pk_sly
2017-03-14 05:38 am
мне "на пальцах" удалось получить примерно 0.77, но это тоже не совсем ассимптотика, а блоки. но они сильно длиннее 9.
(Ответить) (Parent) (Thread)