|
|
 |
Условие
Расстоянием между числами a1a2a3a4a5 и b1b2b3b4b5 назовём максимальное i, для которого ai ≠ bi. Все пятизначные числа выписаны друг за другом в некотором порядке. Какова при этом минимально возможная сумма расстояний между соседними числами?
Решение
Обозначим через x1, x2, x3, x4, x5 количество пар последовательно идущих чисел, расстояние между которыми равно 1, 2, 3, 4, 5 соответственно. Так как последних цифр встречается всего 10, то они
меняются как минимум 9 раз, следовательно, x5 ≥ 9.
Количество пар двух последних цифр – 100, поэтому аналогично x4 + x5 ≥ 100 – 1 = 99. Далее так же получаем ещё три соотношения:
x3 + x4 + x5 ≥ 999, x2 + x3 + x4 + x5 ≥ 9999, x1 + x2 + x3 + x4 + x5 = 89999, в последнем равенстве и справа, и слева стоит количество всех пятизначных чисел, уменьшенное на 1. Сложив все эти неравенства, получим: x1 + 2x2 + 3x3 + 4x4 + 5x5 ≥ 101105.
Заметим, что слева в этом неравенстве у нас как раз получилась
сумма расстояний между последовательными числами.
Теперь докажем, что оценка точная. Для каждого числа n = a1a2a3a4a5 рассмотрим число n' = a5a4a3a2a1 (оно может начинаться с нулей, но не может оканчиваться нулем) и запишем числа n' в порядке возрастания. В соответствующем порядке запишем и исходные числа n.
Заметим, что у чисел n' в таком порядке первая цифра (которая последняя у n) меняется 9 раз, первые две цифры – 99 раз и т. д., так как любые первые k цифр чисел n' тоже идут по порядку в данной последовательности.
Таким образом, все выписанные выше неравенства обращаются в равенства.
Ответ
101105.
