Олимпиадная задача: максимальное совпадение номерков по условиям перестановки, Шаповалов А. В.
Задача
Сто номерков выложили в ряд в порядке возрастания: 00, 01, 02, 03, ..., 99. Затем номерки переставили так, что каждый следующий номерок стал получаться из предыдущего увеличением или уменьшением ровно одной из цифр на 1 (например, после 29 может идти 19, 39 или 28, а 30 или 20 – не может). Какое наибольшее число номерков могло остаться на своих местах?
Решение
Оценка. После перестановки суммы цифр соседних чисел отличаются на единицу. Поэтому либо чётность суммы цифр каждого номерка совпадает с чётностью его места, либо, наоборот, эти чётности у всех номерков различны. А до перестановки чётности совпадали ровно в половине случаев: в каждом втором десятке. Значит, результат сравнения изменился у 50 номерков, и они не могли остаться на месте. Пример, где на месте ровно 50 номерков (выделены жирным): переворачиваем десятки с первой нечётной цифрой. Получится 00, 01, …, 09, 19, 18, ..., 10, 20, 21, ..., 29, 39, 38, ..., 91, 90.
Ответ
50 номерков.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь