Тема ТЕОРИЯ ЧИСЕЛ

Оценка + пример в задачах по теории чисел

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

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

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

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

Подтемы раздела теория чисел

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

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

Задача 1#104692

На окружности через равные промежутки отметили 144 точки и провели все возможные хорды между ними. Хорду с концами в отмеченных точках назовем “чётной”, если на большей дуге, которую она стягивает, лежит чётное число точек. В противном случае хорда “нечётная”. Рядом с каждой вершиной написано число. Сумма квадратов этих чисел равна 36. На каждой хорде написано произведение чисел, стоящих на её концах. Сумма чисел на «чётных» хордах равна $a$ , сумма чисел на «нечётных» хордах равна $b$ . Найдите наибольшее возможное значение величины $a− b$ .

Источники: ОММО - 2025, номер 2 (см. olympiads.mccme.ru)

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

Подсказка 1

Заметим, что чётность дуги не зависит от того рассматривать меньшую дугу или большую. Мы хотим рассмотреть какое-то выражение, в котором будем рассматривать все попарные произведения чисел в точках, а ещё знаем сумму квадратов. Каким тогда может быть это выражение?

Подсказка 2

Да, это очень похоже на какой-то квадрат суммы! Теперь мы хотим, чтобы точки с одной чётностью номеров были с плюсом, а с разными — нет. Как тогда нужно расставить знаки внутри квадрата?

Подсказка 3

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

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

Обозначим числа, стоящие рядом с точками на окружности, как: $a,a ,...,a . 1 2 144$

Оценка. Рассмотрим произвольную хорду $anak,n < k.$ Пусть на большей дуге, которую она стягивает, лежит $x$ точек. Тогда на меньшей дуге лежит $144− x− 2= 142− x$ точек. Очевидно, что числа $x$ и $142 − x$ одной чётности, поэтому мы можем определять чётность хорды по любой из дуг, которую она стягивает. Между точками $an$ и $ak$ лежит $n − k− 1$ точка, откуда мы можно сделать вывод о том, что хорда $anak$ чётная, если числа $n$ и $k$ разной чётности, и нечётная в противном случае.

Теперь рассмотрим следующее выражение:

(a1− a2+ a3− a4+⋅⋅⋅+a143 − a144)2

Раскроем скобки: в сумме будут квадраты и попарные произведения всех слагаемых, при этом, перед слагаемым $aiaj$ будет стоять минус, если числа $i$ и $j$ разной чётности, и плюс в противном случае. Сумма квадратов всех слагаемых равна 36, сумма всех чисел $aiaj,$ где $i$ и $j$ разной чётности, это сумма чисел на чётных хордах (посчитанная дважды!), которая равна $a.$ Аналогично, сумма всех чисел $aiaj,$ где $i$ и $j$ одной четности, равна удвоенной сумме чисел на нечётных хордах, то есть равна $2b.$ Таким образом, данное выражение равно:

(a1− a2+ a3− a4+ ⋅⋅⋅+ a143− a144)2 =36+ 2b− 2a

Тогда

2 2(a− b)=36− (a1− a2+ a3− a4 +⋅⋅⋅+ a143− a144) ≤ 36

Итак, максимальное значение $a − b$ равно 18.

Пример. $a = 1 i 2$ для всех $i.$

Ответ: 18

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

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

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

Задача 2#109558

На окружности через равные промежутки отметили $400$ точек и провели все возможные хорды между ними. Хорду с концами в отмеченных точках назовем “чётной”, если на большей дуге, которую она стягивает, лежит чётное число точек. В противном случае хорда “нечётная”. Рядом с каждой вершиной написано число. Сумма квадратов этих чисел равна $100.$ На каждой хорде написано произведение чисел, стоящих на её концах. Сумма чисел на “чётных” хордах равна $a,$ сумма чисел на “нечётных” хордах равна $b.$ Найдите наибольшее возможное значение величины $a− b.$

Источники: ОММО - 2025, номер 2 (см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Верно, они разной чётности! Теперь самое сложное — нужно придумать какое-то выражение, в котором будут участвовать все числа, данные нам в условии. В каком выражении мы можем встретить сумму квадратов и попарные произведения?

Подсказка 3

Верно, в каком-нибудь квадрате! Рассмотрите квадрат знакопеременной суммы чисел на окружности и аккаратно раскройте его:) Не забудьте привести пример!

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

Обозначим числа, стоящие рядом с точками на окружности, как: $a,a ,...,a . 1 2 400$

Оценка. Рассмотрим произвольную хорду $anak,n < k.$ Пусть на большей дуге, которую она стягивает, лежит $x$ точек. Тогда на меньшей дуге лежит $400− x− 2= 398− x$ точек. Очевидно, что числа $x$ и $398 − x$ одной чётности, поэтому мы можем определять чётность хорды по любой из дуг, которую она стягивает. Между точками $an$ и $ak$ лежит $n − k− 1$ точка, откуда мы можно сделать вывод о том, что хорда $anak$ чётная, если числа $n$ и $k$ разной чётности, и нечётная в противном случае.

Теперь рассмотрим следующее выражение:

(a1− a2+ a3− a4+⋅⋅⋅+a399 − a400)2

Раскроем скобки: в сумме будут квадраты и попарные произведения всех слагаемых, при этом перед слагаемым $aiaj$ будет стоять минус, если числа $i$ и $j$ разной чётности, и плюс в противном случае. Сумма квадратов всех слагаемых равна 36, сумма всех чисел $aiaj,$ где $i$ и $j$ разной чётности, это сумма чисел на чётных хордах (посчитанная дважды!), которая равна $a.$ Аналогично, сумма всех чисел $aiaj,$ где $i$ и $j$ одной четности, равна удвоенной сумме чисел на нечётных хордах, то есть равна $2b.$ Таким образом, данное выражение равно:

(a1− a2 +a3− a4+ ⋅⋅⋅+a399− a400)2 = 100+2b− 2a

Тогда

2 2(a − b)= 100− (a1− a2+ a3− a4 +⋅⋅⋅+ a399− a400) ≤ 100

Итак, максимальное значение $a − b$ равно 50.

Пример. $a = 1 i 2$ для всех $i.$

Ответ: 50

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

Задача 3#121764

Пусть $A$ — набор из $n> 1$ различных натуральных чисел. Для каждой пары чисел $a,b∈A,$ где $a< b,$ подсчитаем, сколько чисел в $A$ являются делителями числа $b− a.$ Какое наибольшее значение может принимать сумма полученных $n(n−1) 2$ чисел?

Источники: Турнир городов - 2025, устный тур, 11.3(см. turgor.ru)

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

Подсказка 1

Что нужно делать в первую очередь, когда проверяем делимость у каких-то элементов последовательности без привязи к их позиции?

Подсказка 2

Упорядочим числа набора! Подумайте, на каких позициях относительно двух элементов могут находиться делители их разности?

Подсказка 3

Для конкретного k и j найдите количество и aᵢ, таких что aⱼ - aᵢ делится на aₖ.

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

Сначала докажем оценку. Пусть $a < a < ⋅⋅⋅< a 1 2 n$ — элементы набора $A.$ Заметим, что разность вида $a − a j i$ при $i<j$ может делиться на $ak$ лишь при $k <j.$ Выберем любые $1≤k < j ≤n$ и посмотрим, сколько из чисел вида $aj − ai$ (при $i< j$ ) может делиться на $ak.$ Все такие числа при $i≤ k$ отличаются менее, чем на $ak,$ поэтому на $ak$ может делиться лишь одно из них. Значит, всего таких разностей может быть максимум $(j− k− 1)+ 1= j− k.$ Итого, получаем оценку:

∑ ∑n ∑n (j− k)= j(j− 1) = C2j = C3n+1 = (n+-1)n(n−-1) 1≤k<j≤n j=2 2 j=2 6

Это количество достигается, например, на наборе $2 n−1 1,2,2 ,...,2 .$ Здесь все неравенства из оценки обращаются в равенства, а значит, и оценка достигается.

Есть и другие примеры, в том числе, в которых все числа набора попарно взаимно простые, скажем,

a1 = 1,a2 = 2,a3 = 3,a4 =7,...,ak+1 =a1a2...ak+ 1

Ответ:

$C3 = (n+1)n(n−1)- n+1 6$

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

Задача 4#126640

У $n$ -значного числа первые две его цифры различаются на 1, вторая и третья — на $2,$ $...,$ предпоследняя и последняя — на $n− 1$ , последняя и первая — на $n.$ При каком наибольшем $n$ такое возможно?

Источники: ФЕ - 2025, 10.1 ( см. www.formulo.org)

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

Подсказка 1

Сколько всего у нас цифр? С учётом этого мы можем получить самую первую оценку на n.

Подсказка 2

Попробуем подобрать пример! Что можно сразу сказать про первую и последнюю цифры числа при таком n? А получится ли дальше заполнить число?

Подсказка 3

Как будто бы составить пример простым подбором не выходит. Значит надо искать противоречия или как-то ограничивать перебор! Попробуйте поработать с чётностью ;)

Подсказка 4

Ну что же, мы пришли к противоречию! Значит надо рассмотреть следующее подходящее n. Зафиксируйте начало и конец числа, а потом попробуйте также поработать с чётностью!

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

Так как разница между десятичными цифрами не превосходит 9, то $n≤ 9.$ Если бы такое девятизначное число существовало, то оно бы начиналось на 9 и заканчивалось на 0 (так как разность между первой и последней цифрой — $n).$ Из условия на разности соседних цифр, если выписать чётности, получится последовательность нччннччнн, но последнее число должно быть нулем — противоречие.

Пусть $n= 8,$ есть несколько примеров: 12473829, 87526170, 98637281.

Ответ:

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

Задача 5#127158

Дано натуральное число $n.$ Натуральные числа $1,2,...,n$ выписывают на доске в строчку в некотором порядке. У каждых двух стоящих рядом чисел вычисляют их НОД (наибольший общий делитель) и записывают этот НОД на листке. Какое наибольшее количество различных чисел может быть среди всех $n − 1$ выписанных на листке чисел?

Источники: ВСОШ, ЗЭ, 2025, 10.5 (см. olympiads.mccme.ru)

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

Оценка. Предположим, что какое-то из выписанных на листке чисел больше $⌊n∕2⌋,$ скажем, $НО Д(a,b)= d> ⌊n∕2⌋.$ Тогда наибольшее из чисел $a,b$ не меньше $2d,$ что больше $n$ – противоречие (НОД двух чисел, не превосходящих $n,$ не превосходит $n$ ). Значит, каждый из написанных $Н ОД$ ов не превосходит $⌊n∕2⌋,$ потому количество различных $Н ОД$ ов не может превышать $⌊n∕2⌋.$

Пример. Разобьём все числа от $1$ до $n$ на цепочки вида $k a,2a,4a,8a,...,2a,$ где $a$ — нечётное число, не превосходящее $n.$ Выпишем в строчку цепочки одну за другой. Тогда для любого натурального $d≤ ⌊n∕2⌋$ найдётся цепочка, в которой встречается $d,$ а следующее за $d$ число будет $2d.$ Видим, что каждое натуральное $d≤⌊n∕2⌋$ будет выписано на листке.

Ответ:

$⌊n⌋ 2$

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

Задача 6#128123

Император планеты Кибертрон приказал создать календарь наподобие земного, то есть разбить год на месяцы так, чтобы один месяц содержал 28 дней, а все остальные — либо 30 , либо 31. Кроме того, он пожелал, чтобы среди любых трёх последовательных месяцев был хотя бы один 31-дневный: «лишние» 31-е дни император планировал сделать всепланетными праздниками, а праздников хотелось побольше. Однако Мудрейший математик Кибертрона установил, что приказ Императора выполнить невозможно. Каким наибольшим числом может быть количество дней в году на планете Кибертрон, если известно, что это число — целое?

Источники: Изумруд-2025, 10.5 (см. izumrud.urfu.ru)

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

Пусть год на Кибертроне составляет $N$ суток. Приказ Императора может быть выполнен тогда и только тогда, когда для некоторых целых неотрицательных $m$ и $k$ выполняется

(| { N =28+ 30m + 31k |( k≥ k+ m+ k+-m-+1- 3

Назовём натуральные $N,$ представимые в указанном виде, приемлемыми, а выражение $28+ 30m + 31k$ — представлением $N.$ Найдем все приемлемые числа $N.$

______________________________________________________________________________________________________________________________________________________

Лемма.Пусть число $N$ — приемлемо. Тогда можно считать, что в его представлении $28 +30m +31,$ где $0≤ m ≤30,$ и такое $m$ (следовательно, и $k)$ — единственно.

Доказательство. Пусть $N = 28 +30m +31k,$ но $m ≥ 31.$ Тогда

N = 28 +30⋅(m− 31)+31⋅(k+ 30)

При этом

k+ 30> k≥ m-+1-> m-− 31+-1 2 2

Следовательно, пара $m1 = m − 31,$ $k1 = k+ 30$ тоже подходит для представления $N.$ Осуществляя данную операцию несколько раз, найдём требуемое представление. Чтобы показать его единственность, предположим противное, то есть, что для некоторых различных $m1$ и $m , 2$ не превосходящих 30

N = 28 +30m1+ 31k1 =28+ 30m2+ 31k2

Тогда

30(m1 − m2)= 31(k2− k1)

Заметим, что левая часть не может быть кратна 31 — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче. Все числа вида $31a+ 28$ приемлемы $(m = 0,$ $k= a).$ Число вида $31a+ 27= 28 +30+ 31(a− 1)$ приемлемо, только если

m + 1 k =a− 1≥ --2--= 1

Другими словами, $a≥ 2.$ Наибольшее неприемлемое число такого вида — $31⋅1+ 27= 58.$ Аналогично, $N = 31a +26= 28+ 30⋅2+ 31(a − 2)$ (здесь $m = a,$ $k= 0)$ приемлемо, если

k= a− 2≥ m-+1-= 3 2 2

a ≥ 7 2

Наибольшее неприемлемое число такого вида — $31⋅3+ 26= 119.$ В остальных случаях имеем $N =28+ 31a − t,$ где $0≤ t≤30.$ Тогда $N = 28+30t+ 31(a− t)$ приемлемо тогда и только тогда, когда

a− t≥ t+1- 2

3 1 a ≥ 2t+2

Поскольку $a$ — целое, получаем, что наибольшее неприемлемое число указанного вида достигается при $3 a= 2t$ в случае нечетного $t$ и при $3 1 a = 2t−2$ в случае нечетного $t.$ Значения $N$ будут соответственно равны

( 91 ) (25 91 ) 28+ -2 t ,-2 +-2 t

Теперь ясно, что наибольшее неприемлемое число возникает при наибольшем значении $t,$ то есть при $t=30.$ В этом случае

N =28+ 91⋅30= 1393 2

Ответ:

1393

Курсы

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

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

Задача 7#78886

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

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

Известно, что $2020 =22⋅5⋅101.$ Теперь понятно, что наименьшее число в принципе четырёхзначное, так как трёхзначное число с произведением $2020$ составить невозможно(как минимум из-за $101$ ). Первая наименьшая цифра, которая может идти в разряде тысячных это $4.$ Она может получиться из первой $4$ или $404.$ В первом случае число $4505,$ во втором $4045$ Итого наименьшее число $4045.$

Ответ:

$4045$

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

Задача 8#79598

На доске написаны числа $1,2,3,...,36$ . За одну операцию Саша может выбрать два числа на доске, стереть их и записать на доску сумму стёртых чисел. Такими операциями он хочет добиться, чтобы на доске не нашлись одно или несколько чисел, сумма которых равна 37 (сумма одного числа — это само это число). Какое наименьшее количество операций придётся сделать Саше?

Источники: ОММО - 2024, задача 2 (см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Хочется разбить числа на пары так, чтобы в каждой паре сумма числа равнялась 37. Это сделать несложно: первое объединяем в пару с последним, второе с предпоследним и так далее. Остаётся придумать, как мы будем портить числа, то есть стирать два числа с доски и оставлять их сумму

Подсказка 3

Да, будем стирать те числа, которые дают в сумме 19, ведь тогда минимальная сумма будет ровно 38, что нас устраивает! То есть можно стирать пары чисел: 1 и 18, 2 и 17 и так далее. В таком случае сколько операций нам понадобится?

Подсказка 4

Ровно 9 операций потребуется!

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

Разобьем числа на пары с суммой $37:{1,36}, {2,35},...,{18,19}$

В каждой такой паре нужно “испортить” хотя бы одно число. За каждую операцию мы “портим” $2$ числа, то есть можем “испортить” максимум две пары. Нужно “испортить” $18$ пар, поэтому нужно минимум $9$ операций. Приведем пример на $9$ действий:

Сложим сначала $1$ с $18$ , затем $2$ с $17$ и так далее до $9+ 10$ . После проделанных действий получаем

19, 19, ..., 20, 21, ..., 36

Ряд не содержит числа $37$ , а также никакие несколько чисел не дают в сумме $37$ , так как их сумма как минимум $19+ 19= 38.$

Ответ: 9

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

Задача 9#80744

Какое максимальное количество простых чисел можно записать, использовав каждую из десяти цифр от 0 до 9 ровно по одному разу?

Источники: Всесиб-2024, 11.1 (см. sesc.nsu.ru)

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

Подсказка 1

Если мы понимаем, что простые числа наши составляют все цифры от 0 до

Подсказка 2

Последней цифрой может быть только 1,2,3,5,7,9. Значит, чисел не больше 6. Попробуйте построить пример на 6, и тогда задача будет решена.

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

Последними цифрами простых чисел могут быть только $1,2,3,5,7,9$ . Значит, использовав каждую из десяти цифр от $0$ до $9$ по одному разу, больше шести простых чисел мы получить не сможем.

6 простых чисел уже может быть:

2,3,5,67,89,401

Ответ: 6

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

Задача 10#82288

Натуральные делители натурального числа $n$ занумеровали по возрастанию: $d = 1, d ,...,d = n 1 2 k$ . Оказалось, что $d =120 18$ . Какое наименьшее значение может принимать число $n$ ?

Источники: ИТМО-2024, 11.3 (см. olymp.itmo.ru)

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

Подсказка 1

Первое, что хочется сделать, это разложить 120 на множители. Получается, что все его 16 делителей будут и делителями исходного числа. А что будет, если наше исходное число будет делится, например, на большую степень двойки?

Подсказка 2

Давайте посмотрим. Если n делится на 2^4, то к делителям n прибавится ещё 3 делителя, меньшие 120. Получается, что 120 не будет восемнадцатым делителем. Противоречие. Аналогично рассматривая 3 и 5, может ли n делится на их большие степени? Какой вывод из этого можно сделать?

Подсказка 3

Да, получаем и там аналогичное противоречие. Значит, у n есть простой делитель p, кроме 2, 3 и 5. Если мы сможем оценить его, то задача решена. Нельзя ли почти с помощью почти аналогичного противоречия получить оценку на p?

Подсказка 4

Верно, если у числа будут делители p, 2p и 3p, меньшие 120, то получается снова, что 120 минимум девятнадцатый делитель. Осталось только найти наименьший простой делитель, больший 40, посчитать ответ, и победа!

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

У числа $120 =23⋅5⋅3$ шестнадцать делителей и все они являются делителями числа $n$ . Если $n$ делится на $24$ , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если $n$ делится на $2 3$ , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если $n$ делится на $2 5$ , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, $n$ делится на какое-то простое число $p$ , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа $p,2p$ и $3p$ являются делителями $n$ , меньшими 120 , и мы опять получаем слишком много делителей. Значит, $p$ хотя бы 41 , то есть $n≥ 120⋅41$ . Заметим, что это число нас как раз устраивает.

Ответ: 4920

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

Задача 11#87405

Кузнечик прыгает по числовой прямой. Каждый свой прыжок он может совершить в любом направлении. Он начинает в точке 0 прыжком единичной длины. Каждый следующий прыжок должен быть на три больше предыдущего (т.е. первый прыжок длины 1, второй длины 4, третий длины 7 и т.д.). За какое наименьшее число прыжков кузнечик сможет оказаться в точке 2024?

Источники: СПБГУ - 2024, 11.1 (см. olympiada.spbu.ru)

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

Подсказка 1

Попробуем как-то оценить n…а как вообще посчитать, насколько далеко мы ушли от начала координат?

Подсказка 2

Заметим, что наши прыжки - это члены арифметической прогрессии a ₙ = 3n-2. Тогда на какое наибольшее расстояние мы можем уйти от нуля? Каким тогда должно быть n?

Подсказка 3

Максимальное расстояние, на которое мы можем уйти - это (3n-1)n/2. И мы знаем, что это число должно быть не менее 2024. Теперь у нас есть какая-то оценка на n. А как (в зависимости от прыжков влево) посчитать местоположение кузнечика?

Подсказка 4

Обозначим общую длину прыжков влево как х. На какой клетке тогда находится кузнечик? Каким тогда должно быть n?

Подсказка 5

Кузнечик будет стоять на точке (3n-1)n/2 - 2х. Осталось лишь понять, каким должен быть n ;)

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

Процесс прыжков можно описать следующим образом: $n$ прыжков кузнечика — это сумма $n$ первых членов арифметической прогрессии $an =3n− 2$ , в которой перед каждым членом стоит $+$ или $−$ . Ясно, что за $n$ прыжков кузнечик сможет оказаться не более, чем в $(3n−1)n 2$ — сумма $n$ первых членов, в которой все члены взяты с $+$ . Значит, необходимо, чтобы $(3n−1)n- 2$ было не меньше $2024$ . То есть $n ≥37$ .

Пусть кузнечик прыгал влево некоторое количество прыжков, и суммарно он прыгнул влево на $x$ единиц, тогда после $n$ прыжков он окажется в точке $(3n−1)n 2 − 2x$ . Значит, чтобы попасть в $2024$ , необходимо, чтобы $(3n−1)n- 2$ было чётным. Значит, $37$ и $38$ прыжков не хватит. В качестве примера на $39$ можно прыгнуть влево на $2$ и на $39$ прыжках, а на остальных — вправо.

Ответ: 39

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#87857

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

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

Сумма любых четырех соседних чисел положительна, поэтому среди них должно быть хотя бы одно положительное число.

Возьмем какое-то положительное число из $13$ чисел (такое найдется, потому что в кругу чисел $≥4$ ). Оставшиеся числа разобьем на группы по $4$ последовательных числа.

$PIC$

Получаем, что положительных чисел должно быть как минимум $4$ (одно отдельное и по $1$ положительному в каждой группе из $4$ подряд идущих чисел). Тогда отрицательных чисел не более $13− 4= 9.$

Приведем пример на $9$ отрицательных чисел:

$PIC$

Ответ: 9

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

Задача 13#88062

На какое самое большое натуральное число будет гарантированно делиться произведение любых шести подряд идущих натуральных чисел?

Ответ обоснуйте.

Источники: Межвед - 2024, 11.1 (см. v-olymp.ru)

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

Подсказка 1

Давайте сначала попробуем найти верхнюю границу (число больше которого искомое точно быть не может)

Подсказка 2

Теперь осталось доказать что (n + 1)(n + 2)...(n + 6) делится на 720 для любого натурального n. Давайте вспомним сочетания из комбинаторики

Подсказка 3

Действительно,

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

Поскольку произведение первых 6 натуральных чисел равно $6!= 720,$ то искомое число не больше $720.$

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел $n+ 1,n +2,...,n+ 6$ делится на $720$ . Поделим:

(n +1)(n +2)...(n+ 6) (n +6)! 6 --------6!--------= -6!n!--= Cn+6

и получим натуральное число способов выбрать шестёрку из $n+ 6$ элементов. Действительно, делится.

Ответ: 720

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

Задача 14#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

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

Задача 15#97674

Женя дала Оле карточки с числами $13,5,64,52$ и попросила ее составить из них всех самое близкое к миллиону число. Как Оле выполнить Женину просьбу?

В ответ введите число, составленное Олей.

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

Давайте попробуем составить какое-нибудь число. Например, $5|13|64|52= 5136452.$ Получается 7-значное число, которое значительно больше одного миллиона. Попробуем составить минимально возможное 7-значное число. Для этого нужно выбирать на каждом шаге карточку с минимальной первой цифрой, но у нас две карточки с первой цифрой 5, рассмотрим два случая. Первый вариант — $13|5|52|64 =1355264,$ второй — $13|52|5|64= 1352564.$ Второе число ближе к 1 000 000. Но можно брать не все карточки и получить 6-значное число. 6-значное число получается из 7-значного убиранием одной цифры. Так как у нас только одна карточка с одной цифрой, то нужно не использовать именно её. Любое 6-значное число меньше одного миллиона, поэтому нужно составить максимально возможное число. Тогда искомое 6-значное число — $64|52|13= 645213.$

Рассматривать 5-значные и меньшие числа нет смысла, так как они будут находиться точно дальше от одного миллиона, чем 6-значные. Тогда нужно только сравнить, какое из чисел $1352564$ и $645213$ ближе к 1 000 000.

1352564 − 1000000 ? 1000000− 645213

352564< 354787

Значит, искомое число — это $1352564.$

Ответ: 1352564

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

Задача 16#97677

У Вари есть стопка карточек с цифрами $1,2$ и $3.$ Она выкладывает карточки в ряд и хочет, чтобы в ряду нашлись все двузначные числа, в записи которых есть эти цифры. Какое наименьшее количество карточек может быть в таком ряду? (Двузначное число можно найти, если карточки с его цифрами лежат рядом в правильном порядке.)

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

Всего двузначных чисел из цифр $1,2,3$ ровно $9.$ Тогда должно получиться $9$ пар соседних карточек, следовательно, карточек должно быть не менее $10.$ Например, карточки можно расположить так:

1133223121

Ответ: 10

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

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

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

Задача 17#120166

На доске написаны числа $1,2,3,...,27.$ За одну операцию Саша может выбрать два числа на доске, стереть их и записать на доску сумму стёртых чисел. Такими операциями он хочет добиться, чтобы на доске не нашлись одно или несколько чисел, сумма которых равна $27$ (сумма одного числа — это само это число). Какое наименьшее количество операций придётся сделать Саше?

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

Разобьем числа на пары с суммой $27:{1,26}, {2,25},...,{13,14}$ и ещё просто само число $27$ (будем считать, что оно в паре с $0).$

В каждой такой паре нужно “испортить” хотя бы одно число. За каждую операцию мы “портим” $2$ числа, то есть можем “испортить” максимум две пары. Нужно “испортить” $14$ пар, поэтому нужно минимум $7$ операций. Приведем пример на $7$ действий:

Сложим сначала $1$ с $13,$ затем $2$ с $12$ и так далее до $6+ 8.$ И ещё $7$ с $27.$ После проделанных действий получаем

14, 14, ...,14, 34, 14, 15, ..., 26

Ряд не содержит числа $27,$ а также никакие несколько чисел не дают в сумме $27,$ так как их сумма как минимум $14+ 14= 28.$

Ответ:

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

Задача 18#63738

При каком наименьшем $n$ можно покрасить каждое натуральное число в один из $n$ цветов так, чтобы любые два числа, отличающиеся на 5 , на 8 , на 10 , на 13 и на 18, были покрашены в разные цвета?

Источники: ОММО-2023, номер 2 (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте попробуем как-то снизу оценить кол-во цветов. Вот что можно заметить в этих разностях: 18-13 = 5, 18-10 = 8, 13-5 = 8, 13-5 = 8....может быть можно найти какую-то группу чисел, в которой все числа должны быть разного цвета?

Подсказка 2

Например, подойдет четверка чисел вида n, n+5, n+10, n+18! А еще подойдет четверка n, n+5, n+13, n+18...теперь проверьте, может ли быть ровно 4 цвета?

Подсказка 3

Для четырех не вышло, давайте попробуем для 5! Может попробовать разбить все числа на какие-то группы, что внутри одной группы разность между числами либо очень маленькая, либо очень большая...тогда, скорее всего, условие выполнится)

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

Докажем для начала, что четырьмя и меньше цветами обойтись не удастся. Посмотрим на числа $n,n +5,n+ 10,n+ 18$ . Разности между ними равны

(n+ 5)− n =5, (n+ 10)− n =10, (n+ 18)− n =18 (n +10)− (n+ 5)= 5, (n +18)− (n +5)= 13, (n +18)− (n +10)= 8

т.е. любые два из этих чисел покрашены в различные цвета. Значит, цветов хотя бы четыре. Предположим, что цветов ровно четыре. Тогда числа $n,n+ 5,n+ 10,n +18$ покрашены во все возможные цвета. Аналогично можно получить, что во все возможные цвета покрашены числа $n,n+ 5,n+ 13$ , $n+ 18$ . Значит, для каждого натурального $n$ числа $n +10$ и $n+ 13$ должны быть покрашены в один и тот же цвет.

Применим полученное утверждение для $n= 1,4,7,...,16$ . Тогда числа $11,14,17,...,29$ покрашены в один и тот же цвет. Противоречие, ведь $29− 11 =18$ и числа 11 и 29 должны быть покрашены в разные цвета.

Докажем теперь, что пять цветов достаточно. Для этого разобьём все натуральные числа на группы по 5 подряд идущих чисел, а группы покрасим так: первую - в первый, вторую - во второй, ..., пятую - в пятый, шестую - в первый, седьмую - во второй, .... При такой раскраске числа одного цвета будут или отличаться не более чем на 4, если лежат в одной пятёрке, или хотя бы на 21 - если в разных. Значит, числа, отличающиеся на $5,8,10,13$ и 18, будут покрашены в разные цвета.

Ответ: 5

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

Задача 19#67585

Натуральные числа $a,b,c$ таковы, что $ab$ делится на $29310510,bc$ делится на $214313513,$ $ac$ делится на $219318530.$ Найдите наименьшее возможное значение произведения $abc.$

Источники: Физтех-2023, 11.1 (olymp-online.mipt.ru)

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

Подсказка 1

Чтобы произведение abc было минимальным, какие простые в своем разложении они могут иметь?

Подсказка 2

Да, каждое из чисел не должно иметь других простых, кроме 2, 3 и 5(но не обязательно, что каждое из них есть). Тогда давайте разложим каждое из чисел a, b, c на простые множители! Какие неравенства можно написать, если внимательно посмотреть на условие задачи?

Подсказка 3

Да, пусть x₁, x₂, x₃ – степени вхождения двойки в a, b, c соответственно, тогда будет верным: x₁ + x₂ ≥ 9; x₂ + x₃ ≥ 14; x₁ + x₃ ≥ 19. Что нужно сделать, чтобы понять в какой степени двойка входит в произведение abc?

Подсказка 4

Верно, нужно сложить эти степени и поделить на 2! Таким образом abc кратно 2²¹(поскольку если мы просто сложим степени двойки, то получим (abc) ²). Так, а дальше осталось сделать то же самое с 3 и 5 и привести пример, что каждая оценка достигается! Но какой случай может вызвать трудности?

Подсказка 5

Ну, если получается нецелое число, то мы его просто округляем до ближайшего целого, это не сложно. А вот, если пример не получается подобрать? Например, в случае с пятеркой: Если сделать также как и с двойками, то получится, что y₁+y₂+y₃ ≥ 27, но при этом y₁+y₃ ≥ 30 и y₂ ≥ 0. Тогда, нужно строить пример для y₁+y₂+y₃ ≥ 30. (y₁, y₂, y₃ – степени вхождения пятёрки в числа a, b, c соответственно)

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

Чтобы произведение $abc$ было минимальным, числа $a,b,c$ не должны иметь простых делителей, отличных от $2,3$ и $5.$

Пусть $α1 β1 γ1 a= 2 ⋅3 ⋅5 ,$ $α2 β2 γ2 b =2 ⋅3 ⋅5 ,$ $α3 β3 γ3 c= 2 ⋅3 ⋅5$ (показатели всех степеней — целые неотрицательные числа). Тогда

α+α +α β+ β+β γ+γ +γ abc= 2 1 2 3 ⋅3 1 2 3 ⋅5 1 2 3

Рассмотрим отдельно делимость на $2,3$ и $5:$

$1)$ Из того, что $ab$ делится на $29,$ $bc$ делится на $214,$ $ac$ делится на $219,$ следует, что

(| α1 +α2 ≥9 { α2 +α3 ≥14 |( α1 +α3 ≥19

Складываем полученные неравенства и получаем:

α +α +α ≥ 9-+14+-19= 21 1 2 3 2

Покажем, что значение $α + α + α = 21 1 2 3$ достигается. Для этого возьмём $α =7,α = 2,α =12. 1 2 3$

$2)$ Из того, что $ab$ делится на $10 3 ,$ $bc$ делится на $13 3 ,$ $ac$ делится на $18 3 ,$ следует, что

( |{ β1 +β2 ≥ 10 |( β2 +β3 ≥ 13 β1 +β3 ≥ 18

Складываем полученные неравенства и получаем:

β1+β2+ β3 ≥ 10+-123+18 =20,5

Покажем, что значение $β1+ β2+ β3 =21$ достигается. Для этого возьмём $β1 = 7,β2 = 3,β3 = 11.$

$3)$ Из того, что $ac$ делится на $530,$ следует, что $γ1+ γ3 ≥30.$ Заметим, что

γ1+ γ2+ γ3 ≥γ1+ γ3 ≥ 30.

$γ1 +γ2+ γ3$ может равнятся $30,$ если, например, $γ1 =15,γ2 =0,γ3 = 15.$

Так как минимум каждой из трёх сумм $α1+ α2+α3,β1+ β2+β3,γ1+γ2+ γ3$ не зависит от оставшихся, то и минимальное значение $abc$ равно

abc= 2min(α1+α2+α3)⋅3min(β1+β2+β3)⋅5min(γ1+γ2+γ3) = 221⋅321⋅530

Ответ:

$221⋅321⋅530$

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

Задача 20#73690

Дано натуральное число $n.$ Рассмотрим множество всех целых чисел, по модулю не превосходящих $n.$ Какое наибольшее число элементов можно выбрать из этого множества так, чтобы не нашлось трех различных выбранных чисел $a,b$ и $c,$ для которых $a+ b= c?$

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

Подсказка 1

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

Подсказка 2

Верно! Для четного n можно взять числа n, n - 1, ... n/2 и те же с минусом до -n/2 - 1 (-n/2 не берём!). Для нечетного n возьмем n, n - 1, ... (n+1)/2 и те же с минусом. Пример на n + 1 есть. Осталась оценка. Попробуйте доказать ее по индукции.

Подсказка 3

База очевидна. Поэтому знаем для n = k, что больше, чем k + 1 чисел, выбрать нельзя. Хотим доказать, что для k + 1 нельзя выбрать k + 3 числа. Пусть можно. Какие числа мы тогда должны точно взять?

Подсказка 4

Правильно! По предположению мы должны взять числа k + 1 и - k - 1. Теперь попробуйте разбить числа на пары так, чтобы из каждой пары можно было взять только одно число. Как это сделать для четного k?

Подсказка 5

Верно! Надо взять в пару все числа, которые в сумме дают k + 1 и -(k + 1). Таких пар k, а, значит, взять k + 3 числа не получится. А какие пары для нечетного?

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

Пример для $n+ 1:$

Если $n$ чётное, то возьмём числа $n n,n − 1,n− 2,..., 2$ и $n − n,− n+ 1,...,−2 − 1.$ Суммы, где оба слагаемых отрицательны или положительны, по модулю больше $n.$ Cуммы, в которых слагаемые разных знаков, принимают значения из отрезка $n n [−2;2 − 1].$

Если $n$ — нечётное, то возьмём числа $n+1 n,n− 1,..., 2$ и $n+1 − n,−n+ 1,...− 2 .$ Суммы, где оба слагаемых одного знака, по модулю больше $n.$ Суммы, в которых слагаемые разных знаков, принимают значения из отрезка $n−1 n−1 [− 2 , 2 ].$

Теперь докажем оценку на $n +1$ по индукции:

База при $n= 1.$ Есть числа $± 1,0.$ Если выбрать все, то $1− 1= 0.$ Выбрать $2$ числа можно.

Переход. Пусть для $n= k$ можно выбрать не более $k+ 1$ чисел. Следовательно, если мы хотим для $n =k +1$ взять хотя бы $k+3$ числа, мы обязаны взять числа $k+ 1$ и $− k− 1,$ потому что среди оставшихся чисел по предположению можно взять не более $k+ 1$ число.

Ясно, что в этом случае $0$ брать нельзя. Рассмотрим случаи.

Если $k$ чётно, то разобьём оставшиеся числа на пары: $(1,k),(2,k− 1),...,(k2,k2 + 1)$ и $(−1,−k),...,(− k2,− k2 − 1)$ — $k$ штук.

Если из какой-то пары взять оба числа, то их сумма будет $± (k +1),$ то есть мы так сделать не сможем. Значит, из каждой пары взято не более $1$ числа, то есть суммарно из этих пар взято не более $k$ чисел. Таким образом, мы выбрали не более $k+ 2$ чисел, противоречие.

Если $k$ нечётно, то разобьём так: $(1,k),(2,k− 1),...,(k−21,k+23)$ и $(− 1,−k),(−2,−k+ 1),...,(− k−21,− k+23).$ Числа $± k+21$ оставим без пары. Получили $k− 1$ пару, из каждой можно взять не более $1$ числа. Также среди чисел $± k+12-$ можно взять не более одного, потому что $k+ 1− k+21= k+21.$ Таким образом, мы взяли не более $k+ 2$ чисел. Оценка доказана.

Ответ:

$n +1$