12 февраля 2020

Как ограбить банк? Логическая задача

Пишу, перевожу и иллюстрирую IT-статьи. На proglib написал 140 материалов. Увлекаюсь Python, вебом и Data Science. Открыт к диалогу – ссылки на соцсети и мессенджеры: https://matyushkin.github.io/links/ Для отправки опечаток на десктопе выделите текст и нажмите [Ctrl]+[Enter]. Если понравился стиль изложения, упорядоченный список публикаций и курсов — на GitHub: https://github.com/matyushkin/lessons
Эту задачу трудно решить аналитически... Но можно попробовать сделать это хотя бы программно. Смогли бы вы вскрыть необычный банковский замок?
Как ограбить банк? Логическая задача

Условие задачи

Медвежатник спланировал колоссальное ограбление. Последней преградой на пути похитителя стал необычный сейфовый замок. На его поверхности ряд из 7 одинаковых двухпозиционных (вкл/выкл) механических тумблеров. Секрет замка таков:

  1. Крайний правый переключатель может быть включен или выключен независимо от других.
  2. Состояние любого другого тумблера можно изменить только когда ближайший сосед справа включен, а все остальные правые тумблеры (если таковые есть) выключены.
  3. За один раз можно поменять положение только одного переключателя.

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

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

Решение – в следущей задаче.

Эта задача – тринадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – карточную головоломку Конвея.

***

Решение карточной головоломки Конвея

Как ответили читатели Библиотеки программиста? Никто из читателей Библиотеки программиста не дал ответа на сайте. В комментариях в паблике vk правильный ответ предложил Максим Авдиенко. Ниже мы рассмотрели решение подробнее.

Как ограбить банк? Логическая задача

Ответ: игра закончится после конечного числа перекладываний карт при любом исходном раскладе.

Решение. Король может появиться наверху колоды не более одного раза. Если он это сделает, алгоритм переместит его на последнюю 13-ю позицию, и никакая другая карта в верхней части колоды не будет в состоянии сдвинуть короля.

Дама может появиться наверху не более двух раз: после ее первого появления там и последующего перемещения на 12-ю позицию, только король сможет сместить ее оттуда, что не может произойти более одного раза.

Валет может появиться наверху колоды в худшем случае 4 раза: после своего первого появления его может переместить лишь король (1 раз) или дама (2 раза).

Итак, по индукции получается, что для любой карты со значением N от 2 до 13 могут появиться наверху колоды не более, чем 1 + (1 + 2 + ... + 212-N), то есть 213-N раз. Таким образом, каждая карта имеет конечное число перекладываний, и вся колода будет отсортирована.

Это пример алгоритмической головоломки, цель которой – доказать, что процедура головоломки останавливается после конечного числа итераций для каждого возможного ввода.

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Data Scientist
от 120000 RUB до 190000 RUB
Team Lead Python
Москва, от 300000 RUB до 400000 RUB

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ