мудрецы в тюрьме

[avva]

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

Итак, король решил, что придворные мудрецы зря проедают его деньги, и повелел всех 20 мудрецов бросить в тюрьму. Чтобы проверить, кто из них действительно мудрец, советники короля придумали следующий тест. На длинном столе в тронной комнате разложены в ряд фотографии всех 20 мудрецов, лицевой стороной вниз. Стража приводит мудрецов по одному из тюремной камеры и ставят перед столом. Каждый мудрец может перевернуть не более 12 фотографий, и среди перевернутых обязана быть его собственная фотография. Если нашел свою фотографию - его тут же выпускают на свободу (он не может передать никаких сведений тем мудрецам, что еще не прошли проверку). Если не нашел - его тут же казнят. В любом случае все раскрытые фотографии переворачивают обратно - их порядок остается таким же, как раньше - и вызывают следующего мудреца.

Когда надзиратели пришли в камеру, где вместе сидели все мудрецы, и сообщили им, что на следующее утро им предстоит эта проверка, мудрецы поначалу приуныли. Но потом решили провести оставшееся время с пользой, и придумать какой-нибудь хитрый трюк, который поможет им избежать казни. После долгих уговоров мудрецам удалось подкупить одного из стражников, который согласился пробраться в тронную комнату перед рассветом, когда все уже будет приготовлено заранее к проверке и фотографии будут разложены. Стражник может перевернуть все фотографии, изучить их, и, действуя по инструкциям мудрецов, обменять местами какие-то две из них (и все перевернуть обратно, конечно). Ничего больше стражник не согласился сделать - только поменять местами две фотографии - он боится, что иначе церемонимейстер может заметить. Кроме того, он уже не успеет вернуться к мудрецам перед проверкой и что-либо им рассказать.

Придумайте, как ВСЕ мудрецы могут избежать казни.

Update: решение задачи.

Comments

[avva.livejournal.com]

Да, верно :) заскриню ваш комментарий пока что.

[dmpogo.livejournal.com]

А мудрецы знают кто пойдет первым ?

[(Anonymous)]

А какая разница?

[dmpogo.livejournal.com]

Тем кто знает, или уже понял, ответ, может и никакой (что конечно тоже само по себе подсказка :) )

[urod.livejournal.com]

Поскольку мудрецы не могут ничего сообщать друг другу, порядок не важен.

[avva.livejournal.com]

Нет, и не могут влиять на порядок.

[gershshpraihler.livejournal.com]

Из того что есть решение следует что у некотопых из них одинаковые лица?

[avva.livejournal.com]

нет, лица у всех разные.

[xxxxx.livejournal.com]

как-то непонятно изложено. К примеру "перевернуть 12" это сразу выбрать 12 из 20 или же переворачивать по одной, имея возможность выбрать следующую в зависимости от увиденного? и обязательно ли стражнику менять пару или же в некоторых случаях инструкции могут предусматривать не менять ничего

[gdt.livejournal.com]

если выбирать сразу 12, то решения, очрвидно, не существует.

[dmpogo.livejournal.com]

А, это другое дело

[alaev.livejournal.com]

Если переворачивать сразу 12, то два мудреца могут спастись.

[gdt.livejournal.com]

13 смогут.

[avva.livejournal.com]

Можно переворачивать по одной. Стражнику менять необязательно (хотя это неважно, если обязательно, задача тоже имеет решение).

[avva.livejournal.com]

Да, все правильно :)

[avva.livejournal.com]

Верно!

[173175973.livejournal.com]

Нереально. Стражник, у которого хватит ума хотя понять инструкции тоже будет в камере при действующем короле.
А за формулировку спасибо. Только в такой постановке, пожалуй, труднее первоначального варианта.

[avva.livejournal.com]

Чуть труднее. Зато определеннее решение.

[utnapishti.livejournal.com]

Труднее из-за того, что возникает иллюзия, что это задача "на чётность-нечётность".

[(Anonymous)]

Поставить на первое место, например, фото определённого мудреца который будет идти первым.
Мудрецы знают порядок в котором они будут выходить.
Первый мудрец смотрит на свою фото и в первой, например, половине ищет следующего вызываемого за ним. Если находит в первой половине фотграфий - каким-либо образом помечает на пераой своей фотке (поворачивает её на 90 градусов или вверх ногами). Следующий смотрит на первую сигнальную фотку и определяет была ли найдена его фотка в первой половине. Либо смотрит сразу во второй половине. Оставляет сигнал на первой фотке следующему мудрецу - находится ли его фотка в первой половине

[http://users.livejournal.com/primus_/]

> обменять местами какие-то две из них (и все перевернуть обратно, конечно).

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

[avva.livejournal.com]

Только между собой.

[occuserpens.livejournal.com]

Похоже что король репрессировал ВСЕХ своих мудрецов. Потому что если бы кто-то остался на свободе, он ввел бы тасовку картинок и мудрецов непосредственно перед и по ходу процедуры. Тогда никто ничего не смог бы сделать.

[obiwanus.livejournal.com]

Если бы король хотел всех убить, то можно было бы и не заморачиваться с задачами

[(Anonymous)]

В моём решении 12 можно заменить на 10. Я ошибся?

[avva.livejournal.com]

не ошиблись :)

[aosypov.livejournal.com]

упс... фигню сморозил

[i-am-a-jew-01.livejournal.com]

Решение задачи может быть разбито на несколько этапов..
1. какое задание дали мудрецы стражнику?
Как мне кажется, это задание должно быть предельно простым.. Стражник должен выбрать фотографию мудреца, который пойдёт первым (в условии задачи не указано, что выбор производится случайным жребием) и поменять её с фотографией, лежащей на определённом месте, к примеру, крайней слева.
2. как передать информацию идущему следом?
Информацию можно передать с помощью вращения фотографии, лежащей в выбранной позиции (в условии задачи не оговорено, что фотографии должны лежать определённым образом)
3. Какую информацию и каким образом можно передать идущему следом?
Если фотография не повёрнута, то "выбирай четные фотографии, в нечетных я тебя не видел".
Если фотография повёрнута, то "выбирай нечетные, в четных тебя нет".

Это примерная процедура, позволяющая решить задачу

[(Anonymous)]

это не процедура позволяющая решить задачу.

[ts-ufa.livejournal.com]

Когда будет ответ? :)

[avva.livejournal.com]

Завтра утром :)

[blainemono.livejournal.com]

Ииииииииии?

[(Anonymous)]

Где ответ?

[(Anonymous)]

С помощью одной транспозиции разбить максимальный цикл на два

[migmit (from livejournal.com)]

Ну, в общем-то, да. Только непонятно, откуда возникло число 12.

[(Anonymous)]

Чтобы точно уж больше половины :)

[urod.livejournal.com]

Я думал в этом направлении, но чем это поможет? Есть два цикла в 10, и что? Мудрец не знает, в каком из двух циклов его физиономия.

[(Anonymous)]

Так если мудрец начал цикл с фотки, соответствующей собственному номеру, и завершил его, то чьей фоткой он его завершил?

[(Anonymous)]

Думал-думал, не додумал :-)
Надеюсь, решение простое и стражник не перекладывает фотографии на основании какого-нибудь сложного алгоритма. Например, нумерации мудрецов от 1 до 20, а затем какого-нибудь подсчёта суммы или чего-то такого.

[(Anonymous)]

Вряд-ли существует простое решение.

Предыдущая задача на эту тему (которую упоминает avva) звучала так: каждый мудрец мог перевернуть половину всех фотографий (т.е. 10 штук), никакого помощника у мудрецов не было, мудрецам сохраняли жизнь только если каждый из них находил свою фотографию.

В такой формулировке у мудрецов нет гарантированой стратегии спасения. Уже самый первый мудрец с вероятностью 1/2 не найдёт свою фотографию и погубит всех. Задача мудрецов была в том, чтобы выработать стретегию, которая даёт им сколько-нибудь существенный шанс спастись.

Конечно, мудрец, который уже переворачивал фотографии, ничего не может сообщить тем, кто ещё не. И поэтому выжить мудрецы могут с вероятностью 1/2^20 - это настолько очевидный факт, что для меня он остаётся очевидным несмотря на то, что знаю намного лучшую стратегию.

[pavelm123.livejournal.com]

а мудрецы знают порядок, в котором они будут входить в комнату?

[(Anonymous)]

Хотя это им ничего не даст... Вопрос не имеет смысла

[mitrichu.livejournal.com]

Первую с последней?

[noname-rambler.livejournal.com]

Если в этом возникнет необходимость:)
(сейчас ответ посмотрю)

[scherkas.livejournal.com]

очень красивая задача и решение.
Подтверждает (уже давно устоявшееся у меня) мнение о полу-магической природе вероятности - под влиянием задач вроде Монти Холла, парадокса Бертрана и - вот теперь еще этой.

Не совсем математическое наблюдение: в задаче интересна роль "советников", предложивших этот тест. Они, советники, понятное дело, решение знали, и даже со стражником договорились заранее (иначе зачем королю соглашаться на тест, в результате которого придется убить кучу своих мудрецов??). Похоже на внутренние разборки в Королевской Академии Наук :-)))