Олимпиада имени Леонарда Эйлера2015-2016 учебный год, I тур заключительного этапа

Даны $2n$-значное натуральное число $a$ и натуральное число $k$. Числа $a$ и $ka$ записали на ленте и каждую из двух записей разрезали на двузначные числа, начиная с последних цифр (при этом числа $00$, $01$, $\ldots$, $09$ здесь тоже считаются двузначными; если в числе $ka$ оказалось нечетное количество цифр, к нему спереди приписали $0$). Оказалось, что у числа $a$ полученные двузначные числа строго убывают справа налево (от младших разрядов числа $a$ к старшим), а у числа $ka$ — строго возрастают. Докажите, что $k \geq n$. ( С. Берлов, О. Нечаева )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение 1. Запишем числа $a$ и $k$ в системе счисления с основанием 100. Двузначные числа, на которые в условии режутся записи чисел $a$ и $ka$, будут в ней цифрами. Далее мы везде под «цифрами» мы понимаем цифры в 100-ичной системе счисления. Пусть в этой системе $a =\overline{{{a}_{n}}\ldots {{a}_{1}}}$.
       Рассмотрим умножение $a$ на $k$ «в столбик». Для всех $i$ от $2$ до $n$ положим $b_i = ka_i+c_i$, где $c_i$ — перенос из $(i-1)$-го разряда в $i$-ый. Положим также $b_1 = ka_1$, $c_1 = 0.$ Заметим, что $i$-ая цифра произведения $ka$ равна остатку $r_i$ от деления $b_i$ на 100 при всех $i = 1, \ldots, n$.
       Покажем по индукции, что тогда $c_i < k$ при всех $i$ от $2$ до $n$. Заметим, что $c_i$ — это неполное частное от деления $b_{i-1}$ на $100$. Поэтому $c_i \geq k \Leftrightarrow b_{i-1} \geq 100k$. Поскольку $b_1 = ka_1 \leq 99k$, перенос $c_2$ меньше $k$ — база проверена. Докажем переход. Пусть $c_i < k$. Тогда $b_i = ka_i+c_i < 99k+k = 100k$, откуда $c_{i+1} < k$.
       Допустим, $k < n$. Тогда $k \leq n-1$, и из доказанного следует, что все $c_i$ не превосходят $n-2$. Значит, по принципу Дирихле среди $c_i$ найдутся два одинаковых: $c_u = c_v = m$. Пусть $b_v = 100m+r_v$, $b_u = 100m+r_u$ и $v > u$. Тогда $b_v = ka_v+c_v \leq k(a_u-1)+c_v < ka_u \leq b_u$, откуда $r_u > r_v$, что противоречит требованию, чтобы цифры произведения $ka$ возрастали от младших разрядов к старшим.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. При $i = 0, 1, \ldots, n-1$ обозначим через $A_i$ остаток от деления числа $100^i \cdot a$ на $10^{2n}$, а через $B_i$ — остаток от деления числа $100^i \cdot ka$ на $10^{2n}$. Числа $A_i$ и $B_i$ неотрицательны, но меньше $10^{2n}$; при этом их десятичные записи начинаются с последних $2(n-i)$ цифр чисел $a$ и $ka$, соответственно. Тогда из условия следует, что $A_0 < A_1 < \ldots < A_{n-1}$ и $B_0 > B_1 > \ldots > B_{n-1}$. Кроме того, $kA_i \equiv B_i \pmod{10^{2n}}$.
       Пусть $kA_i = B_i+10^{2n} \cdot t_i$. Тогда $10^{2n} \cdot t_i = kA_i-B_i > kA_{i-1}-B_{i-1} = 10^{2n} \cdot t_{i-1}$, то есть $0 \leq t_0 < t_1 < \ldots < t_{n-1}$. Поскольку $t_i$ — целые неотрицательные числа, получаем, что $t_{n-1} \geq n-1$, откуда $10^{2n}(n-1) \leq 10^{2n} \cdot t_{n-1} \leq kA_{n-1} < 10^{2n} \cdot k$. Итак, $n-1 < k$, что и требовалось доказать.
       \zam Неравенства $A_0 < A_1 < \ldots < A_{n-1}$ и $B_0 > B_1 > \ldots > B_{n-1}$ из второго решения выполнены и в том случае, если полученные из числа $a$ двузначные числа нестрого убывают (но первое строго меньше второго!), а двузначные числа, полученные из $ka$, нестрого возрастают (но первое строго больше второго!). Значит, и утверждение задачи верно и при этих более слабых условиях.