Увидал эту загадку на хабре. Если кто её тоже видел и знает отгадку, извините.
Итак.
Вы — двое узников-смертников.
Надзиратель предлагает вам единственный шанс спастись, если пройдёте испытание шахматами и деньгами.
Состоит оно в следующем.
Надзиратель заводит первого из вас в камеру, в которой стоит стол, а на столе шахматная доска.
Надзиратель кладёт на доску 64 одинаковые монеты, орлом или решкой вверх исключительно по своему усмотрению.
Затем он показывает пальцем на одну из клеток доски и говорит: если второй узник определит эту клетку с первой попытки, вы оба спасены. Если нет, оба умрёте.
После чего позволяет первому узнику перевернуть одну любую монету на доске.
Далее первого узника выводит в одиночную камеру, а в камеру с доской вводит второго узника, где тот смотрит на доску и делает предположение о выбранной надзирателем клетке.
UPD.
Разумеется, узники знают правила игры и могут договориться между собой о стратегии до начала процедуры.
Далее, когда процедура началась, всё общение сводится к перевороту единственной монеты.
Здравствуйте, Кодт, Вы писали:
К>Надзиратель заводит первого из вас в камеру, в которой стоит стол, а на столе шахматная доска. К>Надзиратель кладёт на доску 64 одинаковые монеты, орлом или решкой вверх исключительно по своему усмотрению. К>Затем он показывает пальцем на одну из клеток доски и говорит: если второй узник определит эту клетку с первой попытки, вы оба спасены. Если нет, оба умрёте. К>После чего позволяет первому узнику перевернуть одну любую монету на доске. К>Далее первого узника выводит в одиночную камеру, а в камеру с доской вводит второго узника, где тот смотрит на доску и делает предположение о выбранной надзирателем клетке.
К>Какова наилучшая стратегия?
Предлагаю такой вариант:
Передавать информацию с помощью количества ЧЕТ и НЕЧЕТ строк/столбцов.
Влиять на это количество можно — если перевернуть монету, то поменяется четность строки и столбца, в которой лежит эта монета.
Действия первого узника:
Нужно обеспечить чтобы монет надзирателя оказалась в том множестве строк (ЧЕТ или НЕЧЕТ), которых меньше.
Для этого нужно выбрать в какой строке и в коком столбце (строго в одном) мы хотим поменять четность. Далее перевернуть монету на пересечении выбранных строки и столбца.
Алгоритм выбора строки (аналогично и для столбца)
Возможны два варианта:
1. Монета надзирателя уже лежит в "меньшем множестве". Пытаемся еще уменьшить "меньшее множество" — меняем четность у любой строки, в которой нет искомой монеты и которая относится к "меньшему множеству".
Например ЧЕТ 2 строки, НЕЧЕТ 6 строк, монета лежит в одной из двух ЧЕТ. Сменим четность у одной из ЧЕТ строк (не в той, где лежит монета). У нас останется ЧЕТ 1 строка, НЕЧЕТ 7 строк, монета останется в ЧЕТ.
2. Монета надзирателя находится в "большем множестве". В этом случаем меняем четность у строки, в которой лежит монета надзирателя.
Например ЧЕТ 2 строки, НЕЧЕТ 6 строк, монета лежит в одной из шести НЕЧЕТ. После смены четности у нас станет ЧЕТ 3 строки, НЕЧЕТ 5 строк, монета теперь лежит в ЧЕТ (их меньше).
3. Есть ещё один, проблемный, вариант. Если строки распределились как 5 к 3. И монета надзирателя лежит в "большем множестве".
Мы можем:
а) оставить неизменной четность строки с монетой надзирателя, выбрав другую строку
б) изменить четность строки с монетой надзирателя
В обоих случаях количество ЧЕТ и НЕЧЕТ станет 4 к 4. Но как тогда второй узник узнает из каких строк делать выбор — из ЧЕТ или НЕЧЕТ? Заметим, что фактически мы можем задать любую четность для строки с монетой надзирателя. Поэтому действуем так — задаем этой строкей такую же четность как четность у всей доски.
Действия второго узника:
1. Посчитать четность каждой строки, отметить те строки, которых меньше — ЧЕТ или НЕЧЕТ
1а. Если встретилось отношение строк 4 к 4, то делаем выбор на основе четности всей доски.
2. Считать, что искомая монета лежит только в отмеченных строках (из п.1)
3. Повторить то же самое для столбцов
К>Какова вероятность спасения?
Если надзиратель пакостит...
В худшем случае мы попадаем на отношение ЧЕТ и НЕЧЕТ строк как 4 к 4 и на такое же отношение столбцов. В этом случае второму узнику придется выбирать одну из 16 клеток (4 строки, 4 столбца). Но это в четыре раза лучше, чем выбирать одну из 64 клеток.
Здравствуйте, Кодт, Вы писали:
К>Увидал эту загадку на хабре. Если кто её тоже видел и знает отгадку, извините.
К>Итак. К>Вы — двое узников-смертников. К>Надзиратель предлагает вам единственный шанс спастись, если пройдёте испытание шахматами и деньгами. К>Состоит оно в следующем.
К>Надзиратель заводит первого из вас в камеру, в которой стоит стол, а на столе шахматная доска. К>Надзиратель кладёт на доску 64 одинаковые монеты, орлом или решкой вверх исключительно по своему усмотрению. К>Затем он показывает пальцем на одну из клеток доски и говорит: если второй узник определит эту клетку с первой попытки, вы оба спасены. Если нет, оба умрёте. К>После чего позволяет первому узнику перевернуть одну любую монету на доске. К>Далее первого узника выводит в одиночную камеру, а в камеру с доской вводит второго узника, где тот смотрит на доску и делает предположение о выбранной надзирателем клетке.
К>Какова вероятность спасения? К>Какова наилучшая стратегия?
Мне кажется, что Вы забыли указать, что у узников есть возможность, зная какое испытание их ждет, обсудить между собой стратегию действий.
Здравствуйте, Буравчик, Вы писали:
Б>В худшем случае мы попадаем на отношение ЧЕТ и НЕЧЕТ строк как 4 к 4 и на такое же отношение столбцов. В этом случае второму узнику придется выбирать одну из 16 клеток (4 строки, 4 столбца). Но это в четыре раза лучше, чем выбирать одну из 64 клеток.
Эх, решение "в лоб" не прокатило (как всегда).
Узнал правильное решение — впечатлился. Оказывается можно сильно-сильно улучшить.
Здравствуйте, Qulac, Вы писали:
К>>Какова вероятность спасения? К>>Какова наилучшая стратегия?
Q>Мне кажется, что Вы забыли указать, что у узников есть возможность, зная какое испытание их ждет, обсудить между собой стратегию действий.
Это лишнее. Они же мегамозги — независимо должны догадаться до одинаковой идеальной стратегии
Здравствуйте, Кодт, Вы писали:
К>Увидал эту загадку на хабре. Если кто её тоже видел и знает отгадку, извините.
К>Итак. К>Вы — двое узников-смертников. К>Надзиратель предлагает вам единственный шанс спастись, если пройдёте испытание шахматами и деньгами.
Всякий раз, когда я вижу такие загадки, и особенно когда я их вижу на собеседовании, мне хочется сломать загадывающему какую-нибудь кость, и — пока он в шоковом состоянии ничего не соображает, заставить разгадывать что-нибудь не имеющее однозначного решения. Под страхом второго перелома.
Здравствуйте, Слава, Вы писали:
С>Всякий раз, когда я вижу такие загадки, и особенно когда я их вижу на собеседовании, мне хочется сломать загадывающему какую-нибудь кость, и — пока он в шоковом состоянии ничего не соображает, заставить разгадывать что-нибудь не имеющее однозначного решения. Под страхом второго перелома.
Да ладно тебе. Задачка вполне решаемая и достаточно красивая.
Тем более, сама постановка вопроса: как одной монеткой передать 6 бит информации в зашумлённый канал.
Здравствуйте, alpha21264, Вы писали:
A>Если монетку можно и не переворачивать, то вероятность спасения можно довести до ста.
Даже если нужно переворачивать.
Разобьём доску пополам. Чётность первой половины обозначает один бит нужной нам информации; на чётность второй половины наплевать.
Если чётность исходно неподходящая, переворачиваем монетку из первой половины. Если исходно подходящая, — переворачиваем из второй.
В частности, этот бит может означать "нужная клетка находится в первой/второй половине доски, разбитой данным способом".
Хотя это и не обязательно, но просто удобно.
Наложим на доску карту Карно любым способом. Геометрические способы удобнее использовать для быстроты принятия решения, но, опять же, это дело вкуса.
Если мы пронумеруем клетки двоичными числами или кодом Грея, как раз получится геометрическая карта Карно.
Остался этюд для программистов: написать компактную формулу или программу
Здравствуйте, Кодт, Вы писали:
К>Наложим на доску карту Карно любым способом.
Кстати, да, тоже про карты Карно вспомнил. Правда, в оригинале,
когда занимаешься минимизацией логических функций, то
для 6 переменных правила склейки ячеек получались
очень нетривиальными. Но тут у нас ничего склеивать не требуется.
Здравствуйте, alpha21264, Вы писали:
A>Если монетку можно и не переворачивать, то вероятность спасения можно довести до ста.
Если переворачивать, то тоже можно
Кстати, в исходной английской формулировке этот момент тоже туманный. Но потом, по ходу
объяснения задачи, упоминается, что мы таки обязаны сделать переворот.
Странно, что это не прописали в условии чётко.
С другой стороны, обязательность переворота — это подсказка, существенно сужающая область поиска решений.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, alpha21264, Вы писали:
A>>Если монетку можно и не переворачивать, то вероятность спасения можно довести до ста.
К>Даже если нужно переворачивать. К>Разобьём доску пополам. Чётность первой половины обозначает один бит нужной нам информации; на чётность второй половины наплевать.
Ну да. Я догадался уже после того, как отправил сообщение.
Перекуём баги на фичи!
