Задача
Волшебник Игорь Поттов попал в тайную комнату, в которой 1 000 000 дверей. Все двери пронумерованы от 1 до 1 000 000. Алик Далбидверь сказал Игорю, что в одной из комнат, в номере которой есть шестёрка, стоит кубок огня. Но магия палочки в комнате не работает. Поэтому искать придётся самостоятельно. Но есть и позитивное обстоятельство. Каждый раз, когда открывается любая дверь, за которой нет кубка, срабатывает заклинание Геминио, которое создаёт клона из того, кто открывает дверь.
Все клоны помогают Игорю открывать двери и искать кубок, они могут открывать разные двери в любом порядке, но только все вместе одновременно. Т.е. Игорь и один клон одновременно откроют две двери, Игорь и 3 его клона, откроют 4 двери одновременно и так далее.
Сколько клонов в итоге будет при самом быстром поиске кубка и при самом долгом?
Подсчёт количества дверей с цифрой «6»
Сначала нужно определить, сколько всего дверей содержат цифру «6» в своём номере. Это можно сделать по формуле:
Подставив все данные в формулу выше получаем количество дверей с шестёркой: N = 468 559.
Процесс открытия дверей
На каждом шаге Игорь и все текущие клоны открывают одновременно C + 1 дверей (где C — текущее количество клонов, +1 — сам Игорь).
Если среди открытых дверей нет кубка, то за каждую открытую дверь без кубка создаётся по одному новому клону.
То есть если открыли k дверей без кубка, то создаётся k новых клонов. Количество клонов увеличивается на k.
Если кубок найден, процесс останавливается.
Минимальное количество клонов
Если кубок находится за первой открытой дверью с шестёркой то процесс поиска прекращается и не появляется ни одного клона, значит минимальное количество клонов для поиска равно нулю.
Максимальное количество клонов
Когда количества клонов максимально, то кубок находится в последней открытой двери с шестёркой в номере. Нужно максимизировать количество созданных клонов до нахождения кубка.
Это эквивалентно тому, что все двери с «6», кроме последней, были открыты без кубка, и после открытия каждой такой двери создавался клон.
На каждом шаге количество «исследователей» увеличивается на количество открытых дверей без кубка.
Кубок находится в последней открытой двери, значит, перед этим было открыто N−1 дверей без кубка.
Количество «искателей» (Игорь + клоны) к моменту нахождения кубка будет равно или больше количества дверей с шестёркой делённое на 2, то есть N / 2 = 234 279.
Уточним, как именно растёт количество клонов
На шаге i:
- Ci — количество клонов перед шагом i.
- Открывается Ci+1 дверей. Т.к. «искателей» на 1 больше чем клонов (+1 сам Игорь).
- Если ни одна не содержит клад, то создаётся Ci + 1 новых клонов.
- Тогда Ci+1 = Ci+(Ci + 1) = 2Ci + 1.
Это экспоненциальный рост. Количество клонов растёт как:
C₀ = 0.
- Шаг 1: открываем 1 дверь, создаём 1 клона: C₁ = 1
- Шаг 2: открываем 2 двери, создаём 2 клонов: C₂ = 1 + 2 = 3
- Шаг 3: открываем 4 двери, создаём 4 клонов: C₃ = 3 + 4 = 7
...
Таким образом видно, что Cₖ = 2ᵏ − 1
Общее количество открытых дверей после k шагов:
Sₖ = 1 + 2 + 4 + ... = 2ᵏ − 1
Нам необходимо, чтобы открытых дверей было Sₖ ≥ N – 1, при этом последняя дверь будет открыта на шаге k + 1.
Найдём минимальное число шагов k, такое что 2ᵏ – 1 ≥ 468559, 2ᵏ ≥ 468560
k = log₂(468560) = 18
В точности этот логарифм равен 18,83787… но в условии задачи k – это натуральное положительное число (N), т.к. число шагов не может быть дробным.
На шаге 18 будет 2¹⁸ – 1 = 262144 – 1 = 262143 дверей и будет столько же клонов Игоря.
А на шаге 19 будет открыто уже 2¹⁹ – 1 = 524287 дверей и будет столько же клонов. По условию нужно открыть 468559 дверей, значит, на шаге 19 процесс остановится. Следовательно, при самом медленном поиске в конце будет 524287 клонов и минус один клон, который найдёт кубок, т.к. по условию при нахождении кубка клон не создаётся, т.о. в итоге останется 524286 клонов.
Ответ на задачу
- Самое быстрое нахождение кубка и минимум клонов:
0 клонов, кубок найден при первой же попытке. - Самое долгое нахождение кубка и максимум клонов: 524286 клонов. Кубок найден на 19 шаге.