Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | |
---|---|---|
Fireman |
|
|
Подскажите куда смотреть при решении этой задачи: В камере сидит 20 заключенных На следующий день должно пройти следующее испытание: 1) на стол предварительно однократно в случайном порядке выкладывается по одной фотокарточке этих 20 заключенных (т.е. 20 фотокарточек) рубашками вверх (изображений лиц не видно) 2) из камеры будут выводить по одному заключённому и подводить к столу 3) заключенный должен перевернуть 12 фотокарточек (в порядке в котором посчитает нужным) - если среди них обнаружится его - отпускают на свободу, нет - казнят 4) после каждого испытания карточки обратно переворачивают рубашками вверх (НО НЕ ПЕРЕМЕШИВАЮТ, так что их порядок сохраняется) 5) после начала испытания заключенные никак друг с другом общаться не могут (те кого вывели не могут общаться с теми, кто остался сидеть) Заключенные подкупи охранника и он обещал в ночь перед испытанием (когда карточки на столе уже были выложены в случайном порядке подойти к карточкам, посмотреть какие именно заключенные и в каком порядке лежат и поменять 2 карточки между собой местами. После этого с заключенными охранник не общался. Вопрос: Какой алгоритм нужно применить, чтобы удалось гарантированно спасти всех 20 заключенных. Подскажите как решить эту задачу? 1) сначала подумал, что каждому заключенному присваивается свой уникальный номер от 1 до 20 2) охранник изучает распределение фотокарточек и на 1 место кладёт фотокарточку заключенного номер которого означает алгоритм (один из 20 алгоритмов), который надо применить для того, чтобы каждый заключенный за следующие 11 переворачиваний карточек смог гарантированно себя найти. Что это за алгоритмы вообще не представляю 3) потом подумал, что первой фотокарточкой можно передать не число от 1 до 20, а состояния 4 флагов (от 1 до 16) или 4 алгоритма (от 17 до 20) (если понадобится) Но опять что-то не выходит есть вероятностный метод - если все карточки лягут на четный-нечетный или нечетный-четный или строго по возрастанию или строго по убыванию, то тогда всех 20 заключенных можно освободить (передать в первой карточке какая из 4 ситуаций случилась), но вероятность такого распределения всего 10% 4) потом подумал, что можно применить следующую технику - разбить все 20 (вернее 18) карточек на 6 блоков ({позиция 2, позиция 3,4}, {5,6,7},...), для каждого блока вычислить сумму номеров, а в первой карточке в битовом виде (флагами) зашифровать возрастание или убывание суммы но доказать, что это сработает - не могу Подскажите куда смотреть и вообще хоть где-то была у меня разумная мысль |
||
Вернуться к началу | ||
Slon |
|
|
Вернуться к началу | ||
[ Сообщений: 2 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |