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

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

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

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

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

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

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

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

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

Задача 1#90449

Какое наибольшее количество непересекающихся троек попарно различных натуральных чисел можно выбрать среди чисел от $1$ до $2024$ так, чтобы в каждой тройке одно число равнялось произведению двух других?

Источники: Турнир Ломоносова - 2024, 11.2 (см. turlom.olimpiada.ru)

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

Подсказка 1

Так как нам дано условие про равенство одного из чисел тройки и произведения остальных, удобно упорядочить все тройки. То есть в тройке (a,b,c) получаем, что a < b < c. Теперь мы точно знаем, что c = a*b. Попробуйте оценить число a, использовав это равенство.

Подсказка 2

Супер! Теперь мы знаем, что a^2 < c. Но по условию c <= 2024, а значит a < 45. Тогда мы получаем, что всего троек не больше 44. Но пример построить не получается... Попробуйте предположить, что их 44, и использовать то, что все числа от 1 до 44 будут использоваться.

Подсказка 3

Посмотрите на тройку, содержащую число 1. Что можно сказать про числа в ней, используя условие про равенство одного из чисел тройки и произведения остальных?

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

Оценка.

Будем считать, что первое число в тройках минимальное из трёх, последнее — максимальное. Рассмотрим произвольную тройку $(a,b,c),$ где $ab= c$ . Ясно, что $2 a < ab= c$ , откуда $√ - √ ---- a < c≤ 2024$ , откуда $a≤ 44$ . Таким образом, первыми числами в тройке могут быть лишь числа от $1$ до $44$ . Значит, всего можно взять не больше $44$ троек, так как числа не повторяются.

Предположим, что можно взять ровно $44$ тройку. Тогда каждое из чисел от $1$ до $44$ будет первым числом в своей тройке. Но $1$ при умножении любого числа на себя даёт то же самое число, то есть в тройке оно быть не может. Стало быть, можно выбрать не более $43$ троек.

Пример.

Рассмотрим тройки вида $(t,89 − t,t(89− t))$ , где $t$ пробегает значения от $2$ до $44$ . Во-первых, ясно, что среди первых и вторых чисел этих троек нет одинаковых, так как $t≤44,89 − t≥ 45.$ Во-вторых, $t(89 − t)≤ 1980$ , то есть третьи числа в тройках не уходят за пределы $2024$ . В-третьих, минимум $t(89− t)$ равен $174> 89$ , а значит никакое третье число не совпадает с первыми и вторыми числами. Наконец, в-четвёртых, если $t1(89− t1)= t2(89− t2)$ и $t1 ⁄= t2$ , то либо $t1 =t2$ , что невозможно, либо $t1+t2 = 89$ , что также невозможно, потому что $t1+ t2 ≤ 43+ 44= 87< 89.$ Значит, пример удовлетворяет условию.

Ответ: 43

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

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

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

Задача 2#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.$

В первом случае при $p≥ 7$ получаем $n ≥ 126,$ при $p =5$ получаем $n =90,$ а

σ(90) =(1+ 2)(1+3 +9)(1 +5)= 234 <270

Во втором случае,

σ(n)= (1 +2+ 4)(1+ 3)(1+ p)=n ⋅ 7⋅ 4 ⋅ p+1 4 3 p

Если $σ(n)≥ 3n,$ то

p+-1≥ 9 p 7

Отсюда $p< 5,$ что неверно.

Аналогично, в третьем случае

σ(n) =(1+ 2)(1+ 3)(1+p)= n⋅ 3 ⋅ 4⋅ p+-1 2 3 p

Отсюда $p+1 p$ должно быть хотя бы $3 2,$ что неверно при $p≥ 5.$

Ответ: 120

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

Задача 3#93346

Найдите количество четвёрок положительных целых чисел $(a,b,c,d),$ таких, что $a≤ b≤ c≤ d$ и

a!⋅b!⋅c!⋅d!= 24!

Источники: Турнир Ломоносова - 2021, 11.2 (см. turlom.olimpiada.ru)

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

Подсказка 1

Сразу же оценим сверху d в силу нашего равенства. Раз мы имеем дело с факториалами, то сразу хочется посмотреть на делимость левой части на делители числа 24. Как за счёт этого мы можем ограничить наши переменные?

Подсказка 2

Верно! Левая часть делится на 23. Тогда d! точно делится на 23, а значит, и d делится на 23. Получаем, что 23 ≤ d ≤ 24. Теперь у d всего 2 возможных значения. Рассмотрите по отдельности оба случая и проделайте всё по аналогии с другими переменными.

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

Легко видеть, что $d≤ 24.$ Заметим, что правая часть равенства делится на $23$ , а значит, и левая часть должна делиться, откуда $d ≥23.$ Разберём два случая, чему может равняться $d:$

$− d= 24 :$ тогда $a!⋅b!⋅c!=1,$ откуда $a= b= c= 1;$

$− d= 23 :$ тогда $a!⋅b!⋅c!=24= 4!.$

Тогда, аналогично, или $c=4,$ или $c=3;$ разберём эти два случая:

$− c=4 :$ тогда $a!⋅b!= 1,$ откуда $a= b=1;$

$− c=3 :$ тогда $a!⋅b!= 4;$ небольшим перебором убеждаемся, что тогда $a =b =2;$

Итого, получаем три возможные четвёрки решений: $(1,1,1,24),$ $(1,1,4,23),$ $(2,2,3,23).$

Ответ:

$3$

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

Задача 4#93394

Фрэнк придумал способ кодирования чисел. Число $n$ кодируется числом $a n$ по следующим правилам: $a = 1; 1$ $a n$ получается из $a n−1$ так: Фрэнк смотрит, какие разряды в десятичной записи числа $n$ отличаются от соответствующих разрядов числа $n − 1,$ и увеличивает в десятичной записи числа $an−1$ на $1$ только самый левый из этих разрядов (при этом $9$ становится $0,$ а если разряда ещё не было, то Фрэнк считает, что в нём стоял $0$ ). Например, $a9 =9,$ $a10 = 19,$ $a11 = 10,$ $a12 =11.$ Найдите $k,$ если известно, что $ak = 2021.$

Источники: Турнир Ломоносова - 2021, 11.5 (см. turlom.olimpiada.ru)

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

Подсказка 1

Мы прибавляем 1 к какому-то разряду числа, при этом 0 → 1, 9 → 0, на какую операцию это похоже? Давайте пойдём от обратного - как получилось число 2021? Сколько раз прибавляли 1 к каждому из разрядов?

Подсказка 2

Конечно, операция является прибавлением 1 к разряду по модулю 10! Изначально у нас было число 0, тогда c₁ ≡₁₀ 2 раза добавили 1 к разряду тысяч, c₂ ≡₁₀ .... А сколько всего проделано операций? Не забудьте учесть, что меняется только левый разряд!

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

Что происходит, когда при увеличении $n− 1$ на $1$ меняются $s$ последних разрядов? Можно посмотреть на это так: мы к каждому из $s$ последних разрядов прибавляем $1$ по модулю $10.$ Способ кодирования Фрэнка состоит в том, что вместо прибавления $1$ ко всем разрядам мы прибавляем $1$ только к самому левому из них.

Тогда и способ декодирования становится понятен: как получилось число $ak = 2021?$ Мы $c1 ≡ 2$ раз прибавляли $1$ к разряду тысяч, $c2 ≡ 0$ — к разряду сотен, $c3 ≡ 2$ — к разряду десятков, $c4 ≡ 1$ — к разряду единиц. Тогда число $k$ получается, когда мы $c1 ≡ 2$ раз прибавляли $1$ к разряду тысяч, $c1+ c2 ≡2$ — к разряду сотен, $c1+ c2+c3 ≡ 4$ — к разряду десятков, $c1+ c2+c3+ c4 ≡ 5$ — к разряду единиц. Получается, что ответ $2245.$