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

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

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

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

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

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

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

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

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

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

Ответ:

$2245$

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

Задача 5#103185

Назовём число $n$ волшебным, если оно делит число

( 1 1 -1--) (n− 1)!× 1+ 2 +3 +...+ n− 1 .

Найдите все волшебные числа $n$ в промежутке от $10$ до $100.$

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Разберите случай n = p*2, где p — простое. Что можно сказать о каждом из слагаемых после раскрытия скобок?

Подсказка 4

И, наконец, можно разобрать случай, когда n можно разложить в произведение a и b, где оба эти множителя больше 2. Как можно оценить a и b? Какие множители точно будут в числителях слагаемых?

Подсказка 5

Хотя бы одно из них небольшое, так что в числителях, кроме a и b, будут ещё числа, которые делятся на них ;)

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

Докажем, что в общем случае при $n> 9$ не являются волшебными числа только вида $n =2p$ , где $p$ — простое.

Для этого разберём три случая: когда $n$ является простым, когда $n∕2$ является простым, и когда ни $n$ , ни $n∕2$ не являются простыми (в частности, если $n$ нечётно, то $n∕2$ не является простым).

_________________________________________________________________________________________________________________________________________________________________________________

Первый случай. Если $n$ является простым. Рассмотрим выражение

( 1 1 1 ) (n− 1)! (n− 1)! (n− 1)!× 1+ 2 + 3 +...+ n-− 1 = (n − 1)!+--2--+ ...+ -n−-1-

по модулю $n.$ Утверждается, что среди слагаемых в этой сумме встретятся все возможные ненулевые остатки по модулю $n$ . Так как различных ненулевых остатков по модулю $n$ ровно $n− 1$ и слагаемых столько же достаточно показать, что все слагаемые дают различные остатки по модулю $n$ . Это действительно так, потому что в противном случае для некоторы $a$ и $b$ таких, что $1≤ a<$ $b≤ n− 1$ было бы верно сравнение

(n−-1)!≡ (n−-1)!(modn ) a b

Но перенеся в этом сравнении всё в левую часть, получаем

(n−-1)!− (n−-1)!≡ 1⋅2⋅...(a− 1)⋅(a+ 1)⋅...⋅(n− 1)− 1 ⋅2⋅...⋅(b− 1)⋅(b+ 1)⋅...⋅(n− 1)≡ a b

1⋅2⋅...⋅(a− 1)⋅(a+ 1)⋅...⋅(b− 1)⋅(b+1)⋅...⋅(n− 1)⋅(b− a) ≡0(modn),

что невозможно, так как все множители в произведении не делятся на $n$ , а $n$ — простое. Полученное противоречие доказывает, что слагаемые являются всеми возможными остатками по модулю $n$ , а значит, им сумма равна $n(n−1) 2$ , то есть кратна $n$ , так как $n$ простое, большее $9,$ а следовательно, нечётно.

_________________________________________________________________________________________________________________________________________________________________________________

Второй случай. Если $n∕2$ является простым. Обозначим $n∕2$ через $p,$ тогда $n =2p.$ Заметим, что среди чисел от $1$ до $n − 1$ есть только одно, кратное $p$ : это само число $p$ . Тогда при раскрытии скобок в выражении

( 1 --1-) (n− 1)!× 1+ 2 +...+ n − 1

все слагаемые кроме $1 (n− 1)!× p$ будут кратны $p,$ а это слагаемое — не будет. Значит, и вся сумма не будет кратна $p$ , а следовательно, и $2p$ , то есть $n$ . Значит, в этом случае число магическим не является.

_________________________________________________________________________________________________________________________________________________________________________________

Tретий случай. Если ни $n,$ ни $n∕2$ не являются простыми. В этом случае $n$ можно представить в виде произведения (т. к. $n$ непростое), причём оба множителя будут больше $2$ (так как либо $n$ , поделённое на любой нечётный простой делитель будет больше двойки, либо $n$ — степень двойки, но в силу $n >9,$ степень двойки хотя бы четвёртая, и значит, $n =4 ⋅ n4$ , где оба множителя больше $2$ ). То есть для некоторых $a,b>2$ верно $n= a⋅b$ . Тогда раскрывая скобки в выражении

( ) (n− 1)!× 1+ 1 +...+--1- n n − 1

получаем слагаемые вида $(n− 1)!⋅ 1 c$ , где $c⁄= a,b$ , и два слагаемых

(n− 1)!⋅ 1,(n− 1)!⋅ 1. a b

Во всех слагаемых первого вида в произведении $(n− 1)!$ содержатся множители $a,b$ и $c$ , а значит, после сокращения на $c$ оставшееся произведение будет делиться на $ab= n$ . Теперь заметим, что $2a <ab= n$ . Тогда в случае $2a⁄= b$ во втором слагаемом в произведении $(n− 1)!$ содержатся различные множители $a,2a,b,$ а значит, после сокращения на $a$ останется произведение $2a⋅b= 2n$ , кратное $n$ . Если же $2a= b$ , то $2 n= 2a$ , но тогда число $3a< n$ и $1 2 a⋅2a⋅3a⋅a = 6a$ кратно $n$ . Аналогично доказывается, что последнее, третье слагаемое, кратно $n$ , а значит, число является волшебным, так как все слагаемые кратны $n$ .

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ:

Все числа от $10$ до $100$ кроме $10,14,22,26,34,38,46,58,62,74,82,86,94$ .

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

Задача 6#103186

Существует ли множество натуральных чисел $A,$ для которого выполнены следующие свойства: всевозможные суммы двух элементов из $A$ уникальны (т.е. не бывает двух различных пар элементов, у которых суммы одинаковы), и при этом среди этих сумм можно найти $2020$ подряд идущих натуральных чисел.

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

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

Подсказка 1

Если вы обратились к подсказкам, то скорее всего вы устали от безрезультатных попыток доказать, что не существует. Дак вот, эта задача — конструктив. Нужно придумать пример)

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Чтобы добиться различности, давайте попробуем некоторые переменные приравнять к степени некоторого числа х от 1 до k-ой. Другие переменные определим как c - x + ..., c - x² + ..., c - x³ + ... и так далее. Что нужно поставить вместо точек, чтобы пример стал рабочим? И не забудьте его работоспособность доказать!

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

Приведём явный пример.

Рассмотрим числа вида

2 2 3 3 a1 = x,b1 =c− x+ 1,a2 =x ,b2 =c− x + 2,a3 = x ,b3 = c− x + 3,...,

k k 2020 2020 ...,ak = x ,bk =c− x + k,...,a2020 = x ,b2020 =c − x + 2020,

где

x= 10,c= 6⋅102020.

Тогда, очевидно, суммы вида

a1 +b1,a2+ b2,...,a2020+ b2020

равны $c+1,c+ 2,...,c+ 2020$ , то есть образуют $2020$ подряд идущих чисел. Осталось доказать, что среди попарных сумм пирведённых чисел нет совпадающих.

Разделим все суммы на три вида: первый вид $an +ak =xn +xk,$ второй вид $an+ bk =c+ xn− xk+ k,$ третий вид $b + b = 2c− xn− xk+ n+ k. n k$

______________________________________________________________________________________________________________________________________________________

Для начала докажем, что суммы из двух разных видов не равны между собой.

Предположим, что число второго вида и третьего вида равны между собой. Тогда для некоторых $n,k,l,m$ будет выполнено

an+ bk =c+ xn− xk+ k= bn +bk = 2c− xl− xm +l+ m =bl+ bm.

Перенося в этом равенстве все слагаемые без $c$ влево и оставляя справа только $c(2c− c= c),$ заметим, что $c$ больше, чем сумма модулей всех остальных слагаемых, а значит, равенства быть не может. Аналогично доказывается, что числа первого вида не могут быть равны числам второго и третьего видов.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Пусть есть $n ≥k$ и $m ≥ l$ такие, что пара чисел $(n,k)$ не совпадает с парой $(m,l)$ . Докажем, что не может быть равенства $bn+ bk = bm + bl.$

Действительно, если так, то после подстановки получаем равенство

− xn− xk +n +k =− xm − xl+m + l.

Если $n⁄= m$ , то без ограничения общности можно считать, что $n> m$ , но тогда $xn$ по модулю больше, чем все суммма модулей остальных $7$ слагаемых в равенстве, а значит, равенства быть не может. Если $n= m$ , то после сокращения равных слагаемых остаётся равенство

k l −x + k= −x +l,

причём в этом равенстве $k ⁄=l,$ так как изначальные пары были различны. Но тогда опять же не умаляя общности будет выполнено, что $k >l$ и $− xk$ по модулю будет больше, чем сумма модулей всех остальных членов в уравнении, что невозможно. Следовательно, все суммы третьего вида различны между собой.

Заметим, что при доказательстве того, что попарные суммы различны внутри второго типа нужно отдельно рассмотреть случаи, когда $n =k$ и $m = l,$ они будут образовывать наши подряд идущие числа, а следовательно, все различны. Во всех остальных случаях соображение о том, что какое-то слагаемое по модулю будет больше, чем сумма модулей остальных, по-прежнему работает.

Ответ: Да, существует