МатОлимп #14⁠⁠

Сегодня рассмотрим задачу интереснее и сложнее предыдущей. Условие выглядит так :

Дадим подумать некоторое время тем, кто сам хочет прорешать задачку!

А теперь начнем решать. Для начала заметим, что

Обозначим число цифр у числа n как p(n). Тогда из нашего неравенства мы сразу замечаем, что

Дальше будем решать от противного. Предположим, что у первого числа в условии цифр больше, чем у второго. Но максимальное число, у которого ровно m, цифр есть 10^(m)-1. Таким образом мы получаем следующее:

Также легко увидеть следующее:

Отсюда мы получаем

С другой стороны

Итак, мы получили двойное неравенство.

Так как k>3n, число посередине явно натуральное. Отсюда сразу же следует

Итак, мы вышли на финишную прямую. Если n=0 или n=1, то наши числа содержат одинаковое число цифр. Если же n>1, то

Но с другой стороны

Во второй строчке я воспользовался биномом Ньютона. Заметим, что 1+3^n не делится на 8 для всех n>0.

Итак, мы пришли к противоречию, которое и завершает наше доказательство от противного! Теперь можно идти пить кофе!