Question

Как решить задачу про Мистера Фокса и 600 карточек (см)?

В ряд лежат карточки с числами от 1 до 600 (на каждой карточке написано ровно одно число; изначально числа на карточках расположены в порядке возрастания слева направо). Мистер Фокс делает следующую операцию: он выбирает группу последовательных карточек в имеющемся ряду и перекладывает их в обратном порядке. Эту операцию он проделал с карточками, лежащими на первых k местах слева, по очереди для всех k от 1 до 600. На каком месте теперь лежит карточка с числом 1

Answer 1

При k=1 мы берем карту 1 и кладем ее обратно на 1 место, потому что перекладывать нечего.

При k=2 мы перекладываем карты 1 и 2, карта 1 оказывается на 2 месте.

При k=3 мы берем карты 2,1,3 и получаем 3,1,2. Карта 1 осталась на 2 месте.

При k=4 берем 3,1,2,4 и получаем 4,2,1,3. Карта 1 оказалась на 3 месте.

При k=5 берем 4,2,1,3,5 и получаем 5,3,1,2,4. Карта 1 осталась на 3 месте.

Далее. При k=6 и 7 карта 1 окажется на 4 месте, при k=8 и 9 карта 1 окажется на 5 месте, и т.д.

Получается, что при любом k=2n и при k=2n+1 карта 1 окажется на (2n+2)/2 = (n+1)-ом месте.

После перекладывания k=600 (n=300) карта 1 окажется на 301-ом месте.