Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Задачка о заключенных, которые хотят выйти из тюрьмы
СообщениеДобавлено: 21 мар 2018, 14:49 
Не в сети
Одарённый
Зарегистрирован:
20 дек 2016, 11:08
Сообщений: 153
Cпасибо сказано: 2
Спасибо получено:
6 раз в 5 сообщениях
Очков репутации: -3

Добавить очки репутацииУменьшить очки репутации
Приветствую!
Подскажите куда смотреть при решении этой задачи:

В камере сидит 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},...), для каждого блока вычислить сумму номеров, а в первой карточке в битовом виде (флагами) зашифровать возрастание или убывание суммы

но доказать, что это сработает - не могу :(


Подскажите куда смотреть и вообще хоть где-то была у меня разумная мысль

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задачка о заключенных, которые хотят выйти из тюрьмы
СообщениеДобавлено: 21 мар 2018, 15:31 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Количество способов выйти из лифта

в форуме Комбинаторика и Теория вероятностей

ArsenyCh

6

686

09 окт 2019, 22:25

Попал я тупик не могу выйти

в форуме Алгебра

Alexandr_2004

12

416

17 авг 2021, 17:40

Задача про заключенных и лампочку - когда же на свободу

в форуме Комбинаторика и Теория вероятностей

Fireman

0

549

20 мар 2019, 22:43

Количество чисел, заключенных между 0 и 1000 и делящихся на

в форуме Комбинаторика и Теория вероятностей

afraumar

5

1346

28 июн 2015, 11:23

Раз хотят ещё задач

в форуме Геометрия

Gintoki-_-

9

342

03 апр 2021, 01:10

Не пойму, что от меня хотят)

в форуме Дифференциальные и Интегральные уравнения

ivanov av

5

814

11 авг 2014, 11:22

Задание, в котором я не понимю что от меня хотят. ЦСУТП

в форуме Начала анализа и Другие разделы школьной математики

Baguvix

0

268

17 янв 2020, 19:35

Трое друзей хотят разделить между собой напиток

в форуме Задачи со школьных и студенческих олимпиад

kaltsifer38

2

585

14 ноя 2019, 19:55

Трое друзей хотят разделить между собой 1 литр напитка

в форуме Пределы числовых последовательностей и функций, Исследования функций

Good_Salavat

6

482

12 сен 2020, 08:54

Найдите всё значения a параметра которые:

в форуме Алгебра

lukas

2

224

21 фев 2021, 13:34


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [bot] и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved