Работа с длинными числами

Обозначим Докажем, что

Это неравенство из-за области значений эквивалентно возведённому в квадрат:

Теперь правое неравенство очевидно в силу , а левое тоже в силу

Тогда получаем, что

где

Рассмотрим число в двоичной системе счисления:

где При умножении на получаем:

Целая часть соответствует числу, составленному из первых цифр двоичного представления. Последняя цифра этого числа в двоичной системе —

Поскольку иррационально, его двоичная запись содержит бесконечно много нулей. При последняя цифра числа в двоичной системе равна следовательно, само число чётно, значит, существует бесконечно много различных четных и бесконечное количество составных чисел вида

Легко проверить, что число

подходит. Действительно, при записи задом наперед оно равно

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Покажем, как можно было бы придумать такое число на олимпиаде. Обозначим это число где — первые три и последние три числа в его записи. На месте многоточие стоят какие-то цифры.

Тогда Значит, так как — результат умножения натурального числа с первой цифрой, не меньшей на так как иначе при умножении на в числе увеличится количество знаков. Тогда Помимо того, делится на значит, четно, поэтому Также кончается на при Так как то

Далее из равенства по цифре можно однозначно определить цифру которая к тому же должна быть нечетная и меньше Получаются варианты и из которых подходит только второй.

Аналогичным образом пытаясь найти и получаем два возможных варианта: и Развивая второй вариант, можно понять, что все числа вида подходят.

Число равно Тогда

Выполняя арифметические операции, получим число

В нем 2 «участка» из 39999 и 40000 девяток соответственно. Итого, 79999 девяток.

Понятно, что это число делится на так как раскладывается через сумму, где каждое слагаемое делится на Очевидно, что сумма цифр тоже равна

Десятичная запись данного числа имеет вид где — первые цифр числа а состоит из цифр: последние цифр числа за которыми следуют первые цифр. Предположим, что это число — степень двойки. Поскольку оно -значное, оно больше чем а значит, оно делится на Следовательно, число (последние цифр данного числа) тоже делится на так как разность всего числа и числа из его последних 100 цифр делится на а значит, и на Число равно произведению числа и нечетного числа вида Следовательно, тоже делится на Но Противоречие.

Лемма. Пусть — натуральные числа, Тогда существует число, делящееся на десятичная запись которого представляет многократно повторенную запись числа

Доказательство. Среди чисел есть два числа, дающих одинаковый остаток при делении на (если взять достаточно много чисел больших, чем ). Возьмем их разность и отбросим нули на конце.

_________________________________________________________________________________________________________________________________________________________________________________

Тогда по лемме возьмём в качестве просто произведение всех -значных чисел, составленных из Это число будет, очевидно, взаимно просто с и Теперь в качестве числа для выполнения условия задачи можно взять число, которое содержит сначала очень много единиц, потом очень много троек, семёрок и девяток. Снова получаем по лемме, что каждый блок по отдельности делится на (либо же можно сослаться на то, что приписывание нулей после блока цифр на делимость не влияет). Тогда и всё число тоже будет делится.

Заметим, что

Аналогично,

Тогда

Значит, число целое, причем так как Отсюда а ответ равен

Заметим, что

Тогда из условия получим

Следовательно, по признаку делимости на 9

Разделим число на . Получим число

Сначала заметим, что не существуют двузначных чисел, делящихся на или , содержащих , или в своей записи. Поэтому в специальных числах таких цифр быть не может. Заметим, что рядом с цифрой в специальном числе может идти только цифра , а рядом с цифрой может идти только цифра . То есть специальных чисел, содержащих или , ровно (в которых чередуются и ). Заметим, что не существует двузначных чисел, делящихся на или на , начинающихся на цифру . Поэтому цифра может стоять в специальном числе только на последнем месте. Перед ней будет , перед будет , перед цифра , дальше , потом опять , и так далее. Аналогично все однозначно восстанавливается, если в конце специального числа стоят цифры . Таким образом, всего специальных чисел .

Обозначим самое большое выписанное число через . Минимальная сумма синих чисел равна

Максимальная сумма красных чисел равна

Так как , отношение суммы красных чисел к сумме синих меньше трех, значит, если все-таки сумма красных чисел делится на сумму синих, частное равно 1 или 2.

В первом случае мы получаем, что суммы красных чисел и синих чисел должны быть равны, поэтому сумма всех выписанных на доску чисел должна быть четна. При этом половина, а именно , чисел нечетна. Поэтому сумма всех чисел на самом деле нечетна, и частное не может быть равно 1.

Во втором случае обозначим сумму синих чисел через . Сумма красных чисел равна , а сумма всех выписанных чисел равна , то есть делится на 3. На самом же деле сумма выписанных чисел равна

Признак делимости на 3 гласит: натуральное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Сумма цифр числа равна 4 , а сумма цифр числа равна 5 . Поэтому оба этих числа не делятся на 3 , тогда и сумма всех выписанных чисел на 3 не делится, и второй случай также невозможен.

Давайте для удобства считать, что и , иначе вычтем целую часть дробей, не изменив дробную часть, получив и в нужном диапазоне (условие на несократимость дробей останется). Скажем, что

(1)

— количество цифр в записи , – количество цифр в записи ( и — периоды наших дробей).

Рассмотрим последовательно написанный раз (такая последовательность в первой дроби есть), по условию она же есть, и во второй, причём в ней цифр, значит, во второй дроби эта последовательность является сдвигом , записанным раз. Тогда скажем, что во второй дроби построенная последовательность перед первым имеет кусок , оставшийся кусок из назовём , то есть . Тогда эта же последовательность во второй дроби выглядит как , , написанный раз, и остаток , причём . Обозначим рассматриваемую последовательность за (), тогда:

(2)

(3)

Скажем, — количество цифр в , —- количество цифр в . Тогда верно следующее:

(4)

(5)

(6)

Вычитая (2) из (4) и (5) из (6) соответственно, получаем:

(7)

(8)

Подставим из (7) равенства в (8), получим:

Вспомним, что пары чисел и взаимно просты. Значит, и .

Докажем, что и взаимно просты. Из (1):

ибо и взаимно просты.

Если НОД — простое, то уж точно на не делится, но тогда и на делиться не может, противоречие, тогда рассматриваемый НОД равен 1, что эквивалентно искомой взаимной простоте, откуда следует, что . Тогда у нас и , что и требовалось.

Как такое представление придумать? Можно заметить, что это стозначное число составляет примерно треть от числа , которое легко записать так, чтобы сумма цифр была маленькой.

Также не надо бояться большого количества цифр: многие из них могут не нести принципиального значения.

Рассмотрим само число . Пусть наш палиндром оканчивается на . Если нулей будет хотя бы 8, то число точно поделится на , так как последние 12 цифр образуют число, делящееся на .

Осталось сделать это число палиндромом. Пусть число начинается на 6904, а остальные цифры будут нулями. Тогда искомое число — , где нулей между 4-значными числами 92 штуки.

Заметим, что . Поэтому в квадрат мы будем возводить именно такое представление числа . Получаем, что . Числитель равен , где 8 стоит на 101-й позиции. При делении на 9 все девятки превратятся в единицы (в количестве 99 штук), а число . Поэтому после деления на 9 получится число , где единиц и восьмерок по 99 штук. Сумма же цифр такого числа равна .

1)

2)

3)

1)

2)

Возьмем . Тогда все наше число делится на , а значит, и на любое число вида , где . Значит, наше число делится на числа и на их произведение (так как суммарная степень по двойкам и пятеркам равна 55). Тогда число , где отлично от от всех других сомножителей.

Сумма цифр , так как каждая ненулевая цифра встречается по 10 раз в разряде единиц и в разряде десятков, а единица еще участвует в числе 100.

Умножение на два — это сложение . Заметим, что при сложении в каждом переходе через разряд мы теряем 9 из удвоенной суммы цифр числа . Посчитаем количество переходов через разряд. Переход случается только при складывании хотя бы 5 в этом числе. Тогда количество переходов = количеству 5, 6, 7, 8 и 9 в этом числе. Как мы раньше узнали, количество таких цифр в числе = . Тогда сумма цифр .

Пусть это число . Если (то есть в ровно знаков), то , то есть в числе или знаков. Так как у нас 2016-значное число (то есть четное), то .

.

Рассмотрим . Возьмем . Тогда . В этом числе видно, что на среднее число 2016 ничто не наложится.