Тема Региональный этап ВсОШ и олимпиада им. Эйлера

Регион 9 класс → .09 Регион 2022

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела региональный этап всош и олимпиада им. эйлера

Разделы подтемы Регион 9 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#125882Максимум баллов за задание: 7

Дан квадратный трёхчлен $P (x),$ не обязательно с целыми коэффициентами. Известно, что при некоторых целых $a$ и $b$ разность $P (a)− P(b)$ является квадратом натурального числа. Докажите, что существует более миллиона таких пар целых чисел $(c,d),$ что разность $P (c)− P (d)$ также является квадратом натурального числа.

Источники: Всеросс, РЭ, 2022, 9.3 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

P(x) — многочлен всего лишь второй степени. В таких случаях бывает очень полезно записать многочлен в общем виде, ведь тогда можно будет что-нибудь подставить и посмотреть наглядно, что происходит.

Подсказка 2:

Пусть P(x) = kx² + mx + n. При этом мы знаем, что P(a) − P(b) = s², где s ∈ ℕ. Подставим же в явном виде и попробуем преобразовать, вдруг что-то получиться? Не забывайте, что в преобразованиях часто бывают полезны формулы сокращённого умножения.

Подсказка 3:

Понятно, в каком направлении мы хотим преобразовывать, мы хотим разложить на скобки, ведь в терминах множителей работать с квадратами гораздо проще. Итого P(a) − P(b) = (a − b)(k(a + b) + m) = s². Теперь мы хотим научиться строить пары (c, d) с таким же свойством...

Подсказка 4:

Константа миллион взята с неба, поэтому пусть она не туманит наше сознание, будем доказывать, что таких пар бесконечно много. Предположим, что мы нашли такую пару (c, d). Пусть c + d = x(a + b) + y (деление с остатком). Подставим (c, d) в P(c) − P(d).

Подсказка 5:

Получаем (с − d)(kx(a + b) + m + ky) = t², где t ∈ ℕ. Можно ли адекватно понять, как изменились делители числа kx(a + b) + m + ky в сравнении с k(a + b) + m при нетривиальных значениях x и y?

Подсказка 6:

В общем виде уж точно нет! Поэтому нужно минимизировать влияние x и y на эту сумму. При каких x и y это "влияние" минимально или отсутствует вовсе?

Подсказка 7:

Разумеется, при (x, y) = (1, 0). То есть, для поиска адекватных пар (c, d) идея искать пары c + d = a + b очень даже полезна, ведь мы тогда знаем гораздо больше про то, как себя ведут множители (скобки). С суммой вроде бы определились, что же происходит с разностью?

Подсказка 8:

Осознайте, что если с + d = a + b, то с = a + z, d = b − z для z ∈ ℕ. Тогда c − d = a − b + 2z. Подставим эти значения в P(c) − P(d).

Подсказка 9:

P(c) − P(d) = (a − b + 2z)(k(a + b) + m). Снова поделим с остатком a − b + 2z = v(a − b) + u. То есть хотим, чтоб (v(a − b) + u + 2z)(k(a + b) + m) было квадратом. Что тогда мы хотим сделать с u?

Подсказка 10:

Конечно, мы хотим снова занулить константу, чтоб уменьшить "влияние". То есть теперь хотим брать такие z, что c − d = v(a − b) (очевидно, это возможно, осознайте самостоятельно). Теперь хотим, чтоб v(a − b)(k(a + b) + m) было квадратом, при этом знаем, что (a − b)(k(a + b) + m) = s². Чем тогда должно быть v?

Подсказка 11:

Разумеется, квадратом. То есть хотим сделать так, что для g ∈ ℕ: a − b + 2z = (a − b)g², то есть (a − b)(g² − 1) = 2z. Кажется, осталось совсем немного) Сделайте последний шаг и осознайте, что победа за Вами. Успехов!

Показать доказательство

Пусть $P(x)= kx2+mx + n.$ По условию, $P(a)− P (b)= s2,$ где $s∈ ℕ.$ Запишем разность:

2 P (a)− P(b)= (a− b)(k(a+ b)+m )=s .

Рассмотрим пары $(c,d)$ такие, что $c+ d= a+ b$ и

2 c− d= (2n +1) (a− b), n∈ ℤ

Тогда:

c = (a+-b)+(2n+-1)2(a− b), 2

(a+-b)− (2n+-1)2(a−-b) d = 2 .

Подставим $c$ и $d$ в $P(c)− P(d):$

P(c)− P(d)=(c− d)(k(c+ d)+m )=

(2n+ 1)2(a − b)(k(a+ b)+ m)= (2n+ 1)2s2.

Это выражение является квадратом натурального числа $(2n+ 1)s.$

Для целочисленности $c$ и $d$ требуется, чтобы числители в выражениях для $c$ и $d$ делились на 2. Поскольку $2 (2n+1) (a − b)$ имеет ту же чётность, что и $a− b,$ а $a+ b$ фиксировано, условие выполняется для всех целых $n.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#134306Максимум баллов за задание: 7

Петя написал на доске десять натуральных чисел, среди которых нет двух равных. Известно, что из этих десяти чисел можно выбрать три числа, делящихся на 5. Также известно, что из написанных десяти чисел можно выбрать четыре числа, делящихся на 4. Может ли сумма всех написанных на доске чисел быть меньше 75?

Источники: ВСОШ, РЭ, 2022, 9.1, 10.1 и 11.1 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте придумать пример таких чисел.

Подсказка 2:

Добавьте в набор число 20. Оно одновременно делится на 4 и на 5. Осталось взять два маленьких числа, кратных 5, и три числа, кратных 4.

Показать ответ и решение

Пример: $1,$ $2,$ $3,$ $4,$ $5,$ $6,$ $8,$ $10,$ $12,$ $20.$ В этом наборе три числа $(5,10,20)$ делятся на 5, четыре числа $(4,8,12,20)$ делятся на 4, а общая сумма равна $71.$

Ответ:

может

Ошибка.
Попробуйте повторить позже

Задача 3#134311Максимум баллов за задание: 7

На доске девять раз (друг под другом) написали некоторое натуральное число $N.$ Петя к каждому из 9 чисел приписал слева или справа одну ненулевую цифру; при этом все приписанные цифры различны. Какое наибольшее количество простых чисел могло оказаться среди 9 полученных чисел?

Источники: ВСОШ, РЭ, 2022, 9.2 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Как показать, что число не является простым? Например, если число делится на другое простое число и при этом больше него, то оно составное.

Подсказка 2:

Заметим, что в контексте задачи сумма цифр полученных чисел не зависит от того, с какой стороны дописывается цифра. Это значит, что есть смысл подумать, сколько чисел делятся на 3.

Показать ответ и решение

Пусть $S$ — сумма цифр числа $N.$ Тогда суммы цифр полученных чисел будут равны $S+ 1,$ $S+ 2,$ …, $S +9.$ Три из этих сумм будут делиться на $3.$ По признаку делимости на $3$ соответствующие три числа на доске также будут делиться на $3.$ При этом они будут больше $3,$ а значит, будут составными. Поэтому больше 6 простых чисел на доске оказаться не может.

Шесть простых чисел может оказаться даже при $N = 1$ — например, если Петя получит, среди прочих, числа $11,13,41,61,17$ и $19.$

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 4#134316Максимум баллов за задание: 7

В компании некоторые пары людей дружат (если $A$ дружит с $B,$ то и $B$ дружит с $A$ ). Оказалось, что среди каждых 100 человек в компании количество пар дружащих людей нечётно. Найдите наибольшее возможное количество человек в такой компании.

Источники: ВСОШ, РЭ, 2022, 9.4 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте придумать какой-нибудь простой пример и далее уже строить оценку.

Подсказка 2:

Есть очевидный пример на 101 — цикл из 101 вершины. Осталось показать, что 102 быть не может.

Подсказка 3:

Чтобы это доказать, попробуйте рассмотреть всевозможные варианты удаления двух вершин из графа на 102 вершинах. Пусть при i-м способе в графе осталось aᵢ рёбер. Рассмотрите сумму всех aᵢ, посчитайте её несколькими способами.

Подсказка 4:

На самом деле интересны не конкретные значения, а чётность этой суммы при разных способах подсчёта.

Подсказка 5:

Если доказывать от противного, то все aᵢ нечётные. А что получится, если посчитать, сколько раз каждое ребро учтено в этой сумме?

Показать ответ и решение

Во всех решениях ниже мы рассматриваем граф дружб, в котором вершины — это люди в компании, а два человека соединены рёбром, если они дружат.

Если граф — это цикл, содержащий 101 вершину, то на любых 100 вершинах ровно 99 рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из 102 человек (тогда и компании из более чем 102 человек тоже быть не может). Ниже мы приведём несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

_________________________________________________________________________________________________________________________________________________________________________________

Первое решение. Рассмотрим произвольное множество из 101 вершины и индуцированный подграф на этих вершинах, пусть в нём $k$ рёбер. Выбрасывая из этого подграфа произвольную вершину (скажем, степени $d$ ), получаем 100 вершин с нечётным количеством рёбер $k− d.$ Значит, степень любой вершины в нашем подграфе имеет чётность, отличную от чётности $k,$ то есть степени всех вершин подграфа имеют одну и ту же чётность. Но, как хорошо известно, в графе из нечётного числа вершин все вершины не могут иметь нечётную степень. Поэтому все эти степени чётны, а число рёбер $k$ нечётно.

Пусть теперь во всём графе на 102 вершинах $ℓ$ рёбер. При выкидывании любой вершины (скажем, степени $d$ ) получается подграф с нечётным числом рёбер $ℓ− d;$ аналогично рассуждению выше получаем, что и во всём графе степени всех вершин имеют одинаковую чётность. Заметим, что наш граф не может быть пустым (т.е. не иметь рёбер) или полным (т.е. иметь все $C2102$ рёбер), иначе на любых 100 вершинах будет либо $0,$ либо $C2100 = 99⋅50$ рёбер, то есть чётное количество. Тогда найдётся вершина, соединённая хоть с какой-то другой вершиной, но не со всеми. Иначе говоря, есть вершины $u1,$ $v1$ и $v2$ такие, что $u1$ соединена с $v1,$ но не с $v2.$ Степени вершин $v1$ и $v2$ в исходном графе одной чётности, поэтому после удаления $u1$ они будут иметь разную чётность. Это невозможно по доказанному выше.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Существует всего $n= C2102 = 51 ⋅101$ способов выбросить две вершины из 102, оставив 100. Пронумеруем эти способы числами от 1 до $n.$ Пусть $ai$ — количество рёбер на оставшихся 100 вершинах в $i$ -м способе; по предположению, все числа $ai$ нечётны, а значит, нечётна и их сумма $S$ (поскольку число $n$ нечётно).

С другой стороны, рассмотрим любое ребро $uv.$ Это ребро учтено в числе $ai$ ровно тогда, когда вершины $u$ и $v$ не выброшены в $i$ -м способе, то есть когда выброшена какая-то пара из оставшихся 100 вершин. Это происходит в $k= (1002 )= 50⋅99$ способах. Итак, каждое ребро учтено в $S$ чётное количество $k$ раз, поэтому $S$ должно быть чётным. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

Случай 1. Пусть общее количество рёбер в графе нечётно. Тогда, выкидывая любую пару вершин, мы должны выкинуть из графа чётное число рёбер (чтобы осталось нечётное число). С другой стороны, если мы выкидываем вершины со степенями $d1$ и $d2,$ то число выкинутых рёбер равно $d1+ d2,$ если эти вершины не соединены рёбром, и $d1+d2− 1,$ если соединены. Отсюда следует, что вершины одинаковой чётности всегда не соединены рёбром, а вершины разной чётности — всегда соединены. Значит, если в графе $k$ чётных вершин и $ℓ$ нечётных, то чётные вершины имеют (чётную) степень $ℓ,$ а нечётные — (нечётную) степень $k.$ Это невозможно, ибо $k+ ℓ= 102.$

Случай 2. Пусть общее количество рёбер в графе чётно. Аналогично получаем, что вершины одинаковой чётности всегда соединены рёбром, а вершины разной чётности не соединены. Поэтому, если в графе $k$ чётных вершин и $ℓ$ нечётных, то чётные вершины имеют (чётную) степень $k− 1,$ а нечётные — (нечётную) степень $ℓ− 1.$ Это опять же противоречит равенству $k+ ℓ= 102.$

Ответ:

101

Ошибка.
Попробуйте повторить позже

Задача 5#135013Максимум баллов за задание: 7

Последовательность чисел $a ,a , 1 2$ …, $a 2022$ такова, что

3 3 an− ak ≥ n − k

для любых $n$ и $k$ таких, что $1 ≤n ≤2022$ и $1≤ k≤ 2022$ . При этом $a1011 =0.$ Какие значения может принимать $a2022$ ?

Источники: ВСОШ, РЭ, 2022, 9.6 и 11.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

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

Подсказка 2:

По всей видимости, вместо одного из индексов нужно подставить 2022. Но что подставить вместо второго, чтобы реализовать первую подсказку? В условии дано значение 1011-го члена. Почему бы не подставить 1011 вместо второго индекса?

Подсказка 3:

Учтите, подставить эти индексы можно двумя разными способами.

Показать ответ и решение

Записывая условие при $n =2022,$ $k= 1011$ и при $n =1011,$ $k= 2022,$ получаем

3 3 a2022 = a2022− a1011 ≥2022 − 1011

−a = a − a ≥ 10113− 20223, 2022 1011 2022

то есть $a2022 ≥ 20223 − 10113 ≥a2022.$ Отсюда и следует ответ.

Ответ:

3 3 3 a2022 =2022 − 1011 = 7⋅1011

Ошибка.
Попробуйте повторить позже

Задача 6#135015Максимум баллов за задание: 7

Петя разбил клетчатый квадрат $100×100$ некоторым образом на домино — клетчатые прямоугольники $1× 2,$ и в каждом домино соединил центры двух его клеток синим отрезком. Вася хочет разбить этот же квадрат на домино вторым способом, и в каждом своём домино соединить две клетки красным отрезком. Вася хочет добиться того, чтобы из каждой клетки можно было пройти в любую другую, идя по синим и красным отрезкам. Обязательно ли у него будет возможность это сделать?

Источники: ВСОШ, РЭ, 2022, 9.7 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте придумать пример, в котором такой возможности не будет.

Подсказка 2:

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

Показать ответ и решение

Первое решение. Занумеруем вертикали слева направо числами от $1$ до $100.$ Пусть $a$ — верхняя строка квадрата, а $b$ — строка сразу под ней. Пусть в Петином разбиении эти строки заняты вертикальными домино $a1 − b1,a2− b2,$ …, $a98− b98$ и горизонтальными домино $a99− a100,b99− b100.$ Очевидно, что оставшуюся часть доски можно разбить на домино (например, на горизонтальные), поэтому такое разбиение существует.

Предположим, что существует Васино разбиение на домино, удовлетворяющее требованиям задачи. Если в васином разбиении какая-то из клеток $a1,a2,$ …, $a98$ занята вертикальным домино, то это — то же домино, что и в Петином разбиении, и из этих двух клеток нельзя добраться до остальных. Поэтому в Васином разбиении обязательно должны присутствовать домино $a1− a2,$ $a3− a4,$ …, $a97− a98.$ Аналогично, клетки $a99$ и $a100$ не могут быть накрыты горизонтальными домино, поэтому они накрыты вертикальными домино $a99− b99$ и $a100− b100.$ Но тогда из четырёх клеток $a99,$ $a100,$ $b99,$ $b100$ нельзя попасть в остальные — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

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

Раскрасим все клетки в шахматном порядке в чёрный и белый цвета, и поставим на каждом синем отрезке стрелку от белой клетки к чёрной, а на красном — от чёрной к белой. Тогда из каждой клетки ведёт ровно одна стрелка, и в неё входит ровно одна. Тогда все клетки разбились на циклы, и, если Васе удалось, то получился один цикл из всех клеток.

Пусть $a$ — верхняя горизонталь, а $z$ — нижняя. Пусть в Петином разбиении присутствуют домино $a1− a2$ и $z2− z3$ (такое разбиение возможно, если, например, клетки $z1$ и $z100$ покрыть вертикальными домино, а все остальные домино сделать горизонтальными). Тогда эти отрезки будут ориентированы как $a1 → a2$ и $z2 → z3.$ Если они находятся в одном цикле, то этот цикл должен пройти от $a2$ к $z2,$ а затем от $z3$ к $a1.$ Но такие два пути должны иметь общую клетку, что невозможно.

Ответ:

не обязательно

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#135016Максимум баллов за задание: 7

В трапеции $ABCD$ диагональ $BD$ равна основанию $AD.$ Диагонали $AC$ и $BD$ пересекаются в точке $E.$ Точка $F$ на отрезке $AD$ выбрана так, что $EF ∥ CD.$ Докажите, что $BE = DF.$

Показать доказательство

Поскольку $AD ∥CB,$ треугольники $EAD$ и $ECB$ подобны, и потому

BE- BC- DE = AD.

Достроим треугольник $BCD$ до параллелограмма $BCDK$ (см. рисунок). Тогда треугольники $DEF$ и $DBK$ подобны, поэтому $DF DK DE-= DB-.$ Наконец, поскольку $DK = BC$ и $DB = DA,$ получаем

DF DK BC BE DE-= DB- = AD-= DE-,

откуда и следует, что $DF = BE.$

$PIC$

Ошибка.
Попробуйте повторить позже

Задача 8#135017Максимум баллов за задание: 7

На плоскости отмечены $N$ точек. Любые три из них образуют треугольник, величины углов которого в градусах выражаются натуральными числами. При каком наибольшем $N$ это возможно?

Источники: ВСОШ, РЭ, 2022, 9.9 и 10.8 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте сначала какой-нибудь пример. Ясно, что точки надо отмечать не каким-то произвольным образом на плоскости. Например, можно отмечать их на окружности, ведь там легко вычисляются углы.

Подсказка 2:

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

Подсказка 3:

Для этого можно ввести координаты, выбрать точку A с наибольшей ординатой и две точки B, C такие, что угол BAC максимален. Теперь подумайте, какое возникнет противоречие, если внутри угла будет хотя бы 178 отмеченных точек.

Показать ответ и решение

Пример. Покажем сначала, что при $N = 180$ требуемое возможно. Отметим на окружности 180 точек, разбивающих её на 180 равных дуг величиной по $∘ 2$ каждая. Величина любой дуги с концами в двух из отмеченных точек выражается чётным числом градусов, поэтому величина любого вписанного в окружность угла, образованного тремя отмеченными точками, выражается натуральным числом градусов. Следовательно, 180 отмеченных точек удовлетворяют условию задачи.

Теперь докажем оценку $N ≤ 180,$ это можно сделать несколькими способами.

_________________________________________________________________________________________________________________________________________________________________________________

Первый способ. Осталось доказать, что $N ≤ 180.$ Любые три отмеченных точки образуют треугольник, поэтому не могут лежать на одной прямой. Считая отмеченные точки расположенными на координатной плоскости, обозначим через $A$ любую из них с максимальной ординатой. Среди оставшихся выберем точки $B$ и $C$ такие, что угол $BAC$ максимален.

Из условия задачи следует, что в треугольнике $ABC$ величины углов $ABC$ и $ACB$ не меньше $1∘,$ поэтому величина угла $BAC$ не больше $178∘.$ Ввиду выбора точек $B$ и $C$ остальные $N − 3$ отмеченные точки лежат строго внутри угла $BAC,$ и каждый луч с началом в точке $A$ содержит не больше одной из них. Проведя через каждую отмеченную точку внутри угла $BAC$ луч с началом в точке $A,$ получим $N − 3$ различных луча, делящих $∠BAC$ на $N − 2$ угла. Если $N − 2> 178,$ то хотя бы один из этих углов имеет величину, меньшую $1∘,$ и является углом некоторого треугольника с вершинами в трёх отмеченных точках, что противоречит условию задачи. Следовательно, $N − 2≤ 178,$ то есть $N ≤180,$ что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Рассмотрим пару отмеченных точек $A,$ $B$ на наибольшем расстоянии друг от друга. Тогда для любой другой отмеченной точки $C$ сторона $AB$ — наибольшая в треугольнике $ABC,$ поэтому, в частности, угол $∠BAC$ острый.

Проведя из точки $A$ лучи во все отмеченные точки, получаем, что все эти лучи различны (ибо три отмеченных точки не могут лежать на одной прямой), и каждый составляет с лучом $AB$ острый угол, выражаемый целым числом градусов. Такой угол (если луч не совпадает с $AB$ ) может принимать значения от $1∘$ до $89∘,$ поэтому количество таких лучей $N − 2$ не превосходит $2⋅89= 178.$ Отсюда $N ≤ 180.$

Ответ:

180

Ошибка.
Попробуйте повторить позже

Задача 9#135020Максимум баллов за задание: 7

Докажите, что существует натуральное число $b$ такое, что при любом натуральном $n> b$ сумма цифр числа $n!$ не меньше $100 10 .$

Источники: ВСОШ, РЭ, 2022, 9.10 и 10.10 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Нужна какая-нибудь лемма, которая позволит оценивать сумму цифр некоторых чисел. Условие задачи даёт много свободы, можно выбрать любое b. Значит, возможно, получится подогнать задачу под лемму.

Подсказка 2:

Через s(m) обозначим сумму цифр числа m. Если натуральное число m кратно 10ᵏ − 1, где k — также натуральное, то s(m) ≥ 9k. Докажите этот факт.

Подсказка 3:

Попробуйте доказывать по индукции. Распишите число m в виде 10ᵏu + v и сведите к меньшему числу.

Подсказка 4:

Для доказательства перехода понадобится следующий факт: s(a) + s(b) ≥ s(a + b). Докажите его, используя сложение в столбик.

Показать доказательство

Положим $a= 10100.$ Через $s(m)$ обозначим сумму цифр числа $m.$ Отметим простое свойство $s(ℓ)+ s(m) ≥s(ℓ+m ),$ которое сразу видно, если числа $ℓ$ и $m$ сложить в столбик.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $k$ — натуральное число, и пусть натуральное число $m$ кратно $k 10 − 1.$ Тогда $s(m)≥ 9k.$

Доказательство. Индукция по $m.$ База $k m =10 − 1$ очевидна.

Предположим, что $k m ≥ 10 ,$ и что утверждение доказано для всех чисел, меньших $m.$ Докажем его и для $m.$ Пусть последние $k$ цифр числа $m$ образуют число $v$ (возможно, с ведущими нулями), а все остальные — число $u >0$ (иначе говоря, $-- k m =uv =10 u+ v$ ). Поскольку $m$ делится на $k 10 − 1,$ то и (положительное) число

m′ = u+ v = m − (10k− 1)u

также кратно $k 10 − 1.$ Поэтому $′ s(m )≥ 9k$ по предположению индукции, а тогда

′ s(m )=s(u)+s(v) ≥s(u+v)= s(m )≥ 9k.

______________________________________________________________________________________________________________________________________________________

Для решения задачи осталось взять такое $k,$ что $9k ≥a,$ и заметить, что если $b= 10k− 1$ и $n ≥b,$ то $n!$ делится на $10k − 1$ и, значит, $s(n!)≥ 9k ≥a.$

Предыдущая подтема

Следующая подтема