Теория чисел в задаче 19

01устройство задачи

Три пункта — три разных вопроса

Задача 19 почти всегда устроена одинаково. Условие описывает набор чисел, доску, кучки камней или последовательность.

Дальше идут три вопроса. Выглядят они похоже, но требуют разных рассуждений, и решать их удобно по отдельности.

Пункт а): достаточно примера

Здесь обычно спрашивается, может ли что-то случиться. Если ответ «да», хватит одного примера — конкретных чисел, для которых выполнены все условия.

Пункт б): доказать, что нельзя

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

Для этого ищут свойство, которое есть у всех допустимых наборов и которого нет у требуемого. Это чётность, остаток, делимость или оценка суммы.

Пункт в): оценка и пример

Здесь просят найти наибольшее или наименьшее значение. Ответ состоит из двух утверждений.

Оценка: для любого допустимого набора величина не больше числа $M$ .

Пример: существует набор, на котором она равна $M$ .

Без примера оценка может оказаться грубой. Без оценки пример может оказаться не лучшим.

Так же устроены и критерии проверки. За задачу ставят до 4 баллов:

\begin{aligned} 4 &: \text{а)} + \text{б)} + \text{в)}, \\ 3 &: \text{в)} + \text{одна из а), б)}, \\ 2 &: \text{а)} + \text{б)}\ \text{или одна в)}, \\ 1 &: \text{одна из а), б)}. \end{aligned}

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

Спрашивают про разность масс. На сцене ниже можно разложить камни самому и посмотреть, какие разности выходят.

Камней по 7 кг3 из 4Камней по 22 кг4 из 9

первая кучка—вторая кучка—разность—

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

разбор линия 19ЕГЭ-2024, основная волна, разные города

На столе лежат 4 камня по 7 кг и 9 камней по 22 кг. Их разделили на две кучки.

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

Дано

$4 \cdot 7\ \text{кг}$

$9 \cdot 22\ \text{кг}$

Найти

$d_{\min} > 0$

лёгких камней	0	1	2	3	4
их масса, кг	0	7	14	21	28
остаток по 22	0	7	14	21	6

Остаток массы кучки при делении на 22 задают только лёгкие камни. Остатков 1, 2 и 3 среди них нет.

Сведём разность к массе одной кучки. Общая масса камней равна

4\cdot 7 + 9\cdot 22 = 226\ \text{кг}.

Пусть в лёгкой кучке $m$ кг. Тогда в другой $226 - m$ кг, и разность равна

d = 226 - 2m,\qquad m \le 113.

Вопрос свёлся к одному: какие массы $m$ вообще набираются из этих камней.

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

Лёгких камней в кучке от нуля до четырёх, то есть 0, 7, 14, 21 или 28 кг. Остатки получаются такие:

0,\ 7,\ 14,\ 21,\ 6.

Других остатков у кучки не бывает. Значит, из этого списка выводятся все три пункта.

а) Разность 8 кг означает кучки 109 и 117 кг.

Число 109 даёт остаток 21: это три лёгких камня и $(109 - 21) : 22 = 4$ тяжёлых.

Первая кучка — 3 камня по 7 кг и 4 по 22 кг. Вторая — 1 камень по 7 кг и 5 по 22 кг, то есть $7 + 110 = 117$ кг.

б) Равные кучки весили бы по 113 кг. Остаток числа 113 при делении на 22 равен 3, такого остатка в списке нет, и кучку в 113 кг не набрать.

в) Оценка. Разность $226 - 2m$ чётна, а нулю она не равна по пункту б).

Разность 2 кг требует $m = 112$ , разность 4 кг — $m = 111$ . Остатки этих чисел равны 2 и 1, и в списке их тоже нет.

Поэтому разность не меньше 6 кг.

в) Пример. Остаток числа 110 равен нулю, то есть это пять камней по 22 кг и ни одного лёгкого.

Во второй кучке тогда $226 - 110 = 116$ кг, и разность равна 6 кг.

Ответ: а) да; б) нет; в) 6 кг

02остатки

Чётность и остатки

Самый короткий способ доказать, что что-то «нельзя», — найти свойство, которое не меняется. Чаще всего это чётность или остаток от деления на небольшое число.

Чётность суммы

Сумма целых чисел нечётна тогда и только тогда, когда нечётных слагаемых нечётное количество.

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

\text{нечёт} + \text{нечёт} = \text{чёт}.

Если нечётных слагаемых нечётное число, одно остаётся без пары и делает нечётной всю сумму.

Деление с остатком

Любое целое $a$ при делении на натуральное $m$ записывается единственным образом в виде

a = mq + r,\quad 0 \le r < m.

Здесь $q$ — неполное частное, $r$ — остаток.

Остаток суммы и произведения задаётся остатками слагаемых и множителей.

Пусть $a = mq_1 + r_1$ и $b = mq_2 + r_2$ . Тогда

\begin{aligned} a + b &= m(q_1 + q_2) + (r_1 + r_2), \\ ab &= m(mq_1q_2 + q_1r_2 + q_2r_1) + r_1r_2. \end{aligned}

Первые слагаемые делятся на $m$ . Поэтому $a + b$ даёт тот же остаток, что $r_1 + r_2$ , а $ab$ — тот же, что $r_1 r_2$ .

Отсюда последняя цифра произведения зависит только от последних цифр множителей, то есть от $r_1$ и $r_2$ при $m = 10$ .

Числа с одинаковыми остатками при делении на $m$ называют сравнимыми по модулю $m$ и пишут

a \equiv b \pmod m.

Это то же самое, что «разность $a - b$ делится на $m$ ».

Запись ввёл Гаусс в «Арифметических исследованиях» 1801 года. На экзамене ей можно пользоваться, но проще расписать подробно словами.

Шаги по кругу остатков

Остатки при делении на $m$ удобно представлять делениями на циферблате. Прибавить к числу $k$ — значит сдвинуться по кругу на $k$ делений.

Стартуем с нуля и шагаем много раз. Точка побывает в остатках $0,\ k,\ 2k,\ \ldots$ , и какие из них встретятся, решает наибольший общий делитель:

d = \text{НОД}(m, k).

Все числа $jk$ делятся на $d$ , и $m$ делится на $d$ . Поэтому остатки $jk$ тоже кратны $d$ , а другие деления недостижимы.

Точка возвращается в ноль, когда $jk$ впервые делится на $m$ , то есть при $j = m/d$ .

За эти $m/d$ шагов остатки не повторяются, а кратных $d$ делений на круге ровно $m/d$ . Значит, точка обходит их все.

Делений на кругеm = 10Шагk = 4

НОД(m, k)—цикл—достижимы—

Меняй число делений и шаг. Серые деления точка не посетит никогда: достижимы только остатки, кратные НОД(m, k).

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

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

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

разбор линия 19ЕГЭ-2022, основная волна, Санкт-Петербург

Есть четыре коробки: в первой коробке 101 камень, во второй — 102, в третьей — 103, а в четвёртой коробке камней нет. За один ход берут по одному камню из любых трёх коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.

а) Могло ли в первой коробке оказаться 97 камней, во второй — 102, в третьей — 103, а в четвёртой — 4?
б) Могло ли в четвёртой коробке оказаться 306 камней?
в) Какое наибольшее число камней могло оказаться в первой коробке?

Дано

$(101,\ 102,\ 103,\ 0)$

$\text{ход: } -1,\ -1,\ -1,\ +3$

Найти

$\max\ \text{в первой коробке}$

коробка	1-я	2-я	3-я	4-я
камней вначале	101	102	103	0
остаток по 4	1	2	3	0

Остатки всех коробок попарно разные. Ход убавляет каждый на единицу, поэтому разными они и останутся.

Ход удобно описать иначе. Из каждой коробки убирают по камню, а затем в одну из них кладут четыре.

(-1,\ -1,\ -1,\ +3) = (-1,\ -1,\ -1,\ -1) + (0,\ 0,\ 0,\ +4).

Значит, остаток при делении на 4 убавляется на единицу сразу во всех коробках.

Разность любых двух количеств меняется на 0 или на 4, и остатки, которые были разными, разными и останутся.

Камней 101, 102, 103 и 0, поэтому остатки при делении на 4 равны

1,\ 2,\ 3,\ 0.

Все четыре разные. Общее число камней $306$ при ходах тоже не меняется.

а) Да. Положим камни дважды в четвёртую коробку, затем в третью и во вторую:

\begin{aligned} &(101, 102, 103, 0) \\ &\to (100, 101, 102, 3) \\ &\to (99, 100, 101, 6) \\ &\to (98, 99, 104, 5) \\ &\to (97, 102, 103, 4). \end{aligned}

б) Нет. Если в четвёртой коробке 306 камней, остальные три пусты:

(0,\ 0,\ 0,\ 306)\ \to\ \text{остатки } 0,\ 0,\ 0,\ 2.

Тогда у трёх коробок остаток одинаковый, а по шагу 1 остатки попарно разные.

в) Оценка. Во второй, третьей и четвёртой коробках остатки разные, значит, это три разных неотрицательных числа.

Их сумма не меньше $0 + 1 + 2 = 3$ , поэтому в первой коробке камней не больше, чем

306 - 3 = 303.

в) Пример. Сделаем 25 ходов в четвёртую коробку, затем 75 ходов в первую, затем по одному ходу в четвёртую и в первую:

\begin{aligned} &(101, 102, 103, 0) \to (76, 77, 78, 75) \\ &\to (301, 2, 3, 0) \to (300, 1, 2, 3) \\ &\to (303, 0, 1, 2). \end{aligned}

Все промежуточные количества неотрицательны, и в первой коробке 303 камня.

Ответ: а) да; б) нет; в) 303

если ход не меняет остатка, число с другим остатком не получить

03цифры

Признаки делимости и цифры

Задачи про цифры числа решаются теми же остатками, только модуль выбирается под десятичную запись. Число с цифрами $a_k, \ldots, a_1, a_0$ — это сумма разрядов:

\begin{aligned} n &= a_k \cdot 10^k + \ldots + a_2 \cdot 100 \\ &\quad {}+ a_1 \cdot 10 + a_0. \end{aligned}

Делимость на 2, 5, 4 и 25

Все разряды, начиная с десятков, делятся на 10. Поэтому остаток числа при делении на 2, 5 и 10 такой же, как у последней цифры.

Все разряды, начиная с сотен, делятся на 100, а значит, и на 4, и на 25. Остаток по этим модулям задают две последние цифры.

Делимость на 3 и 9

Каждую степень десяти запишем как число из девяток плюс единица:

10 = 9 + 1,\quad 100 = 99 + 1,\quad 1000 = 999 + 1.

Число из девяток делится на 9, поэтому

\begin{aligned} n &= (a_k \cdot 99\ldots9 + \ldots + a_1 \cdot 9) \\ &\quad + (a_k + \ldots + a_1 + a_0). \end{aligned}

Первая скобка делится на 9 при любых цифрах.

Значит, число и сумма его цифр $S(n)$ дают одинаковые остатки при делении на 9, а потому и при делении на 3.

Признаки делимости на 3 и на 9 — частный случай этого равенства, когда остаток нулевой.

разность $n - S(n)$ делится на 9 у любого числа

Делимость на 11

Для 11 степени десяти раскладываются через ближайшие кратные одиннадцати:

\begin{aligned} 10 &= 11 - 1, & 100 &= 99 + 1, \\ 1000 &= 1001 - 1, & 10\,000 &= 9999 + 1. \end{aligned}

Единица входит то с минусом, то с плюсом. Поэтому число даёт тот же остаток при делении на 11, что и знакопеременная сумма цифр, взятая от младшей:

\begin{aligned} n \equiv a_0 - a_1 + a_2 - a_3 + \ldots \\ \pmod{11}. \end{aligned}

число—сумма цифр—остаток числа—остаток суммы—

Нажимай на верх или низ плитки, чтобы менять цифры. Синие слагаемые делятся на 9 (или на 11) при любых цифрах, поэтому остаток числа всегда равен остатку второго слагаемого — оно выделено розовым внизу.

Делимость на составное число

Число делится на 45 тогда и только тогда, когда оно делится на 5 и на 9.

Кратное 45 делится на оба числа, поскольку $45 = 5 \cdot 9$ .

Обратное утверждение опирается на то, что 5 и 9 взаимно просты. Если $n = 9t$ делится на 5, то простой множитель 5 входит в $t$ : в разложении девятки его нет.

t = 5s \;\Longrightarrow\; n = 45s.

Для чисел с общим делителем так рассуждать нельзя, ведь 12 делится на 4 и на 6, но не делится на 24.

разбор линия 19ЕГЭ-2024, досрочная волна, Москва

Дан набор цифр 0, 1, 2, 3, 5, 7, 9. Из него выбирают три различные цифры и составляют трёхзначное число $A$ . Из оставшихся четырёх цифр составляют четырёхзначное число $B$ . Известно, что число $A$ кратно 45 и число $B$ кратно 45.

а) Может ли сумма чисел $A + B$ быть равна 2205?
б) Может ли сумма чисел $A + B$ быть равна 3435?
в) Чему равна наибольшая возможная сумма чисел $A + B$ ?

Дано

$0,\ 1,\ 2,\ 3,\ 5,\ 7,\ 9$

$A \,\vdots\, 45,\ \ B \,\vdots\, 45$

Найти

$\max\,(A + B)$

разряд	тыс.	сотни	десятки	ед.
B, четыре цифры	9	?	?	5
A, три цифры	—	?	?	0

Нуль и пятёрка заняты разрядом единиц, девятка — старшим разрядом B. На места вопросов идут цифры 1, 2, 3, 7.

Число кратно 45 тогда и только тогда, когда оно делится на 5 и на 9.

На 5 делится число, оканчивающееся на 0 или 5. Каждая цифра берётся один раз, поэтому нуль достаётся одному числу, а пятёрка — другому.

На 9 делится число, у которого сумма цифр кратна 9. Сумма всех семи цифр

0 + 1 + 2 + 3 + 5 + 7 + 9 = 27

тоже кратна 9. Поэтому если сумма цифр $A$ кратна 9, то у $B$ она кратна 9 сама собой.

а) Да: $270 + 1935 = 2205$ .

У числа 270 сумма цифр 9 и последняя цифра 0, у 1935 — сумма 18 и последняя цифра 5. Вместе они берут все семь цифр по разу.

б) Нет. Оба числа делятся на 9, значит, и сумма делится на 9.

У числа 3435 сумма цифр на 9 не делится:

3 + 4 + 3 + 5 = 15.

в) Оценка. Если первая цифра $B$ меньше 9, то $B < 8000$ и $A < 1000$ , а сумма меньше 9000.

Поэтому у наибольшей суммы число $B$ начинается с девятки.

Нуль и пятёрка стоят в разряде единиц, а цифры 1, 2, 3, 7 занимают сотни и десятки обоих чисел.

Пусть в сотнях стоят цифры с суммой $H$ . Тогда в десятках стоят цифры с суммой $13 - H$ , и

\begin{aligned} A + B &= 9000 + 100H \\ &\quad {}+ 10(13 - H) + 5 \\ &= 9135 + 90H. \end{aligned}

Сумма двух цифр из 1, 2, 3, 7 не больше $7 + 3 = 10$ , поэтому

A + B \le 9135 + 900 = 10\,035.

в) Пример. $B = 9315$ : сумма цифр 18, оканчивается на 5.

$A = 720$ : сумма цифр 9, оканчивается на 0. Оба делятся на 45, цифры не повторяются, а сумма равна $9315 + 720 = 10\,035$ .

Ответ: а) да; б) нет; в) 10 035

04оценка

Оценка

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

Инструментов здесь три.

Различные числа не бывают маленькими

Упорядочим $k$ различных натуральных чисел по возрастанию:

a_1 < a_2 < \ldots < a_k.

Наименьшее не меньше 1, а каждое следующее больше предыдущего хотя бы на 1. Поэтому $a_i \ge i$ , и после сложения

\begin{aligned} &a_1 + a_2 + \ldots + a_k \\ &\ge 1 + 2 + \ldots + k \\ &= \frac{k(k+1)}{2}. \end{aligned}

Если все числа больше $m$ , то так же $a_i \ge m + i$ , и сумма не меньше $(m + 1) + \ldots + (m + k)$ .

Этой оценкой ограничивают количество чисел. Наименьшая возможная сумма растёт как $k^2/2$ , поэтому при известной сумме слишком много чисел не поместится.

Среднее лежит между крайними

Среднее арифметическое $n$ чисел не больше наибольшего из них и не меньше наименьшего.

Если бы все числа были меньше среднего, их сумма была бы меньше, чем $n$ средних, — меньше самой себя.

\min a_i \;\le\; \frac{a_1 + \ldots + a_n}{n} \;\le\; \max a_i.

Это же рассуждение называют принципом Дирихле.

Если $n + 1$ предмет разложен по $n$ ящикам, то в среднем на ящик приходится больше одного предмета, и в каком-то ящике их не меньше двух.

Для целых величин оценку усиливают округлением: если сумма $n$ натуральных чисел равна $S$ , то

\max a_i \;\ge\; \left\lceil \frac{S}{n} \right\rceil.

Сколько чиселn = 6

сумма——наибольшее——

Тяни столбики вверх и вниз. Различные числа не опускаются ниже пунктирных ступенек 1, 2, …, n, а при сумме 40 самый высокий столбик не бывает ниже среднего.

Делимость как оценка

Третье наблюдение связывает оценку с предыдущими разделами.

Если из условия следует, что количество чисел делится на 25, то чисел не меньше 25, и это неравенство получено из делимости. Так устроена первая задача раздела.

разбор линия 19ЕГЭ-2022, резервный день основной волны

На доске написано несколько различных натуральных чисел. Дробная часть среднего арифметического этих чисел равна 0,32 (то есть если вычесть из среднего арифметического этих чисел 0,32, то получится целое число).

а) Могло ли на доске быть написано меньше 100 чисел?
б) Могло ли на доске быть написано меньше 20 чисел?
в) Найдите наименьшее возможное значение среднего арифметического этих чисел.

Дано

$\text{числа натуральные и различные}$

$\text{дробная часть среднего } 0{,}32$

Найти

$\min\ \text{среднего}$

Среднее имеет вид «целое плюс 0,32» и не меньше 13. Наименьшее такое число — 13,32.

Пусть на доске $n$ чисел, а их среднее равно $x + 0{,}32$ , где $x$ целое.

Сумма чисел целая, поэтому целым обязано быть и

n(x + 0{,}32) - nx = 0{,}32n = \frac{8n}{25}.

Числа 8 и 25 взаимно просты, значит, $n$ делится на 25. Это главное следствие условия: из него выводятся все три ответа.

а) Да. Возьмём 25 чисел: $1, 2, \ldots, 24$ и 33.

Их сумма $300 + 33 = 333$ , среднее $333 : 25 = 13{,}32$ . Чисел меньше 100.

б) Нет. Количество чисел делится на 25, поэтому их не меньше 25.

в) Оценка. Чисел $n \ge 25$ , и они различны, поэтому их сумма не меньше

1 + 2 + \ldots + n = \frac{n(n+1)}{2},

а среднее не меньше

\frac{n + 1}{2} \ge \frac{25 + 1}{2} = 13.

Среднее имеет вид «целое плюс 0,32» и не меньше 13, поэтому наименьшее возможное значение равно

13 + 0{,}32 = 13{,}32.

в) Пример. Набор из пункта а): его среднее равно ровно 13,32.

Ответ: а) да; б) нет; в) 13,32

Во второй задаче работают сразу оба неравенства раздела.

Среднее ограничивает снизу наибольшее число на красных карточках, а оно — все синие числа и их сумму.

разбор линия 19ЕГЭ-2019, основная волна, Центр

Есть синие и красные карточки. Всего карточек 50 штук. На каждой карточке написано натуральное число. Среднее арифметическое всех чисел равно 16. Все числа на синих карточках разные.

При этом любое число на синей карточке больше, чем любое на красной. Числа на синих увеличили в 2 раза, после чего среднее арифметическое стало равно 31,2.

а) Может ли быть 10 синих карточек?
б) Может ли быть 10 красных карточек?
в) Какое наибольшее количество синих карточек может быть?

Дано

$50\ \text{карточек},\ \text{среднее } 16$

$\text{синие удвоены: среднее } 31{,}2$

Найти

$\max\ \text{числа синих}$

сумма чисел	синие	красные	всего
как было	760	40	800
синие удвоены	1520	40	1560

Удвоение прибавило ровно сумму синих. Отсюда синие дают 760, красные — 40.

Пусть $S_{\text{с}}$ — сумма чисел на синих карточках, $S_{\text{к}}$ — на красных. Два средних дают систему:

\begin{aligned} S_{\text{с}} + S_{\text{к}} &= 50 \cdot 16 = 800, \\ 2S_{\text{с}} + S_{\text{к}} &= 50 \cdot 31{,}2 = 1560. \end{aligned}

Вычитая, находим $S_{\text{с}} = 760$ и $S_{\text{к}} = 40$ .

Дальше остаётся один вопрос, как разложить эти суммы по карточкам.

а) Да. На 40 красных карточках напишем единицы — их сумма 40.

На синих напишем $2, 3, \ldots, 10$ и 706: сумма $54 + 706 = 760$ , числа разные и больше единицы.

б) Нет. Если красных карточек 10, их среднее равно 4, и наибольшее красное число не меньше 4.

Тогда каждое синее число не меньше 5, а 40 разных синих чисел дают сумму не меньше

\begin{aligned} &5 + 6 + \ldots + 44 \\ &= \frac{(5 + 44)\cdot 40}{2} \\ &= 980 > 760. \end{aligned}

в) Оценка. Пусть синих карточек $k \ge 36$ . Тогда красных не больше 14, их среднее не меньше $40 : 14 > 2$ , и наибольшее красное число не меньше 3.

Все синие числа разные и не меньше 4, поэтому

\begin{aligned} S_{\text{с}} &\ge 4 + 5 + \ldots + (k + 3) \\ &\ge 4 + \ldots + 39 \\ &= 774 > 760. \end{aligned}

Противоречие, значит, синих карточек не больше 35.

в) Пример. Красных карточек 15: двенадцать троек, одна двойка и две единицы, сумма $36 + 2 + 2 = 40$ .

Синих 35: числа $4, 5, \ldots, 37$ с суммой 697 и число 63.

Сумма синих $697 + 63 = 760$ , все они разные и больше любого красного.

Ответ: а) да; б) нет; в) 35

05пример

Пример, который достигает оценки

Оценка говорит, что лучше некоторого числа сделать нельзя. Пример показывает, что это число достигается.

Искать пример наугад долго, поэтому его строят одним из трёх способов.

От оценки назад

Оценка — цепочка неравенств, и в примере каждое из них должно обратиться в равенство.

В задаче про среднее 13,32 неравенств было два: чисел не меньше 25 и сумма не меньше, чем

1 + 2 + \ldots + 25 = 325.

Равенство в первом означает ровно 25 чисел, во втором — числа $1, 2, \ldots, 25$ .

Но у них среднее 13, а нужно 13,32, то есть сумма 333.

Недостающие 8 прибавим к наибольшему числу: числа останутся различными, и пример $1, \ldots, 24, 33$ готов.

Жадно

Набор строится по одному элементу, и каждый раз берётся самый выгодный из допустимых.

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

С малых случаев

Если условие большое — 425 чисел, 800 монет, — полезно решить ту же задачу для 5 или 10.

Закономерность, замеченная на малых числах, подсказывает пример для больших. Доказывать его всё равно придётся проверкой.

Проверка примера

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

Различны ли числа, натуральны ли они, не выходят ли за границы, выполняется ли условие для любых троек, пар или отрезков, если так сказано в условии.

Решения уравнения в целых числах

Многие задачи 19 сводятся к уравнению в целых неотрицательных числах.

Если есть монеты по $a$ , $b$ и $c$ рублей, то сумма $N$ набирается тогда и только тогда, когда есть решение у уравнения

ax + by + cz = N.

Здесь $x, y, z$ — количества монет, а решения — целые точки на плоскости.

У отсутствия решений бывают две причины.

Первая — сумма слишком велика: плоскость проходит мимо всех допустимых наборов.

Вторая — делимость. Левая часть делится на $\text{НОД}(a, b, c)$ при любых целых $x, y, z$ , и если $N$ на него не делится, плоскость идёт между узлами решётки.

Обе причины — оценки, а любая розовая точка — пример.

Коэффициент a2Коэффициент b3Коэффициент c5Сумма N17

решения естьточек на плоскости7НОД(a, b, c)1пример (x; y; z)(2; 1; 2)

Каждый узел — набор целых x, y, z от 0 до 6, розовые лежат на плоскости ax + by + cz = N. Поставь a = 4, b = 6, c = 8 и нечётное N: плоскость режет куб, но ни через один узел не проходит. Куб можно вращать.

разбор линия 19ЕГЭ-2024, резервный день досрочной волны

В продуктовом магазине есть весы с двумя чашами. На одну чашу весов кладут только продукты, на другую — гири. На чашу для гирь можно положить несколько гирь. Магазину разрешено продавать только целое число килограммов продуктов.

а) Можно ли некоторым набором из пяти гирь отвесить любое целое число килограммов от 1 до 25?
б) Можно ли некоторым набором из четырёх гирь отвесить любое целое число килограммов от 1 до 25?
в) Найдите наибольшее значение $n$ такое, что любой вес от 1 до $n$ килограммов можно отвесить каким-нибудь набором из 5 гирь.

Дано

$\text{гири кладут на одну чашу}$

$\text{вес продукта } 1, 2, \ldots, n\ \text{кг}$

Найти

$n_{\max}\ \text{для пяти гирь}$

гиря, кг	1	2	4	8	16
доступно до, кг	1	3	7	15	31

Каждая следующая гиря тяжелее суммы прежних на единицу, и доступный отрезок удваивается.

Каждый вес отвешивается каким-то непустым набором гирь.

Из пяти гирь таких наборов

2^5 - 1 = 31.

Это и даёт оценку. Пример строится жадно, по одной гире.

а) Да. Гиря 1 кг отвешивает 1 кг. Вторую возьмём в 2 кг — доступны все веса до 3 кг.

Третью возьмём в 4 кг. Её добавляют к каждому весу от 0 до 3, и отрезок доходит до

1 + 2 + 4 = 7.

Так же 8 кг дают веса до 15 кг, а 16 кг — до 31 кг:

1 + 2 + 4 + 8 + 16 = 31.

Набор 1, 2, 4, 8, 16 покрывает и отрезок от 1 до 25.

б) Нет. Каждую из четырёх гирь можно взять или не взять, всего $2^4 = 16$ вариантов, и один из них — не брать ничего. Различных весов не больше 15, а нужно 25.

в) Оценка. Различных весов не больше 31, поэтому при $n = 32$ все веса не покрыть, и $n \le 31$ .

в) Пример. Тот же набор 1, 2, 4, 8, 16: любое число от 1 до 31 записывается пятью двоичными разрядами, например $25 = 16 + 8 + 1$ , и гири берутся по единицам этой записи.

Ответ: а) да; б) нет; в) 31

06сводка

Шпаргалка и типичные ошибки

Формул в задаче 19 мало, и все они короткие. Баллы чаще теряют на логике, чем на вычислениях. Пример без проверки, оценка без примера, пропущенное доказательство там, где ответ кажется ясным.

a = mq + r,\ \ 0 \le r < m

деление с остатком

a \equiv b \pmod m \iff m \mid a - b

одинаковые остатки — разность делится на m

n \equiv S(n) \pmod 9

число и сумма цифр: признаки делимости на 3 и 9

n \equiv a_0 - a_1 + a_2 - \ldots \pmod{11}

знакопеременная сумма цифр от младшей

a_1 + \ldots + a_k \ge \dfrac{k(k+1)}{2}

сумма k различных натуральных чисел

\min a_i \le \dfrac{a_1 + \ldots + a_n}{n} \le \max a_i

среднее между крайними, принцип Дирихле

0,\ k,\ 2k,\ \ldots\ \to\ \text{кратные } \text{НОД}(m, k)

какие остатки по модулю m даёт шаг k

2^n - 1

непустых наборов из n предметов

Типичные ошибки

В пункте а) приведён пример, но не проверено, что он удовлетворяет всем условиям.

Пример подставляют в каждое условие: различие, натуральность, границы, «для любых» наборов.

В пункте в) доказано, что больше 35 нельзя, и на этом решение закончено.

Нужен ещё пример, на котором 35 достигается, — иначе оценка может оказаться грубой.

В пункте в) приведён пример на 35 без доказательства, что больше нельзя.

Пример — половина ответа. Вторая половина — оценка для любого допустимого набора.

«Очевидно, что так сделать нельзя» или «перебрал варианты и не нашёл».

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

Число делится на 4 и на 6, значит, делится на 24.

Так можно только для взаимно простых делителей: на 4 и на 6 делится 12, но не 24.

Оценка проведена для одного удобного набора чисел.

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

задачи

Проверьте себя

Решите задачу, впишите ответ на пункт в) и нажмите «Проверить».

Ответы на пункты а) и б) и все доказательства — в разборе, он открывается кнопкой под задачей.

Все восемь задач — из вариантов ЕГЭ разных лет.

На доске написано несколько различных натуральных чисел, которые делятся на 3 и оканчиваются на 4.

а) Может ли сумма составлять 282?
б) Может ли их сумма составлять 390?
в) Какое наибольшее количество чисел могло быть на доске, если их сумма равна 2226?

ЕГЭ-2020, основная волна, Краснодар

в)

Разбор

Решение

Разность двух из них делится на 3 и на 10, то есть на 30.

Значит, у всех один вид:

30t + 24:\quad 24,\ 54,\ 84,\ 114,\ 144,\ \ldots

а) Да: $24 + 54 + 204 = 282$ .

б) Нет. Последняя цифра суммы $k$ чисел совпадает с последней цифрой $4k$ и равна нулю только при $k$ , кратном 5.

Но пять наименьших таких чисел дают уже слишком много:

24 + 54 + 84 + 114 + 144 = 420 > 390.

в) Оценка. Последняя цифра $4k$ должна быть 6, а это верно при $k = 4, 9, 14, \ldots$

Числа различны, поэтому их сумма не меньше суммы $k$ наименьших подходящих:

\begin{aligned} &24 + 54 + \ldots + (30k - 6) \\ &= 15k^2 + 9k. \end{aligned}

При $k = 14$ это 3066 — больше 2226, а при больших $k$ и подавно. Значит, $k \le 9$ .

в) Пример. Восемь чисел $24, 54, \ldots, 234$ дают в сумме 1032.

Добавим девятое, 1194: оно делится на 3 и оканчивается на 4, а сумма равна $1032 + 1194 = 2226$ .

Ответ: а) да; б) нет; в) 9

Дано натуральное число. На каждом ходе из него либо вычитают утроенную сумму цифр, либо прибавляют утроенную сумму цифр, так, что полученное число остаётся натуральным.

а) Могло ли из числа 65 получиться число 41?
б) Могло ли из числа 65 получиться число 43?
в) Какое наименьшее двузначное число можно получить из 65?

ЕГЭ-2023, досрочная волна, Урал

в)

Разбор

Решение

Ход меняет число на утроенную сумму цифр, то есть на кратное 3.

Поэтому остаток при делении на 3 не меняется никогда:

65 \equiv 2 \pmod 3.

а) Да, тремя ходами:

65 - 33 = 32,\quad 32 - 15 = 17,\quad 17 + 24 = 41.

б) Нет. Остатки у 65 и 43 разные:

65 \equiv 2 \pmod 3,\qquad 43 \equiv 1 \pmod 3.

в) Оценка. Получаются только числа с остатком 2 при делении на 3. Число 10 даёт остаток 1 и не подходит, поэтому двузначного меньше 11 не получить.

в) Пример. Цепочка ходов, которая доводит 65 до 11:

\begin{aligned} &65 \to 98 \to 149 \to 107 \\ &\to 83 \to 50 \to 35 \to 11. \end{aligned}

Ответ: а) да; б) нет; в) 11

Есть 16 монеток по 2 рубля и 29 монеток по 5 рублей.

а) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 175?
б) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 176?
в) Какое наименьшее количество монеток по 1 рублю нужно добавить в набор, чтобы можно было получить любую целую сумму от 1 до 180 включительно?

ЕГЭ-2024, основная волна, разные города

в)

Разбор

Решение

Посчитаем, сколько всего денег:

16\cdot 2 + 29\cdot 5 = 177\ \text{рублей}.

а) Да, берём все монеты, кроме одной двухрублёвой.

б) Нет. Невзятые монеты должны давать 1 рубль, а самая мелкая монета — 2 рубля.

в) Оценка. С $k$ рублёвыми монетами всего денег $177 + k$ рублей.

Для суммы 180 нужно $177 + k \ge 180$ , то есть $k \ge 3$ .

в) Пример. Трёх монет хватает. Всего теперь 180 рублей, и сумма $S$ набирается тогда же, когда $180 - S$ : берутся остальные монеты.

Поэтому хватит проверить суммы до 90. Любое такое $S$ запишем с остатком:

S = 5q + r,\qquad q \le 18,\ \ 0 \le r \le 4.

Берём $q$ пятирублёвых, а остаток набираем как $1,\ 2,\ 2 + 1,\ 2 + 2$ .

Ответ: а) да; б) нет; в) 3

Есть контейнеры массой 7 тонн и массой 2 тонны и корабли грузоподъёмностью 10 тонн.

а) Можно ли увезти за один раз 11 контейнеров массой 7 тонн и 22 контейнера массой 2 тонны на 14 кораблях?
б) Можно ли увезти за один раз 11 контейнеров массой 7 тонн и 17 контейнеров массой 2 тонны на 12 кораблях?
в) На каком наименьшем количестве кораблей можно увезти за один раз 11 контейнеров массой 7 тонн и 77 контейнеров массой 2 тонны?

ЕГЭ-2023, резервный день основной волны, Санкт-Петербург

в)

Разбор

Решение

Два тяжёлых контейнера не помещаются, а к одному тяжёлому — не больше одного лёгкого:

7 + 7 > 10,\qquad 7 + 2 + 2 > 10.

Корабль без тяжёлых контейнеров везёт не больше пяти лёгких.

а) Да. На 11 кораблей — по контейнеру 7 т и 2 т, а оставшиеся 11 лёгких уходят на три корабля по 5, 5 и 1.

11 + 3 = 14\ \text{кораблей}.

б) Нет. Тяжёлые контейнеры занимают 11 кораблей и увозят с собой не больше 11 лёгких.

Свободных кораблей остаётся один, а лёгких на него приходится больше пяти:

17 - 11 = 6 > 5.

в) Оценка. Кораблей с тяжёлыми контейнерами ровно 11, с ними уходит не больше 11 лёгких.

Остаётся не меньше 66 лёгких, а на корабль их влезает пять:

\left\lceil \frac{66}{5} \right\rceil = 14,\qquad 11 + 14 = 25.

в) Пример. Одиннадцать кораблей «7 т + 2 т», тринадцать по пять лёгких и один с одним лёгким:

11 + 65 + 1 = 77.

Ответ: а) да; б) нет; в) 25

Дано трёхзначное натуральное число, не кратное 100.

а) Может ли частное этого числа и суммы его цифр быть равным 13?
б) Может ли частное этого числа и суммы его цифр быть равным 6?
в) Какое наибольшее натуральное значение может иметь частное данного числа и суммы его цифр, если первая цифра данного числа равна 6?

ЕГЭ-2021, основная волна, Москва и Санкт-Петербург

в)

Разбор

Решение

Пусть число равно $100a + 10b + c$ , тогда сумма его цифр равна $a + b + c$ .

а) Да: у числа 117 сумма цифр 9, и $117 : 9 = 13$ .

б) Нет. Равенство $100a + 10b + c = 6(a + b + c)$ означает

94a + 4b = 5c.

Левая часть не меньше 94, так как $a \ge 1$ , а правая не больше 45.

в) Оценка. При $a = 6$ частное не меньше 70 тогда и только тогда, когда

\begin{aligned} 600 + 10b + c &\ge 70(6 + b + c), \\ 60b + 69c &\le 180. \end{aligned}

Это оставляет семь чисел: 600, 610, 620, 630, 601, 611, 602.

Число 600 кратно 100, а у остальных частные такие:

\begin{aligned} &610 : 7,\quad 620 : 8,\quad 630 : 9 = 70, \\ &601 : 7,\quad 611 : 8,\quad 602 : 8. \end{aligned}

Целое среди них только 70, поэтому большего натурального частного не бывает.

в) Пример. $630 : (6 + 3 + 0) = 70$ .

Ответ: а) да; б) нет; в) 70

По кругу расставлено $N$ различных натуральных чисел, каждое из которых не превосходит 425. Сумма любых четырёх идущих подряд чисел делится на 4, а сумма любых трёх идущих подряд чисел нечётна.

а) Может ли $N$ быть равным 280?
б) Может ли $N$ быть равным 149?
в) Найдите наибольшее значение $N$ .

ЕГЭ-2022, основная волна, Восток

в)

Разбор

Решение

Возьмём четыре подряд: $x_1, x_2, x_3, x_4$ .

Их сумма делится на 4 и потому чётна, а $x_1 + x_2 + x_3$ нечётна. Значит, $x_4$ нечётно.

Любое число на круге бывает четвёртым в такой четвёрке, поэтому нечётны все.

а) Нет. Нечётных чисел от 1 до 425 всего 213, а различных нужно 280.

Суммы $x_1 + \ldots + x_4$ и $x_2 + \ldots + x_5$ делятся на 4, поэтому

x_5 \equiv x_1 \pmod 4.

Каждая четвёрка подряд содержит одни и те же четыре остатка, и каждый из них равен 1 или 3.

Пусть единиц среди них $u$ . Тогда сумма остатков равна

u + 3(4 - u) = 12 - 2u

и делится на 4 только при $u = 0, 2, 4$ .

При $u = 0$ и при $u = 4$ все остатки одинаковы. Чисел с остатком 1 до 425 ровно 107, с остатком 3 — 106, поэтому $N \le 107$ .

При $u = 2$ чисел с остатком 3 ровно $N/2$ , значит, $N$ чётно и $N/2 \le 106$ .

б) Нет. Нечётное $N = 149$ возможно только при одинаковых остатках, а тогда $N \le 107$ .

в) Оценка. Из двух случаев остаётся $N \le \max(107, 212) = 212$ .

в) Пример. Числа $1, 3, 5, \ldots, 423$ по порядку, их 212.

Остатки чередуются 1, 3, 1, 3 и по кругу тоже, ведь 423 даёт остаток 3, а следующая за ним единица — остаток 1.

Любые три подряд нечётны, и сумма их нечётна. В любых четырёх подряд два остатка 1 и два остатка 3, а такая сумма делится на 4.

Ответ: а) нет; б) нет; в) 212

На доске записано 10 натуральных чисел, среди которых нет одинаковых. Оказалось, что среднее арифметическое любых трёх, четырёх, пяти или шести чисел из записанных является целым числом. Одно из записанных чисел равно 30 032.

а) Может ли среди записанных на доске чисел быть число 312?
б) Может ли отношение двух записанных на доске чисел равняться 6?
в) Отношение двух записанных на доске чисел является целым числом $n$ . Найдите наименьшее возможное значение $n$ .

ЕГЭ-2025, основная волна, Санкт-Петербург

в)

Разбор

Решение

Возьмём $x$ и $y$ и ещё $k - 1$ других, где $k$ равно 3, 4, 5 или 6.

Суммы этих других с $x$ и с $y$ делятся на $k$ , значит, на $k$ делится и разность:

x - y \;\vdots\; 3,\ 4,\ 5,\ 6 \;\Longrightarrow\; x - y \;\vdots\; 60.

Все числа дают при делении на 60 тот же остаток, что 30 032, — это 32.

Обратно, у чисел вида $60t + 32$ сумма $k$ штук равна «кратное 60 плюс $32k$ » и делится на $k$ .

а) Нет, 312 даёт остаток 12 при делении на 60.

б) Нет: если $x = 60t + 32$ , то $6x = 60(6t + 3) + 12$ даёт остаток 12.

в) Оценка. Пусть на доске стоят $x$ и $nx$ . Их разность делится на 60:

(n - 1)(60t + 32) \;\vdots\; 60 \;\Longrightarrow\; 32(n - 1) \;\vdots\; 60.

Сократив на 4, получаем, что $8(n - 1)$ делится на 15.

Числа 8 и 15 взаимно просты, поэтому $n - 1$ делится на 15. Числа различны, значит, $n \ne 1$ и $n \ge 16$ .

в) Пример. 32, 92, 152, 212, 272, 332, 392, 452, 512 и 30 032. Все дают остаток 32 при делении на 60, и $512 : 32 = 16$ .

Ответ: а) нет; б) нет; в) 16

На столе лежит $N$ монет по 2 рубля и $(800 - N)$ монет по 5 рублей ( $N$ — натуральное число от 1 до 799). Оказалось, что если взять любые 300 монет, то сумма денег, набранная этими монетами, будет не меньше четверти от общей суммы денег на столе.

а) Может ли $N$ равняться 200?
б) Может ли $N$ равняться 400?
в) Сколько различных значений может принимать число $N$ ?

ЕГЭ-2026, основная волна, Санкт-Петербург

в)

Разбор

Решение

Всего на столе

2N + 5(800 - N) = 4000 - 3N\ \text{рублей}.

Условие достаточно проверить для самых дешёвых 300 монет, ведь у любого другого набора сумма не меньше.

а) Да. При $N = 200$ самые дешёвые 300 монет — это 200 по 2 рубля и 100 по 5, всего 900 рублей.

Четверть общей суммы равна $3400 : 4 = 850$ , а $900 \ge 850$ — условие выполнено.

б) Нет. При $N = 400$ можно взять 300 двухрублёвых — это 600 рублей, а четверть общей суммы равна $2800 : 4 = 700$ .

в) Первый случай: $N \le 300$ . Самые дешёвые 300 монет стоят $2N + 5(300 - N) = 1500 - 3N$ , и условие принимает вид

\begin{aligned} 4(1500 - 3N) &\ge 4000 - 3N, \\ 9N &\le 2000. \end{aligned}

Отсюда $N \le 222$ — это 222 значения.

в) Второй случай: $N \ge 300$ . Самые дешёвые монеты стоят 600 рублей, и условие даёт

\begin{aligned} 4 \cdot 600 &\ge 4000 - 3N, \\ 3N &\ge 1600. \end{aligned}

Отсюда $N \ge 534$ — значения от 534 до 799, их 266.

Всего $222 + 266 = 488$ .

Ответ: а) да; б) нет; в) 488

Следующая статья серии — «Параметр как третья ось», задача 18, в которой параметр становится ещё одной осью, а число решений — числом точек пересечения графиков.

Чтобы назвать наибольшее значение, надо доказать, что больше не бывает, и показать набор, на котором оно достигается.

В Компендиуме разбираем задачи второй части ЕГЭ так, чтобы за ответом было видно рассуждение.

залетай в Академию→