Условие задачи
Медвежатник спланировал колоссальное ограбление. Последней преградой на пути похитителя стал необычный сейфовый замок. На его поверхности ряд из 7 одинаковых двухпозиционных (вкл/выкл) механических тумблеров. Секрет замка таков:
- Крайний правый переключатель может быть включен или выключен независимо от других.
- Состояние любого другого тумблера можно изменить только когда ближайший сосед справа включен, а все остальные правые тумблеры (если таковые есть) выключены.
- За один раз можно поменять положение только одного переключателя.
Замок открывается, когда все рычаги находятся в выключенном состоянии. Но исходно все включены. За какое минимальное количество переключений тумблеров медвежатник, узнавший секрет замка, его откроет?
Если не получается решить задачу аналитически, приведите программное решение на любом языке. Это гораздо проще, но вы хотя бы узнаете число. Сможете ли вы найти приближение для n тумблеров?
Решение – в следущей задаче.
Эта задача – тринадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – карточную головоломку Конвея.
Решение карточной головоломки Конвея
Как ответили читатели Библиотеки программиста? Никто из читателей Библиотеки программиста не дал ответа на сайте. В комментариях в паблике vk правильный ответ предложил Максим Авдиенко. Ниже мы рассмотрели решение подробнее.
Ответ: игра закончится после конечного числа перекладываний карт при любом исходном раскладе.
Решение. Король может появиться наверху колоды не более одного раза. Если он это сделает, алгоритм переместит его на последнюю 13-ю позицию, и никакая другая карта в верхней части колоды не будет в состоянии сдвинуть короля.
Дама может появиться наверху не более двух раз: после ее первого появления там и последующего перемещения на 12-ю позицию, только король сможет сместить ее оттуда, что не может произойти более одного раза.
Валет может появиться наверху колоды в худшем случае 4 раза: после своего первого появления его может переместить лишь король (1 раз) или дама (2 раза).
Итак, по индукции получается, что для любой карты со значением N от 2 до 13 могут появиться наверху колоды не более, чем 1 + (1 + 2 + ... + 212-N), то есть 213-N раз. Таким образом, каждая карта имеет конечное число перекладываний, и вся колода будет отсортирована.
Это пример алгоритмической головоломки, цель которой – доказать, что процедура головоломки останавливается после конечного числа итераций для каждого возможного ввода.
Комментарии