№20. Числа и их свойства

Ключевое наблюдение

Сначала переведём условие на язык делимости. Среднее арифметическое четырёх чисел целое — это то же самое, что сумма этих четырёх чисел делится на 4. Аналогично для семи и семёрки.

Все числа на доске дают одинаковый остаток при делении на 4. Докажем от противного. Пусть числа \(a\) и \(b\) дают разные остатки. Возьмём ещё какие-нибудь три числа \(c\), \(d\), \(e\) с доски — их хватит, чисел всего десять. Рассмотрим две четвёрки:

\[a,\ c,\ d,\ e \qquad\text{и}\qquad b,\ c,\ d,\]\[\ e.\]

Суммы обеих делятся на 4. Тогда и их разность делится на 4:

\[(a + c + d + e) - (b + c + d + e) = a - b.\]

Но если \(a - b\) делится на 4, то \(a\) и \(b\) дают одинаковые остатки при делении на 4 — противоречие.

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

Важно! Приём «вычесть две суммы с общей частью» — главный инструмент этой задачи. Общие слагаемые сокращаются, и остаётся разность ровно двух интересующих нас чисел.

Пункт а

Найдём остатки при делении на 4:

\[563 = 4\cdot 140 + 3,\]\[1417 = 4\cdot 354 + 1.\]

Остатки 3 и 1 разные, а по доказанному они обязаны совпадать.

Нет, не могут.

Пункт б

Раз на доске есть 563, то все числа дают остаток 3 при делении на 4. Посмотрим, какие остатки при делении на 4 вообще бывают у квадратов. Любое натуральное число даёт при делении на 4 остаток 0, 1, 2 или 3, поэтому достаточно проверить четыре случая:

\[0^2 = 0 \ \text{— остаток } 0,\]

\[1^2 = 1 \ \text{— остаток } 1,\]

\[2^2 = 4 \ \text{— остаток } 0,\]

\[3^2 = 9 \ \text{— остаток } 1.\]

Квадрат даёт при делении на 4 только остаток 0 или 1. Остатка 3 среди них нет.

Нет, не может.

Пункт в. Что требуется от числа \(n\)

На доске стоят 1 и \(n^2\), причём это разные числа, значит \(n \neq 1\). Число 1 даёт остаток 1 и при делении на 4, и при делении на 7. Следовательно, того же требуем от \(n^2\):

\[n^2 \equiv 1 \pmod 4 \qquad\text{и}\qquad n^2 \equiv 1 \pmod 7.\]

Из разбора в пункте б видно, что остаток 1 по модулю 4 квадрат даёт только тогда, когда само число нечётно. Поэтому перебираем только нечётные \(n\) и смотрим остаток при делении на 7.

\(n = 3\): \(n^2 = 9\), остаток 2

\(n = 5\): \(n^2 = 25\), остаток 4

\(n = 7\): \(n^2 = 49\), остаток 0

\(n = 9\): \(n^2 = 81\), остаток 4

\(n = 11\): \(n^2 = 121\), остаток 2

\(n = 13\): \(n^2 = 169\), остаток 1 — подходит

Первое подходящее значение — \(n = 13\).

Пункт в. Пример

Осталось показать, что при \(n = 13\) доска действительно может существовать. Нужно десять различных натуральных чисел, дающих остаток 1 и по модулю 4, и по модулю 7, среди которых есть 1 и \(169 = 13^2\).

Числа, дающие остаток 1 сразу по двум модулям, — это числа вида \(28k + 1\), ведь \(4\cdot 7 = 28\). Возьмём первые десять:

\[1,\ 29,\ 57,\ 85,\ 113,\ 141,\]\[\ 169,\ 197,\ 225,\ 253.\]

Проверим условие. Каждое число даёт остаток 1 при делении на 4, поэтому сумма любых четырёх даёт остаток \(1+1+1+1 = 4\), то есть делится на 4. Точно так же сумма любых семи даёт остаток \(7\cdot 1 = 7\) при делении на 7, то есть делится на 7. Оба средних арифметических целые, число \(169 = 13^2\) на доске есть.

Ответ: а) нет, не могут;   б) нет, не может;   в) 13.

Обозначения

Пусть \(a\) детей потратили по 30 рублей, а \(b\) детей — по 140 рублей. Всего детей \(n\), поэтому \(a + b = n\).

Важно! В условии сказано, что не все дети потратили поровну. Это значит, что обе группы непусты: \(a \geqslant 1\) и \(b \geqslant 1\). Без этого замечания в пунктах б и в получатся неверные ответы.

Пункт а

Если каждый из \(n\) аттракционов получил по 80 рублей, то вся выручка парка равна \(80n\). С другой стороны, эта же выручка — это все потраченные детьми деньги:

\[80n = 30a + 140b.\]

Подставим \(a = n - b\) и упростим. Разделим обе части на 10:

\[8n = 3a + 14b = 3(n - b) + 14b = 3n + 11b,\]

\[5n = 11b.\]

Подойдёт \(n = 11\) и \(b = 5\), тогда \(a = 6\). Проверим: дети потратили

\[6\cdot 30 + 5\cdot 140 = 180 + 700 = 880\ \text{рублей},\]

и на 11 аттракционов это даёт ровно по 80 рублей. Осталось убедиться, что такое распределение возможно: 880 рублей — это 88 посещений по 10 рублей, а 88 посещений делятся на 11 аттракционов по 8 посещений. Один аттракцион можно посещать много раз, поэтому препятствий нет.

Да, может.

Пункт б

Пусть каждый аттракцион посетили \(x\) раз, тогда его выручка равна \(10x\) рублей, а выручка всего парка — \(10xn\) рублей. Как и выше,

\[10xn = 30a + 140b, \qquad xn = 3n + 11b.\]

Посмотрим на это равенство с точки зрения делимости на \(n\). Слева \(xn\) делится на \(n\). Справа \(3n\) тоже делится на \(n\). Значит и \(11b\) обязано делиться на \(n\).

По условию \(1 \leqslant b \leqslant n-1\), то есть само \(b\) на \(n\) не делится. Разберём, что это даёт.

Если бы числа \(n\) и 11 были взаимно просты, то из делимости \(11b\) на \(n\) следовало бы, что на \(n\) делится \(b\) — а это невозможно. Значит \(n\) и 11 не взаимно просты. Но 11 — простое число, поэтому единственный вариант: \(n\) делится на 11.

Наименьшее такое количество детей — \(n = 11\), и пример для него уже построен в пункте а).

Ответ пункта б: 11.

Пункт в. Оценка сверху

Оценим выручку парка с двух сторон.

Снизу. Выручки всех \(n\) аттракционов различны и кратны 10 (каждое посещение стоит 10 рублей), причём могут быть нулевыми. Наименьшая возможная сумма получится, если выручки равны \(0,\ 10,\ 20,\ \ldots,\ 10(n-1)\). Это арифметическая прогрессия, её сумма равна

\[\frac{0 + 10(n-1)}{2}\cdot n = 5n(n-1).\]

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

\[30a + 140b \leqslant 140(n-1) + 30 = 140n - 110.\]

Соединяем обе оценки:

\[5n(n-1) \leqslant 140n - 110.\]

Раскрываем и делим на 5:

\[5n^2 - 5n \leqslant 140n - 110, \qquad 5n^2 - 145n + 110 \leqslant 0, \qquad n^2 - 29n + 22 \leqslant 0.\]

Дискриминант \(D = 841 - 88 = 753\), и больший корень равен \(\dfrac{29 + \sqrt{753}}{2}\). Оценим его: \(\sqrt{753} < \sqrt{784} = 28\), поэтому

\[n \leqslant \frac{29 + \sqrt{753}}{2} < \frac{29 + 28}{2} = 28{,}5.\]

Число \(n\) целое, значит \(n \leqslant 28\).

Пункт в. Пример на 28 детей

Из оценки видно, что запас совсем небольшой, поэтому берём самый выгодный вариант: 27 детей тратят по 140 рублей и один ребёнок — 30 рублей. Всего

\[27\cdot 140 + 30 = 3780 + 30 = 3810\ \text{рублей},\]

то есть \(381\) посещение.

Нам нужно 28 различных выручек. Самый экономный набор \(0, 10, \ldots, 270\) даёт \(0+1+\ldots+27 = 378\) посещений — на 3 меньше, чем есть. Значит последнюю выручку увеличиваем на 3 посещения: вместо 270 рублей берём 300.

Итоговые выручки: \(0,\ 10,\ 20,\ \ldots,\ 260,\ 300\) рублей. Все они различны, все кратны 10, а их сумма равна \(3810\) рублей — ровно столько потратили дети.

Ответ: а) да, может;   б) 11;   в) 28.

Сколько чисел может быть на доске

Это понадобится во всех пунктах, поэтому разберёмся сразу. Кратные 15 идут через каждые 15 чисел. Если их ровно пять, то набор обязательно накрывает пять таких чисел и не накрывает шестое.

Самый короткий набор. Он начинается кратным 15 и им же заканчивается: между первым и пятым кратным ровно \(4\cdot 15 = 60\) шагов, а чисел на одно больше:

\[4\cdot 15 + 1 = 61.\]

Самый длинный набор. Слева можно добавить ещё 14 чисел (до следующего кратного 15 не дотянув) и справа тоже 14:

\[61 + 14 + 14 = 89.\]

Значит на доске от 61 до 89 чисел.

Пункт а

Достаточно привести пример. Возьмём все числа от 16 до 96 включительно.

Кратных 15 среди них ровно пять: \(30,\ 45,\ 60,\ 75,\ 90\). Кратных 16 — шесть: \(16,\ 32,\ 48,\ 64,\ 80,\ 96\).

Да, могло.

Пункт б

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

Кратные 11 идут через каждые 11 чисел. Разобьём 61 подряд идущее число на группы по 11: получится \(61 = 5\cdot 11 + 6\), то есть пять полных групп и остаток. В каждой полной группе из 11 подряд идущих чисел ровно одно кратно 11. Значит кратных 11 не меньше пяти.

Важно! Здесь легко ошибиться и решить, что кратных может быть меньше, если «неудачно» расположить набор. Но в любых 11 подряд идущих числах кратное 11 есть всегда — как бы набор ни сдвигали. Именно поэтому оценка не зависит от расположения.

Итак, кратных 11 всегда не меньше пяти, меньше быть не может.

Нет, не могло.

Пункт в. Оценка сверху

Из пункта а) уже видно, что \(k = 16\) подходит. Проверим, годится ли \(k = 17\), и покажем, что \(k \geqslant 18\) уже нет.

Случай \(k \geqslant 18\). Чтобы среди подряд идущих чисел нашлось шесть кратных \(k\), набор должен быть достаточно длинным. Самый короткий такой набор начинается кратным \(k\) и им же заканчивается, в нём

\[5k + 1 \geqslant 5\cdot 18 + 1 = 91\ \text{число}.\]

Но мы выяснили, что на доске не больше 89 чисел. Противоречие: такой длинный набор не может содержать ровно пять кратных 15.

Важно! Обратите внимание на логику: мы не проверяли каждое \(k\) по отдельности. Оценка длины набора сверху (не больше 89) сразу отсекает все \(k \geqslant 18\) одним ударом.

Пункт в. Пример для \(k = 17\)

Возьмём числа от 16 до 104 включительно — это 89 чисел, то есть ровно максимально возможная длина.

Кратных 15 здесь ровно пять: \(30,\ 45,\ 60,\ 75,\ 90\). Кратных 17 — шесть: \(17,\ 34,\ 51,\ 68,\ 85,\ 102\). Условие выполнено, и шесть чисел делятся на 17.

Ответ: а) да, могло;   б) нет, не могло;   в) 17.

Что означает условие

Условие «никакие два не имеют общего делителя, большего 1» означает, что числа попарно взаимно просты. Из этого сразу следует важное наблюдение: среди наших чисел не может быть двух чётных — у любых двух чётных чисел есть общий делитель 2. Точно так же не может быть двух чисел, кратных 3, двух кратных 5 и так далее для любого простого числа.

Единица взаимно проста с любым числом, поэтому её брать в набор всегда можно и выгодно.

Пункт а

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

\[1 + 2 + 3 + 5 + 7 + 11 + 13 + 23 = 65.\]

Да, может.

Пункт б

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

Случай 1: чётное число есть. Тогда остальные семь чисел нечётны. Сумма семи нечётных чисел нечётна, а прибавление чётного числа чётность не меняет, поэтому вся сумма нечётна. Но 62 чётно — не подходит.

Случай 2: чётного числа нет. Тогда все восемь чисел нечётны и различны. Самая маленькая сумма получится на восьми наименьших нечётных числах:

\[1+3+5+7+9+11+13+15 = 64 > 62.\]

Значит любая сумма в этом случае больше 62. (Заметим, что сам этот набор условию даже не удовлетворяет — числа 3, 9 и 15 кратны трём. Но нам и не нужно, чтобы он подходил: он даёт оценку снизу, и её уже достаточно.)

Ни в одном из случаев сумма 62 невозможна.

Нет, не может.

Пункт в. Какими должны быть три первых числа

Расположим числа по возрастанию: \(a_1 < a_2 < \ldots < a_8\). Будем последовательно показывать, что для наименьшей суммы набор обязан начинаться с 1, 2, 3.

Единица. Если её в наборе нет, заменим наибольшее число на 1 — взаимная простота сохранится, ведь единица взаимно проста со всем, а сумма уменьшится. Значит \(a_1 = 1\).

Двойка. Чётное число в наборе может быть только одно. Если чётного числа нет, заменим наибольшее из чисел на 2 и уменьшим сумму. Если чётное число есть, но больше 2, заменим его на 2 — других чётных в наборе нет, поэтому конфликта не возникнет, а сумма уменьшится. Значит \(a_2 = 2\).

Тройка. Рассуждение то же: кратное трём может быть только одно, и если его нет или оно больше 3, заменяем на 3 и уменьшаем сумму. Значит \(a_3 = 3\).

Пункт в. Остальные пять чисел

Двойка и тройка уже заняты, поэтому больше нельзя брать ни чётные числа, ни кратные трём. Выпишем, какие числа остаются, начиная с 4:

4 — чётное, нельзя. 5 — можно. 6 — чётное, нельзя. 7 — можно. 8 — чётное. 9 — кратно 3. 10 — чётное. 11 — можно. 12 — чётное. 13 — можно. 14 — чётное. 15 — кратно 3. 16 — чётное. 17 — можно.

Значит \(a_4 \geqslant 5\), \(a_5 \geqslant 7\), \(a_6 \geqslant 11\), \(a_7 \geqslant 13\), \(a_8 \geqslant 17\), и сумма не меньше

\[1 + 2 + 3 + 5 + 7 + 11 + 13 + 17 = 59.\]

Осталось убедиться, что этот набор годится. Числа 1, 2, 3, 5, 7, 11, 13, 17 — это единица и семь различных простых чисел, они попарно взаимно просты. Оценка достигается.

Ответ: а) да, может;   б) нет, не может;   в) 59.

Пункт а

Достаточно привести пример. Возьмём числа 2034 и 9:

\[2034 + 9 = 2043,\]

а суммы цифр равны: \(2+0+3+4 = 9\) и \(9\). Числа различны, оба натуральные.

Да, можно.

Пункт б

Предположим, что такие числа \(A\) и \(B\) существуют: \(A + B = 599\), и суммы их цифр равны. Сложим их в столбик и посмотрим на разряды справа налево. Если одно из чисел короче, будем считать, что в старших разрядах у него стоят нули.

Разряд единиц. Сумма последних цифр должна заканчиваться на 9. Но сумма двух цифр не превосходит \(9+9 = 18\), а единственное число, не превосходящее 18 и заканчивающееся на 9, — это само 9. Значит сумма цифр единиц равна ровно 9, и переноса в следующий разряд нет.

Разряд десятков. Переноса не было, поэтому здесь та же логика: сумма цифр десятков заканчивается на 9, не превосходит 18, значит равна 9. Переноса снова нет.

Разряд сотен. Переноса нет, поэтому сумма цифр сотен равна 5.

Теперь сложим все цифры обоих чисел. Мы разобрали три разряда, и в каждом знаем сумму:

\[5 + 9 + 9 = 23.\]

Это сумма цифр числа \(A\) плюс сумма цифр числа \(B\). Но по условию эти две суммы равны, значит их общая сумма чётна. А 23 нечётно. Противоречие.

Нет, нельзя.

Пункт в. Оценка снизу

Пусть искомые числа \(x_1 < x_2 < \ldots < x_7\). Воспользуемся тем же признаком, что и в пункте б, но для девятки: число даёт при делении на 9 тот же остаток, что и сумма его цифр. Причина та же: \(10 \equiv 1 \pmod 9\), значит и \(100 \equiv 1\), и \(1000 \equiv 1\), и каждый разряд вносит в остаток ровно свою цифру.

Суммы цифр у наших чисел равны, поэтому равны и их остатки при делении на 9. Но числа различны, а два числа с одинаковым остатком отличаются на кратное девяти. Значит соседние числа отличаются не меньше чем на 9:

\[x_2 \geqslant x_1 + 9,\quad x_3 \geqslant x_1 + 18,\]\[\ldots,\quad x_7 \geqslant x_1 + 54.\]

Складываем все семь неравенств:

\[x_1 + x_2 + \ldots + x_7 \geqslant 7x_1 + (9 + 18 + \ldots + 54) = 7x_1 + 189.\]

Здесь \(9 + 18 + \ldots + 54 = 9(1+2+\ldots+6) = 9\cdot 21 = 189\).

Пункт в. Перебор

Заметим, что если сумма цифр равна \(d\) и \(d \leqslant 9\), то самое маленькое число с такой суммой цифр — это само \(d\). Поэтому перебирать сумму цифр — то же самое, что перебирать наименьшее число \(x_1\).

Для каждого значения \(x_1\) берём семь наименьших чисел с суммой цифр \(x_1\) и складываем.

\(x_1 = 1\): числа 1, 10, 100, 1000, 10 000, 100 000, 1 000 000 — их сумма 1 111 111.

\(x_1 = 2\): числа 2, 11, 20, 101, 110, 200, 1001 — их сумма 1445.

\(x_1 = 3\): числа 3, 12, 21, 30, 102, 111, 120 — их сумма 399.

\(x_1 = 4\): числа 4, 13, 22, 31, 40, 103, 112 — их сумма 325.

\(x_1 = 5\): числа 5, 14, 23, 32, 41, 50, 104 — их сумма 269.

\(x_1 = 6\): числа 6, 15, 24, 33, 42, 51, 60 — их сумма 231.

Случай \(x_1 \geqslant 7\) разбирать по отдельности не нужно — его закрывает оценка снизу:

\[x_1 + \ldots + x_7 \geqslant 7x_1 + 189 \geqslant 7\cdot 7 + 189 = 238 > 231.\]

Значит наименьшая возможная сумма равна 231, и достигается она на наборе

\[6,\ 15,\ 24,\ 33,\ 42,\ 51,\ 60.\]

Проверим: суммы цифр у всех семи чисел равны 6, числа различны, а их сумма равна 231.

Ответ: а) да, можно;   б) нет, нельзя;   в) 231.

Ключевое соображение

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

Правая часть неравенства — четверть общей суммы всех монет на столе — от выбора набора вообще не зависит, это фиксированное число. Меняется только левая часть, то есть сумма выбранных 300 монет. Значит труднее всего выполнить условие тогда, когда эта сумма наименьшая.

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

Общая сумма всех монет равна

\[5N + 2(1000 - N) = 2000 + 3N.\]

Пункт а

При \(N = 100\) двухрублёвых монет \(900\) — их больше 300, поэтому самый бедный набор состоит только из двоек:

\[300\cdot 2 = 600,\]\[\frac{2000 + 3\cdot 100}{4} = \frac{2300}{4}\]\[= 575.\]

Так как \(600 \geqslant 575\), условие выполнено. Да, может.

Пункт б

При \(N = 500\) двухрублёвых тоже \(500\), то есть больше 300, и снова берём 300 двоек:

\[300\cdot 2 = 600,\]\[\frac{2000 + 3\cdot 500}{4} = \frac{3500}{4}\]\[= 875.\]

Получилось \(600 < 875\) — нашёлся набор, нарушающий условие. Нет, не может.

Пункт в

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

Случай 1: \(1000 - N \geqslant 300\), то есть \(N \leqslant 700\). Самый бедный набор — 300 двоек:

\[600 \geqslant \frac{2000 + 3N}{4},\]\[2400 \geqslant 2000 + 3N,\quad 3N \leqslant 400,\]

откуда \(N \leqslant 133\frac{1}{3}\), то есть \(N \leqslant 133\). Подходят все \(N\) от 1 до 133 — это 133 значения.

Случай 2: \(1000 - N < 300\), то есть \(N > 700\). Теперь двухрублёвых монет на столе меньше 300, и набрать 300 монет из одних двоек уже не получится. Самый бедный набор устроен так: берём все двухрублёвые монеты, сколько их есть, а недостающие добираем пятирублёвыми.

Двоек всего \(1000 - N\) штук. Значит пятёрок придётся взять

\[300 - (1000 - N) = N - 700.\]

Сумма такого набора и должна быть не меньше четверти общей суммы:

\[2(1000 - N) + 5(N - 700) \geqslant\]

\[\geqslant \frac{2000 + 3N}{4}.\]

Слева \(2000 - 2N + 5N - 3500 = 3N - 1500\). Умножаем неравенство на 4:

\[12N - 6000 \geqslant 2000 + 3N,\]\[9N \geqslant 8000,\quad N \geqslant 888\frac{8}{9},\]

то есть \(N \geqslant 889\). Подходят все \(N\) от 889 до 999 — это \(999 - 889 + 1 = 111\) значений.

Всего

\[133 + 111 = 244.\]

Ответ: а) да;   б) нет;   в) 244.