======= 138 ========ММ138 (6 баллов)
Доказать, что для любого натурального k найдутся натуральные a, n и g, такие что для всех i из {0,1,... ,k-1}
в системе счисления с основанием g+i, число a является n-i-значным.
===============РешениеПриведу решение Владислава Франка.
Условие задачи равносильно следующему утверждению:
![$\forall i \in \{0,1,\dots,k\} (g+i)^{n-i}> a\ge (g+i)^{n-i-1}$ $\forall i \in \{0,1,\dots,k\} (g+i)^{n-i}> a\ge (g+i)^{n-i-1}$](https://dxdy-02.korotkov.co.uk/f/d/c/7/dc74ac0e92eb2c3d229e6132270c3c3782.png)
Попробуем подобрать
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
и
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
так, чтобы все выражения в левых (и правых) частях неравенства были очень близки друг к другу.
Для этого нужно, чтобы функция
![$f(x)=(g+x)^{n-x}$ $f(x)=(g+x)^{n-x}$](https://dxdy-02.korotkov.co.uk/f/1/e/3/1e3a6c2895a38943e649ef83c3799dd382.png)
была почти постоянна, а для этого ее производная
![$f'(x)=(g+x)^{n-x}\cdot \left(\frac{n-x}{g+x}-\ln(g+x)\right)$ $f'(x)=(g+x)^{n-x}\cdot \left(\frac{n-x}{g+x}-\ln(g+x)\right)$](https://dxdy-02.korotkov.co.uk/f/d/8/e/d8e61163653665b515f1cc773b142dfa82.png)
должна мало отличаться от нуля.
Для этого
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
должно быть близко к
![$g\ln g$ $g\ln g$](https://dxdy-03.korotkov.co.uk/f/a/b/a/aba57a624b845ff39a99ba61bb45039782.png)
. Выберем
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
и в качестве
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
возьмем
![$\lceil g\ln g\rceil$ $\lceil g\ln g\rceil$](https://dxdy-01.korotkov.co.uk/f/8/c/b/8cbb3f509ad7418cfcd17660f4e8557882.png)
.
Тогда
![$\frac{n-x}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$ $\frac{n-x}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$](https://dxdy-01.korotkov.co.uk/f/0/6/e/06e0612eed29d284e8ddc5a3df6def3182.png)
. Значит функция убывает и принимает максимальное значение на границе интервала. Поэтому от всех оценок для
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
сверху достаточно оставить одну:
![$(g+k)^{n-k}>a$ $(g+k)^{n-k}>a$](https://dxdy-03.korotkov.co.uk/f/2/8/6/286c3cef028b65e8c455ae5dca8b449582.png)
.
Аналогично, рассматривая нижние оценки, получаем:
![$h'(x)=(g+x)^{n-x-1}\cdot \left(\frac{n-x-1}{g+x}-\ln(g+x)\right)$ $h'(x)=(g+x)^{n-x-1}\cdot \left(\frac{n-x-1}{g+x}-\ln(g+x)\right)$](https://dxdy-01.korotkov.co.uk/f/8/2/b/82bdd73ced047e0c4068a644e5c6b57582.png)
и
![$\frac{n-x-1}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$ $\frac{n-x-1}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$](https://dxdy-03.korotkov.co.uk/f/6/9/5/6957936b682fab897a83ec5c88bbaea782.png)
.
Поэтому из всех оценок снизу достаточно взять
![$a\ge g^{n-1}$ $a\ge g^{n-1}$](https://dxdy-03.korotkov.co.uk/f/a/7/3/a735162352fa95cb8c90152c0235aa1c82.png)
.
Докажем, что при больших
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
в интервале
![$\left(g^{n-1},(g+k)^{n-k}\right)$ $\left(g^{n-1},(g+k)^{n-k}\right)$](https://dxdy-02.korotkov.co.uk/f/1/5/9/159e967b61070283f8c568de4749bd4b82.png)
найдется хотя бы одно натуральное число (оно-то и будет нашим
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
).
(Заодно мы докажем, что верхняя граница интервала действительно больше нижней.)
Достаточно доказать неравенство
![$(g+k)^{n-k}> 2g^{n-1}$ $(g+k)^{n-k}> 2g^{n-1}$](https://dxdy-01.korotkov.co.uk/f/4/2/a/42a32705a11c53bf5fc0ef29c9ea3f8e82.png)
. Тогда длина интервала будет велика и хотя бы одно число туда попадет.
Логарифмируем:
![$(n-k)\ln (g+k) > (n-1)\ln g +\ln 2$ $(n-k)\ln (g+k) > (n-1)\ln g +\ln 2$](https://dxdy-02.korotkov.co.uk/f/1/a/4/1a4a8e46a2b22bbfedbcbb95979ac2e482.png)
Как известно,
![$\ln(1+x) > x-\frac{x^2}{2}$ $\ln(1+x) > x-\frac{x^2}{2}$](https://dxdy-03.korotkov.co.uk/f/6/7/5/675ca4e9f895f77b13db3414970ba81582.png)
при малых
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
, поэтому достатчно будет доказать
![$(g\ln g -1)\left(\frac{k}{g}-\frac{k^2}{2g^2}\right)-k\ln(g+k)+\ln g - \ln 2 > 0$ $(g\ln g -1)\left(\frac{k}{g}-\frac{k^2}{2g^2}\right)-k\ln(g+k)+\ln g - \ln 2 > 0$](https://dxdy-01.korotkov.co.uk/f/4/0/0/4004504bbb70c03e72d892d54746095582.png)
![$\ln g \left(k-\frac{k^2}{2g}\right)-k\ln(g+k)+\ln g > \ln 2 + \frac{k}{g}-\frac{k^2}{2g^2}$ $\ln g \left(k-\frac{k^2}{2g}\right)-k\ln(g+k)+\ln g > \ln 2 + \frac{k}{g}-\frac{k^2}{2g^2}$](https://dxdy-04.korotkov.co.uk/f/7/1/d/71d8eb41e45c97b7cb1c9cc14bc53c2e82.png)
![$\ln g > \ln 2 +\frac{k}{g}-\frac{k^2}{2g^2}+\frac{k^2\ln g}{2g}+k\ln(1+\frac{k}{g})$ $\ln g > \ln 2 +\frac{k}{g}-\frac{k^2}{2g^2}+\frac{k^2\ln g}{2g}+k\ln(1+\frac{k}{g})$](https://dxdy-04.korotkov.co.uk/f/7/6/e/76e31971644bdf7863d07e00f956c32982.png)
Очевидно, это верно при больших
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
поскольку в правой части все слагаемые, кроме первого, стремятся к 0 с ростом
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
.
Остается взять подходящее
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
, по нему
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
и по ним
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
.
ОбсуждениеПриведу пример для
![$k=5$ $k=5$](https://dxdy-04.korotkov.co.uk/f/b/e/8/be82cf66eb32e65bbf7472eed0fc86e582.png)
: Пусть
![$a=3486784400$ $a=3486784400$](https://dxdy-01.korotkov.co.uk/f/8/5/0/850dd2007e0dbf874184cb0988c396a582.png)
(в десятичной системе). Ниже приводится (обратная) запись
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
для систем с основаниями от 5 до 9:
Код:
5, [0, 0, 1, 0, 0, 1, 4, 0, 1, 0, 2, 1, 4, 2], 14
6, [2, 1, 2, 0, 2, 5, 3, 5, 5, 3, 3, 3, 1], 13
7, [1, 2, 1, 5, 1, 1, 6, 5, 2, 2, 5, 1], 12
8, [0, 2, 6, 5, 1, 0, 5, 6, 7, 1, 3], 11
9, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8], 10
Для больших значений
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
потребуются огромные
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
. Например, для
![$k=16$ $k=16$](https://dxdy-02.korotkov.co.uk/f/1/3/1/1314fa91f4e8494ec669878fd1e6d96482.png)
Сергей Половинкин нашел
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
порядка
![$10^{273}$ $10^{273}$](https://dxdy-04.korotkov.co.uk/f/3/4/9/3493df01bf2f91c0e55a4f6d2fc36c6782.png)
. Похожие оценки получил и Алексей Волошин.
НаградыЗа правильное (более аккуратное, чем у ведущего) решение задачи ММ138 Дмитрий Пашуткин, Анатолий Казмерчук и Владислав Франк получают по 7 призовых баллов. Александр Ларин получает 6 призовых баллов, Алексей Волошин и Сергей Половинкин - по 4 призовых балла, Николай Дерюгин - 3 призовых балла.
Эстетическая оценка задачи 4.9 баллаРазбор задачи ММ138 подготовил Владимир Лецко