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

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

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

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

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

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

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

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

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

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

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

Задача 1#88062

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

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

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

Поскольку произведение первых 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

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

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

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

Задача 2#87857

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

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

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

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

$PIC$

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

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

$PIC$

Ответ: 9

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

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

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

Задача 4#82288

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

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

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

Подсказка 1

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

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

У числа $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

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

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

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

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

Курсы

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

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

Задача 7#78897

В строку записано $2020$ натуральных чисел. Каждое из них, начиная с третьего, делится и на предыдущее, и на сумму двух предыдущих. Какое наименьшее значение может принимать последнее число в строке?

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

Пример. Условию задачи, очевидно, удовлетворяют числа $1,1,2!,3!,...,2019!,$ так как при любом натуральном $k$ число $(k+2)!$ делится как на $(k +1)!,$ так и на $(k +1)!+k!= k!(k+ 2).$

Оценка. Пусть $a,b,c$ — три подряд идущих числа в строке, но не первые три числа. Докажем, что $c -b b ≥a +1.$ По условию, $-b c a = x,b = y,$ где $x$ и $y$ натуральные. Тогда $c= by = axy,$ причём $c$ делится на $b+ a= ax+a = a(x+ 1).$ Получаем, что $axy$ делится на $a(x+ 1),$ откуда $xy$ делится на $x+ 1,$ и так как $x$ и $x +1$ взаимно просты, $y$ делится на $x+1,$ то есть $y ≥ x+ 1,$ что и требовалось.

Заметим, что первые два числа не меньше $1$ каждое. Третье число больше второго (так как делится на сумму второго и первого), а значит, хотя бы в два раза больше второго (так как делится на него и не равно ему). По доказанному выше, четвёртое число тогда хотя бы в $3$ раза больше третьего, пятое — хотя бы в $4$ раза больше четвёртого, и так далее, откуда по индукции получаем, что $k$ -е число не меньше, чем ( $k− 1$ )! при всех натуральных $k.$

Ответ:

$2019!$

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

Задача 8#78887

Найдите следующее после $2020$ число, которое оканчивается на $2020$ и делится на $2020.$

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

Заметим, что раз число оканчивается на $2020$ и делится на $2020,$ то делится и на $101.$ Значит, если записать наше число в виде $--- abc2020$ (далее станет понятно, почему трёх цифр перед $2020$ достаточно), то $--- 4 abc⋅10$ должно делиться на $101$ ( $2020$ уже делится и всё число по условию должно делится). При этом $4 10$ взаимно просто со $101,$ но делится на $20,$ а наименьшее число делящееся на $101$ равно $101$ (понятно, что однозначные и двухзначные не подходят). Итого, получаем число $1012020.$

Ответ:

$1012020$

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

Задача 9#78886

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

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

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

Ответ:

$4045$

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

Задача 10#73690

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

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

Пример для $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$

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

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

Интенсивы

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

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

Задача 12#64951

Для какого наибольшего натурального числа $n$ число $n3+ 7n2− 2n +100$ делится на число $n+ 10?$

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

Заметим, что $n ≡ −10. n+10$ Тогда

3 2 3 2 n + 7n − 2n+ 100n≡+10(− 10) + 7⋅(− 10) − 2⋅(−10)+ 100 =− 180

Получается, что $( ) n3+ 7n2− 2n +100 +180$ всегда делится на $n +10$ . Чтобы $n3+ 7n2− 2n +100$ делилось на $n+ 10$ , получается, что $180$ делится на $n+ 10,$ откуда $180≥ n+ 10$ , а наибольшее натуральное $n$ равно $180− 10 =170.$

Ответ: 170

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

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

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

Задача 14#81489

В какое наименьшее количество цветов можно раскрасить натуральные числа от $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]$

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

Задача 15#81487

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

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

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

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

Ответ:

$2$

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

Задача 16#76634

Длины ребер $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

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

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

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

Задача 17#74576

$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

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

Задача 18#72978

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

Источники: ММО-2022, 11.2, (см. 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$

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

Задача 19#72743

Можно ли найти четыре различных натуральных числа, каждое из которых не делится ни на $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.$

Ответ: да

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

Задача 20#72253

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

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

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

Подсказка 1

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

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

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

Ответ: 6200

Предыдущий раздел

Следующий раздел