Решение задачи MM138 IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики
======= 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}$
Попробуем подобрать $g$ и $n$ так, чтобы все выражения в левых (и правых) частях неравенства были очень близки друг к другу.
Для этого нужно, чтобы функция $f(x)=(g+x)^{n-x}$ была почти постоянна, а для этого ее производная $f'(x)=(g+x)^{n-x}\cdot \left(\frac{n-x}{g+x}-\ln(g+x)\right)$ должна мало отличаться от нуля.
Для этого $n$ должно быть близко к $g\ln g$. Выберем $g$ и в качестве $n$ возьмем $\lceil g\ln g\rceil$.
Тогда $\frac{n-x}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$. Значит функция убывает и принимает максимальное значение на границе интервала. Поэтому от всех оценок для $a$ сверху достаточно оставить одну: $(g+k)^{n-k}>a$.
Аналогично, рассматривая нижние оценки, получаем: $h'(x)=(g+x)^{n-x-1}\cdot \left(\frac{n-x-1}{g+x}-\ln(g+x)\right)$ и $\frac{n-x-1}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$.
Поэтому из всех оценок снизу достаточно взять $a\ge g^{n-1}$.

Докажем, что при больших $g$ в интервале $\left(g^{n-1},(g+k)^{n-k}\right)$ найдется хотя бы одно натуральное число (оно-то и будет нашим $a$).
(Заодно мы докажем, что верхняя граница интервала действительно больше нижней.)
Достаточно доказать неравенство $(g+k)^{n-k}> 2g^{n-1}$. Тогда длина интервала будет велика и хотя бы одно число туда попадет.
Логарифмируем: $(n-k)\ln (g+k) > (n-1)\ln g +\ln 2$
$\left[g\ln g\right](\ln(g+k)-\ln g)-k\ln(g+k)+\ln g -\ln 2 > 0$
$\left[g\ln g\right](\ln(1+\frac{k}{g})-k\ln(g+k)+\ln g -\ln 2 > 0$
Как известно, $\ln(1+x) > x-\frac{x^2}{2}$ при малых $x$, поэтому достатчно будет доказать
$(g\ln g -1)\left(\frac{k}{g}-\frac{k^2}{2g^2}\right)-k\ln(g+k)+\ln g - \ln 2 > 0$
$\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 > \ln 2 +\frac{k}{g}-\frac{k^2}{2g^2}+\frac{k^2\ln g}{2g}+k\ln(1+\frac{k}{g})$
Очевидно, это верно при больших $g$ поскольку в правой части все слагаемые, кроме первого, стремятся к 0 с ростом $g$.
Остается взять подходящее $g$, по нему $n$ и по ним $a$.< Обсуждение

Приведу пример для $k=5$: Пусть $a=3486784400$ (в десятичной системе). Ниже приводится (обратная) запись $a$ для систем с основаниями от 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$ потребуются огромные $g$. Например, для $k=16$ Сергей Половинкин нашел $a$ порядка $10^{273}$. Похожие оценки получил и Алексей Волошин.

Награды

За правильное (более аккуратное, чем у ведущего) решение задачи ММ138 Дмитрий Пашуткин, Анатолий Казмерчук и Владислав Франк получают по 7 призовых баллов. Александр Ларин получает 6 призовых баллов, Алексей Волошин и Сергей Половинкин - по 4 призовых балла, Николай Дерюгин - 3 призовых балла.

Эстетическая оценка задачи 4.9 балла

Разбор задачи ММ138 подготовил Владимир Лецко

Задайте вопрос на блоге о математике