Теория чисел на Турломе —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на Турломе

Тема ТурЛом (турнир Ломоносова)

Теория чисел на Турломе

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

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

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

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

Подтемы раздела турлом (турнир ломоносова)

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

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

Задача 1#76579

При каком наименьшем $n$ все натуральные делители числа $n$ можно поделить на три группы, суммы в которых равны? Если группа состоит из одного числа, то сумма чисел в этой группе равна этому одному числу.

Источники: Турнир Ломоносова-2022, 11.4

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

Подсказка 1

Вспомните для начала, как считать сумму делителей числа, или выведите. Это несложно. Давайте подумаем в общем о природе групп. Какая может быть минимальная сумма делителей у одной группы?

Подсказка 2

Верно, так как в какую-то группу попадёт число n, а это делитель n, то сумма должна быть равна минимум n. Тогда о каком примере можно подумать? Попробуйте перебрать не слишком большие числа, где сумма делителей будет хотя бы 3n.

Подсказка 3

Да, это число 120, сумма его делителей 360. Поэтому у нас получатся группы (120), (40, 20, 60) и в последней группе остальные числа. Отсюда получается и идея для доказательства оценки. Если число будет меньше 120, то сумма его делителей будет меньше 3n. Как тогда можно оценить самым грубым образом сумму делителей в общем виде?

Подсказка 4

Верно, если предположить, что геометрическая прогрессия бесконечная, то это запишется просто как n на произведение дробей вида p/p-1. Как можно оценить сколько простых делителей входит в n при наших условиях?

Подсказка 5

Да, давайте просто переберём все наши возможности. Это когда n просто степень простого числа, когда n произведение двух степеней простых. Рассмотрев ещё, что будет происходить с 3 делителями или больше, получим, что n содержит ровно 3 простых делителя. А можем ли мы сказать, из каких точно делителей должно состоять n?

Подсказка 6

Верно, маленьким перебором получится, что n представляется в одном из трёх видов 2*3²*p, 2²*3*p, 2*3*p, где p простое число. Теперь только осталось разобрать их, и мы получим оценку на число 120. Победа!

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

Заметим, что $120 =23⋅3⋅5,$ поэтому сумма всех делителей числа $120$ равна $(1+2 +4+ 8)(1+ 3)(1+ 5) =15⋅4⋅6= 360.$ Поэтому нам надо поделить делители в группы с суммой $120.$ Подойдут группы ${120}$ , ${20,40,60}$ и все оставшиеся числа.

Докажем теперь, что делители чисел меньше $120$ нельзя поделить на три группы с равной суммой. Для этого докажем, что если $n$ меньше $120,$ то сумма делителей числа $n$ меньше $3n.$ Поскольку у $n$ всегда есть делитель, равный $n,$ то сумма в одной группе должна быть хотя бы $n,$ на этом и будет построено противоречие.

Вспомним, что сумма делителей числа $α1α2 αs n= p1 p2 ...ps$ равняется

( )( ) ( ) σ(n)= 1+ p1 +p21+ ...+ pα11 1+ p2+p22+ ...+ pα22 ...1+ ps+ p2s +...+ pαss

Следовательно

( 1 1 ) ( 1 1 ) ( 1 ) σ(n)= n 1 +p1 +...+ pα11 ... 1+ ps + ...+ pαss < n 1 +p1 +... ...

( ) ... 1+ 1-+ ... = n⋅--p1-...-ps-- ps p1− 1 ps− 1

В неравенстве мы заменили конечную сумму геометрической прогрессии на бесконечную.

Пусть теперь $n$ — некоторое число. Если у $n= pa,$ то

--p- σ(n)< n⋅p− 1 ≤2n< 3n,

поскольку число $p 1 p−-1 = 1+ p−1$ тем больше, чем меньше $p.$

Аналогично, если $n =pa⋅qb,$ то

p q 2 3 σ(n)< n⋅p−-1q−-1 ≤n2-− 1 ⋅3− 1-= 3n

Итак, если $σ(n)≥3n,$ то в разложение $n$ входит хотя бы 3 простых числа. Поскольку уже $2 ⋅3 ⋅5 ⋅7 =$ $210> 120,$ то нас интересуют лишь $n,$ в разложении которых ровно три простых числа.

Если среди этих простых чисел нет $2:$ если среди них нет и $3,$ то $n ≥$ $5 ⋅7 ⋅11 >120,$ значит $3$ есть; если нет $5,$ то $n ≥3⋅7⋅11> 120,$ значит и $5$ есть; если нет $7,$ то $n≥ 3⋅5⋅11 >120,$ значит и $7$ есть. Тогда $n =3⋅5⋅7= 105$ (добавление ещё одного простого сделает $n$ больше $120$ ), сумма делителей которого равна $(1 +3)(1+ 5)(1+ 7)=192< 315.$ Значит, $n$ обязательно делится на $2.$

Пусть третий простой делитель $p.$ Заметим, что $2⋅3⋅p≥ 30;$ поскольку мы ищем $n< 120,$ то домножить $2⋅3⋅p$ мы можем максимум на $3.$ Итак, получили всего немного вариантов: или $n =2 ⋅32⋅p$ , или $n =22⋅3⋅p$ , или $n =2 ⋅3 ⋅p.$