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

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

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

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

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

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

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

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

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

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

На числовой оси отмечено 2 000 000 точек с целыми координатами. Рассматриваются отрезки длин 97, 100 и 103 с концами в этих точках. Какое наибольшее количество таких отрезков может быть?

Источники: СПбОШ - 2024, 10.5 (см. pdmi.ras.ru)

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

Подсказка 1

Возьмем, например, отрезки длины 97. Рассмотрите цепочки из них и ответьте на следующий вопрос: чему будет равно количество отрезков в такой цепочке?

Подсказка 2

Да, отрезков в цепочке будет на 1 меньше, чем точек в цепочке. Тогда суммарное количество отрезков длины 97 будет (N - a), где a — количество цепочек.

Подсказка 3

Проделайте аналогичные рассуждения для отрезков длины 100 и 103. Предъявите в виде равенства общее число отрезков и критерий состоятельности оценки.

Подсказка 4

Критерий: a + b + c ≥ 97 + 100 + 103, где b и c — количества цепочек для чисел 100 и 103 соответственно.

Подсказка 5

Для проверки критерия предположите, что по какому-то из модулей присутствуют не все остатки.

Подсказка 6

Дело за малым: вычислите точное количество отрезков и предъявите ответ.

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

Пример: Указанное количество отрезков получается, если отметить на числовой оси $2000000$ последовательных целых чисел.

Оценка: Покрасим отрезки длины $97,100$ и $103$ в красный, синий и зелёный цвета соответственно. Все $N = 2000000$ точек разобьются на $a$ красных цепочек. В каждой такой цепочке остатки всех чисел по модулю $97$ одинаковы, а количество отрезков ровно на $1$ меньше, чем точек. Поэтому суммарное количество красных отрезков равно $N − a.$

Аналогично, пусть имеется $b$ синих и $c$ зелёных цепочек. Тогда общее количество отрезков равно:

(N − a)+ (N − b)+(N − c)= 3N − (a+ b+c)

Оценка будет доказана, если мы проверим, что

a+ b+ c≥97+ 100+103

Если у исходных $N$ чисел присутствуют все возможные остатки по каждому из модулей $97,100$ и $103,$ то $a≥ 97,b≥ 100,c≥ 103,$ и нужное неравенство очевидно.

Предположим теперь, что по одному из трёх модулей (например, по модулю $97$ ) присутствуют не все остатки. Тогда в каждой синей цепочке (которая соответствует отрезкам длины $100$ ) содержится не более чем $96$ точек. Действительно, переход от числа $k$ к числу $k+ 100$ по синему отрезку соответствует прибавлению $3$ по модулю $97.$ Если бы присутствовали все $97$ остатков, то в цепочках было бы не менее $97$ точек. Следовательно,

N- b≥ 96

Аналогично, для зелёных цепочек (длина $103,$ модуль $102$ ):

N-- c≥ 102

Таким образом,

N N a+ b+c ≥96 +102

что при $N =2 000000$ уже гораздо больше, чем $97+ 100+ 103.$

Ответ:

$3⋅2000000− (97+ 100+ 103) =5999700$

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

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

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

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

При каком наименьшем $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

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

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

Натуральные числа $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$

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

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

Дано натуральное число $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$

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

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

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

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

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

Разобьём числа от $1$ до $2022= 6⋅337$ на шестёрки подряд идущих. По доказанному, в каждой шестёрке может быть выбрано не больше двух чисел. Остаются числа 2023 и 2024, из которых может быть выбрано не больше одного, поскольку они отличаются на 1.

Теперь мы доказали, что больше $2⋅337 +1= 675$ чисел выбрано точно быть не может.

Выберем числа $1,3+ 1,3⋅2+ 1,3 ⋅3 +1,...,3⋅674+ 1= 2023.$ Их попарные разности кратны трём, поэтому, очевидно, не равняются 1, 4 или 5. При этом выбранных чисел ровно 675, то есть максимально возможное количество.

Ответ: 675

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

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

Дано натуральное число $a.$ Какое наибольшее количество точных квадратов может быть среди чисел $a,a2+ 1,$ $a3+2,...,a16 +15?$

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

Подсказка 1

При a = 1 легко вычислить все числа и посмотреть, сколько квадратов получится. При a ≥ 2 могут ли получится квадраты при четных степенях?

Подсказка 2

Верно, не могут, ведь если при степени 2k получилось число b², то с помощью оценок степеней получим, что сумма b и k-ой степени a слишком велика. А когда еще квадратов наверняка быть не может?

Подсказка 3

Верно! Если a = t², то квадратов тоже не будет (из предыдущих рассуждений). Вычислением для a = 1 получаем, что точных квадратов в этом случае всего 4. При этом, убрав четные степени, мы отсеяли достаточно большую часть чисел. Могло ли получиться хотя бы 5 квадратов?

Подсказка 4

Из принципа Дирихле следует, что найдутся две последовательные нечётные степени a, для которых оба соответствующих числа являются точными квадратами. Могло ли так получиться?

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

При $a= 1$ получаем $4$ точных квадрата: $1,4,9$ и $16.$ Теперь рассмотрим $a ≥2.$ Покажем, что при чётных степенях $a$ точно не будет точных квадратов. Пусть $2k 2 a +2k− 1= b.$ Получаем, что $k k b+ a >2a > 2k− 1,$ поскольку $k b> a$ и $a> 1.$ Но тогда $k k (b− a)(b+a )> 2k− 1.$ Противоречие.

Значит, квадраты надо искать только среди нечётных степеней. Предположим, что $2 a =t .$ Тогда все выражения содержат $t$ в чётной степени и аналогичными рассуждениями приходим к противоречию. Значит, $a$ не является точным квадратом.

Тогда предположим, что при каком-то $a$ точных квадратов хотя бы $5.$ Тогда найдутся две степени $a,$ отличающиеся на $2$ такие, что оба числа, им соответствующие, — это точные квадраты, причём $k≥ 3$ (по принципу Дирихле). Пусть $2k−1 a + 2k− 2$ и $2k+1 2 a +2k =x$ точные квадраты. Тогда умножим первое число на $2 a ,$ тоже получим точный квадрат $2k+1 2 2 a + (2k− 2)a =y .$ То есть мы получили два достаточно “близких” точных квадрата. Покажем, что так не бывает. Снова $2 2 y − x > 2x(y > x).$ Значит,

(∘ -------) (2k− 2)a2− 2k> 2 a2k+1+ 2k

Сделаем огрубление: $2ka2 > 2ak, k> ak− 2.$ При $k≥ 3$ и $a≥ 3$ так быть не может. Осталось разобраться с $a= 2.$ Тогда $22k+1+ 2k$ при нечётных $k$ делится на $2,$ но не делится на $4,$ а значит, не является точным квадратом и всего их не более четырёх. Пример на $4$ при $a = 1.$

Ответ:

$4$

Курсы

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

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

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

Найдите наибольшее натуральное число $n,$ для которого произведение чисел $n,n +1,$ $n +2,$ …, $n+ 20$ делится на квадрат какого-то одного из них.

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

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

Подсказка 1:

Попробуйте придумать какой-нибудь пример. Чтобы легче придумывалось, попробуйте подобрать n так, чтобы произведение чисел от n до n + 20, делённое на n², равнялось некоторой цешке. Она целая.

Подсказка 2:

Попробуйте n = 20!. Чтобы показать, что при больших n это невозможно, предположите обратное. Пусть существует такое n и произведение делится на некоторое k². Рассмотрите частное произведения и k. Оно должно делиться на k. А с чем оно сравнимо по этому модулю?

Подсказка 3:

Пусть P = n(n + 1)...(n + 20), k = n + i, где i от 0 до 20. Тогда P / k = (k – i)(k – i + 1)...(k – 1)(k + 1)(k + 2)...(k + j), где j = 20 – i. Нетрудно видеть, что P / k сравнимо с (–1)ⁱi!j! по модулю k. Может ли (–1)ⁱi!j! делиться на k?

Подсказка 4:

Покажите, что число i!j! больше 0 и меньше 20!. Используйте для этого равенство j = 20 – i.

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

При $n= 20!$ имеем

n(n+-1)(n+-2)...(n+20) (n+-1)(n+-2)...(n-+20) 20 n2 = 20! = Cn+20— целое число.

Пусть теперь $n> 20!$ и пусть

P = (n+ 1)(n+ 2)...(n+ 20)

делится на $2 k ,$ где $k= n+ i,$ $i= 0,1,2,$ …, $20.$ Имеем

P ∕k =(k− i)(k− i+1)...(k− 1)(k+1)(k +2)...(k+ j),

где $j =20− i.$ Заметим, что число

i P∕k ≡(−1)i!j! (mod k)

должно делиться на $k.$ Но

0 <i!j!≤ i!⋅(i+ 1)(i+2)...(i+j)= 20!<n ≤k,

значит, $i!j!$ не делится на $k.$ Противоречие.

Ответ:

$20!$

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

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

Какой ближайший к текущему год имеет в своей записи два нуля подряд?

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

Подсказка 1

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

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

Текущий год — это год 21 века, поэтому номер года точно четырёхзначный, поэтому нулями являются разряд десятков и либо разряд единиц, либо разряд сотен. В первом случае ближайшим годом может быть 2000 или 2100, а во втором — 2009. В текущий год ближайшим является 2009. Ответ поменяется в 2055 году, когда до 2100 будет 45 лет, а до 2009 — 46 лет.

Ответ:

$2009$

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

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

У Кати, Лизы, Маши и Насти вместе $100$ леденцов. У любых двух девочек в сумме хотя бы $41$ леденец. Какое наименьшее количество леденцов может быть у Лизы?

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

Обозначим количество леденцов у Кати, Лизы, Маши и Насти соответственно за $k,l,m,n$ . Тогда $k+ l≥ 41,$ $l+ m ≥41,$ $l+n ≥ 41.$ Складывая эти неравенства, получаем

2l+(k+ l+ m + n)≥123.

Причем

k+ l+m + n= 100,

откуда $2l≥ 23,$ или же в целых числах $l≥ 12.$ Пример на $12$ существует: $l= 12,$ $m =n = 29,$ $k =30.$

Ответ:

$12$

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

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

Найдите ближайший в будущем год, в записи которого не встречается цифра $0$ .

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

Докажем, что год должен быть $≥2111$ . В каждом разряде искомого года должна стоять $≥ 1$ , и год должен быть $> 2000$ => искомый год $≥2111$ .

Заметим, что 2111 год подходит.

Ответ: 2111

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

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

Даны $20$ различных натуральных чисел. Известно, что сумма любых двух из них делится на $10$ . Какое наименьшее количество чисел, делящихся на $10$ , может быть среди них?

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

Заметим, что меньше 0 быть не может.

Приведем пример, когда среди чисел ровно 0, делящихся на 10: 15, 25, 35, ..., 205. Легко видеть, что сумма любых двух чисел заканчивается на 0, то есть кратна 10.

Ответ: 0

Интенсивы

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

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

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

Какое наибольшее количество натуральных чисел можно написать на доске так, чтобы сумма любых двух чисел была нечетной?

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

Подсказка 1

Чтобы сделать оценку, давайте подумаем, какой четности будет сумма двух чисел в зависимости от четности самих этих чисел, и выпишем все возможные варианты

Подсказка 2

Сумма двух чисел четная, если они одинаковой четности, и нечетная иначе. Что это значит для нашей задачи?

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

Докажем, что нельзя написать больше 2 чисел. Предположим, написано хотя бы 3 числа. Тогда среди этих чисел есть хотя бы 2 нечетных или хотя бы 2 четных числа (так как иначе всего чисел не более 2), которые в сумме дают четное число. Получили противоречие с условием. Значит, наше предположение неверно.

Теперь покажем, что можно написать 2 числа, чтобы их сумма была нечетной. Напишем числа 1 и 2, которые удовлетворяют условию.

Ответ: 2

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

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

На картинке нарисовано несколько кружочков, соединённых отрезками.

$PIC$

Саша выбирает натуральное число $n$ и расставляет в кружочках различные натуральные числа так, чтобы для всех этих чисел выполнялось свойство: если числа $a$ и $b$ не соединены отрезком, то сумма $a+b$ должна быть взаимно проста с $n,$ a если соединены, то числа $a+ b$ и $n$ должны иметь общий натуральный делитель, больший 1.

При каком наименьшем $n$ существует такая расстановка?

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

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

Подсказка 1

Чтобы как-то снизить количество вариантов для n, давайте подумаем: а может ли n быть чётным?

Подсказка 2

Нет, поскольку если n чётно, то по принципу Дирихле найдутся два числа одинаковой чётности, которые не будет соединены! А значит их сумма кратна 2, поэтому НОД не будет равен 1. А теперь, зададимся вопросом: а могут ли три суммы четырех последовательно соединенных чисел быть кратны одному и тому же делителю числа n?

Подсказка 3

Нет, ведь в таком случае сумма крайних чисел(которые не соединены ребром) - тоже будет кратна этому делителю! То есть, число n не может равняться степени нечётного простого, поэтому оно кратно хотя бы двум различным нечётным простым! Теперь мы хотим взять минимальные простые(дли минимальности n), то есть, надо узнать, а может ли n быть кратно 3?

Подсказка 4

И опять-таки нет, n не может быть кратно 3. Поскольку, в таком случае найдётся пара чисел, соединенных ребром, сумма которых не будет кратна 3(для этого достаточно рассмотреть остатки при делении 3) То есть тройки не может быть среди простых! Осталось проверить, можно ли составить пример для n=5*7.

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

Сделаем два замечания.

1) $n$ нечетно. Действительно, пусть $n$ четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины 3.

2) Если $q$ — простой делитель $n,$ то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна $q.$ Возьмем цепочку $(a,b,c,d)$ последовательно соединенных чисел. По условию

. a +d= (a+ b)− (b+c)+ (c+ d).. p

Тогда числа $a$ и $d$ тоже соединены, то есть на картинке получился цикл длины 4, которого там нет.

Из 1) и 2) вытекает, что число $n$ имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, $p$ и $q).$ Покажем, что они отличны от 3. Допустим, например, что $p= 3.$ Не более двух чисел делятся на 3 (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на 3 остатки 1 и 2. Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на 3 не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна 3 и, значит, делится на $q.$ Но это противоречит 2).

Таким образом, если $n$ имеет ровно два различных нечетных простых делителя, то $n ≥5 ⋅7 =35.$ Если же таких делителей больше двух, то $n≥ 3⋅5⋅7= 105 >35$ . Расстановка для $n= 35$ приведена на рисунке.

$PIC$

Ответ: 35

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

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

Найдите четырёхзначное число с суммой цифр $8,$ у которого первая слева цифра получается из второй умножением на $3,$ а четвёртая из третьей умножением на $4.$

Источники: Муницип - 2022, Кировская область, 7.1

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

Подсказка 1

Попробуем строить число постепенно. Первая цифра хотя бы 1, значит вторая хотя бы 3. Аналогично продолжим рассуждения...

Подсказка 2

Если третья цифра хотя бы 1, то четвертая - хотя бы 4. Какой тогда будет сумма цифр? Как это предотвратить?

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

Первая цифра не может быть нулём, поэтому вторая цифра не меньше $1,$ а первая — не меньше $3.$ Если третья цифра больше $0,$ то четвёртая не меньше $4,$ и получается, что сумма цифр числа не меньше, чем $3+ 1+ 1+ 4= 9$ — противоречие. Поэтому третья и четвёртая цифры — нули, а первая и вторая должны в сумме давать $8.$ Значит, вторая цифра равна $2,$ а первая равна $6.$

Ответ: 6200

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

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

Можно ли найти четыре различных натуральных числа, каждое из которых не делится ни на $2,$ ни на $3,$ ни на $4,$ но сумма любых двух делится на $2,$ сумма любых трёх делится на $3,$ а сумма всех четырёх делится на $4?$

Источники: Муницип - 2022, Республика Татарстан, 8.1

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

Подсказка 1

Такс, наши числа не делятся на 2, 3 и 4, но при этом в сумме несколько чисел делятся на 2, 3 и 4. Что можно сказать про остатки при делении на 2, 3 и 4?

Подсказка 2

Верно, у всех чисел должны быть одинаковые остатки при делении на 2, 3 и 4! Ведь, в противном случае, найдется такой набор(например по модулю 3), что его сумма не будет делиться на 3. Осталось подобрать пример)

Подсказка 3

Для того, чтобы подобрать пример, давайте решим какие остатки будут давать наши числа при делении на каждое из чисел. Пусть эти остатки будут равны 1. Какие числа дают остаток 1 при делении на 3 и 4?(какой вид они имеют)

Подсказка 4

Верно, числа вида: 12k+1

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

Можно, например,

5,17,29,41

Указанные четыре числа можно записать в виде $12k+ 5$ , где $k$ принимает значения $0,1,2,3,$ поэтому сумма любых трёх чисел

(12k1+ 5)+ (12k2+ 5)+(12k3+ 5)= 12 (k1+ k2+k3)+ 15

делится на $3.$ Все числа в наборе нечётные, значит, сумма любых двух делится на $2.$ Наконец, сумма всех четырёх чисел равна $72$ и делится на $4.$

Варианты правильных ответов:

да
Да
можно
Можно

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

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

Таня последовательно выписывала числа вида $n7− 1$ для натуральных чисел $n= 2,3,...$ и заметила, что полученное при $n= 8$ число делится на $337.$ А при каком наименьшем $n >1$ она получит число, делящееся на $2022?$

Источники: ММО-2022, 11.5, (см. mmo.mccme.ru)

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

Подсказка 1

Никому ещё не вредило разложение чисел на простые множители в задачках на теорию чисел. Давайте разложим 2022 и поймём, какие условия накладывает каждый из множителей.

Подсказка 2

Мы понимаем, что нам достаточно просто перебрать все остатки по каждому из модулю, чтобы найти все условия на n, но как бы ускорить этот перебор?

Подсказка 3

Попробуйте подумать, какое максимальное кол-во решений может иметь сравнение n^7 = 1 (mod 337) на отрезке [0;336], а ещё подумать, что происходит с решением сравнения, если его возвести в произвольную положительную степень?

Подсказка 4

Мы понимаем, что решений не больше 7 и что возведение решения в положительную степень не портит сравнение, остаётся перебрать маленькие n, пока мы не сможем применить эти 2 факта, проверить, что хотя бы одно из них удовлетворяет остальным условиям, полученным из сравнений по mod 2 и mod 3, и выбрать из них наименьшее.

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

Пусть натуральное число $n$ таково, что $n7− 1$ делится на $2022 =2⋅3⋅337.$ Тогда $n7− 1$ делится на $2$ и на $3,$ поэтому $n$ — нечётное число, имеющее остаток $1$ при делении на $3.$ Помимо того, $7 n − 1$ делится на $337.$ Заметим, что если два числа сравнимы по модулю $337$ (т.е. дают одинаковые остатки при делении на $337$ ), то седьмые степени этих чисел также сравнимы по модулю $337.$ Это означает, что для нахождения искомого числа достаточно рассмотреть все целые числа $n$ из промежутка $[0;336],$ удовлетворяющие сравнению $7 n ≡ 1(mod337).$

Мы будем пользоваться следующим утверждением. Пусть $p$ — простое число, $Pk$ — многочлен степени $k$ с целыми коэффициентами, старший коэффициент которого не делится на $p;$ тогда сравнение $Pk(n) ≡0(modp)$ имеет не более $k$ решений среди целых чисел $0 ≤n <p.$

Найдём теперь все решения сравнения $7 n ≡ 1(mod337)$ на отрезке $[0;336].$ Нам известны два решения: $n1 =1$ , $n2 = 8.$ Заметим, что если $n$ — решение сравнения $n7 ≡ 1$ $(mod337),$ то для любого натурального $s$ числа $ns$ также являются решениями. Следовательно, решениями данного сравнения являются числа

82 = 64≡ 64(mod337) 83 = 512 ≡175(mod337) 84 ≡ 8⋅175 ≡52(mod337) 5 8 ≡ 8⋅52≡ 79(mod337) 86 ≡ 8⋅79≡ 295(mod337)

Итак, мы нашли семь решений на отрезке $[0;336]:n1 = 1,n2 =8,n3 = 52,n4 = 64,n5 =79,n6 = 175,n7 = 295.$ Так как число $337$ простое, по сформулированному выше утверждению других решений на этом отрезке нет. Из них нечётными и имеющими остаток $1$ при делении на $3$ являются $n1 =1,n5 = 79,n6 =175$ и $n7 = 295.$ Из них наименьшее, большее $1,$ есть $n5 = 79.$

Ответ:

$79$

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

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

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

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

$427000− 82$ делится на $3n.$ Какое наибольшее натуральное значение может принимать $n?$

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

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

Подсказка 1

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

Подсказка 2

Верно, это значит, что наше число делится на n-ую степень, но не делится на (n+1)-ую. Через сравнения тут решить, наверное, не получится. Но можно же попробовать выразить наше число в явном виде через сумму, где будет видна степень тройки. Какую формулу хорошо бы не побояться применить?

Подсказка 3

Да, конечно, это формула бинома Ньютона. Можно представить 4=3+1 и раскрыть скобки. Достаточно раскрыть первые 5-6 скобок, потому что в дальнейшем степени будут большими, а вот первые члены можно проанализировать, выделив степени тройки. Осталось только найти член в выражении, который не будет делиться на большую степень тройки в отличие от других, и победа!

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

27000 27000 27000⋅26999-⋅32- 27000⋅...⋅26998⋅33- 4 =(1+ 3) = 1+ 27000⋅3+ 2 + 6 +

27000⋅...⋅26997⋅34 27000 ⋅...⋅26996⋅35 + ------24-------+ -------120-------...

Два последних выписанных слагаемых делятся на $36,$ как и все остальные слагаемые, заключённые в многоточие.

2 3 1+ 27000⋅3+ 27000⋅26999-⋅3--+ 27000⋅26999⋅26998⋅3-= 1+ 81000+ 2 6

+27000⋅26999⋅32+27000⋅26999⋅26998⋅32 2

Заметим, что

1+ 81000= 1+ 81(1+ 999)= 1+ 81+ 81 ⋅999= 82+ 81 ⋅999

Это даёт остаток $82$ при делении на $36,$ так как последнее слагаемое делится на $36.$

2 2 2 27000⋅26999-⋅3-+-272000⋅26999-⋅26998⋅3-= 27000⋅26999⋅32-⋅(1+26998)-

А это число, очевидно, делится на $35,$ но не на $36.$ Значит, $427000 − 82$ также делится на $35,$ но не на $36.$

Ответ: 5

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

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

Длины рёбер $a ,a,a 1 2 3$ и $b,b ,b 1 2 3$ прямоугольных параллелепипедов $P A$ и $P B$ — целые числа. Если в параллелепипеде $P A$ увеличить на $1$ длину одного из рёбер $a1,a2$ или $a3,$ то отношение объёмов $VA :VB$ изменится на 3, на 5 или на 7 единиц соответственно. Найдите наименьшее возможное при этих условиях значение отношение объёмов $VA :VB.$

Источники: Росатом-2022, региональный вариант, 11.4 (см. olymp.mephi.ru)

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

Подсказка 1

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

Подсказка 2

Мы можем выразить тройку как разность и понятно, в каком соотношении находятся отношение объемов и одна из сторон. Какие соотношения получатся?

Подсказка 3

Отношение объемов = 3*(a1) = 5*(a2) = 7*(a3). Подумаем, как использовать целочисленность сторон. Получается, что пришли к уравнениям в целых числах?) вспомним, как решать! 3, 5 и 7 даны не зря...

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

Обозначим

a1⋅a2⋅a3 C =VA :VB = b1 ⋅b2⋅b3

Из условий получаем

(a1+b-1⋅)b⋅a⋅2b⋅a3-− a1b⋅⋅ab2⋅⋅ab3= 3= 1b-⋅a⋅2b⋅a⋅3b = 1a-⋅C ⇒ C = 3⋅a1 1 2 3 1 2 3 1 2 3 1

Аналогично $C =5 ⋅a2$ и $C =7 ⋅a3.$

В этом случае целое число $C$ делится на $3,5$ и $7.$ С учетом взаимной простоты этих чисел, $C =105k,k ∈ℤ$ и $C ≥ 105.$

Покажем, что $C = 105$ реализуется как отношение объемов некоторых $PA$ и $PB.$ Например, $a1 =35,a2 =21,a3 = 15,b1 = 3,b2 = 5,b3 = 7.$ Тогда

36⋅21-⋅15-− 35⋅21⋅15= -21⋅15 =3 3⋅5⋅7 3⋅5⋅7 3⋅5⋅7

Аналогично,

35⋅22-⋅15- 35⋅21⋅15- -35⋅15 3⋅5⋅7 − 3⋅5⋅7 = 3⋅5⋅7 =5

35⋅21-⋅16-− 35⋅21⋅15= -35⋅21 =7 3⋅5⋅7 3⋅5⋅7 3⋅5⋅7

Ответ: 105

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

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

Какая наименьшая сумма цифр может быть у числа кратного $7?$

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

Пример: $1001 =7 ⋅143.$

Оценка: Предположим, что существует число, кратное $7,$ с суммой цифр, равной $1.$ Понятно, что среди его цифр имеется ровно одна единица, а остальные цифры — нули, значит единица находится на первом месте. Таким образом, это число имеет вид $n 10 ,$ то есть оно не может делиться на $7,$ противоречие.

Ответ:

$2$

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

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

В какое наименьшее количество цветов можно раскрасить натуральные числа от $1$ до $n$ так, чтобы никакие два различных числа одного цвета не давали в произведении точный квадрат?

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

Рассмотрим произвольное число $k,$ не превосходящее $n.$ Представим $k$ в виде $a2t,$ где $t$ — число, свободное от квадрата или равное $1$ (будем говорить, что $k$ имеет свободное от квадрата число $t$ ).

Покажем, что если два числа $a$ и $b$ в произведении дают квадрат и имеют свободные от квадрата числа $m$ и $n,$ то $m = n.$ Пусть это не так. Тогда либо существует такое простое число $p,$ что $m$ не кратно $p,$ а $n$ — кратно или наоборот. Но в таком случае $p$ входит в разложение $a$ в чётной степени, а в разложение $b$ — в нечётной или наоборот. Следовательно, $ab$ не квадрат, противоречие.

Из вышеописанных рассуждений также следует, что если $ab$ и $ac$ — квадраты, то $bc$ — также квадрат.

Теперь ясно, что все числа от $1$ до $n$ разбиваются на группы чисел с одинаковым свободным от квадрата числом. То есть любые два числа из одной группы в произведении дают квадрат, а любые два из разных — не дают.

Узнаем количество чисел в самой большой группе. Числа из произвольной группы в порядке возрастания выглядят так: $a21t,a22t,...,a2rt,t$ — свободное от квадрата или равное $1.$ В силу упорядочивания $a1 <a2 < ...<ar,$ но тогда количество чисел в группе не превосходит $ar.$

Найдём максимальное значение $ar.$ Мы знаем, что $a2rt≤n,$ откуда $∘-- √- ar ≤ nt ≤ n.$ Таким образом, $√- ar ≤[ n].$

Значит, количество чисел в самой большой группе не больше $√ - [ n].$ Такая группа есть: $√- 12,22,...,[ n]2.$ Значит, нам хватит $√- [ n]$ цветов, потому что мы можем в каждой группе раскрасить числа в разные цвета. Если же количество цветов меньше $√ - [ n],$ то в самой большой группе будут два числа одного цвета.

Ответ:

$[√n]$