matyushkin 12 февраля 2020

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

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

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

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

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

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

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

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

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

***

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

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

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

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

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

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

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

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

РУБРИКИ В СТАТЬЕ

МЕРОПРИЯТИЯ

Web@Cafe #21
21 марта Омск Бесплатно
2-й большой казанский PHP-митап
28 марта Казань Бесплатно
DE or DIE #1
27 февраля Москва Бесплатно
@Databases Meetup #1
28 февраля Москва Бесплатно

Комментарии 8

ВАКАНСИИ

Programmer, Game (C++)
по итогам собеседования
Программист игровой логики C# (Unity)
Екатеринбург, по итогам собеседования
Программист игровой логики С++
Екатеринбург, по итогам собеседования
Android разработчик
от 140000 RUB до 200000 RUB

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

BUG