Числа и их свойства

Оцениваем минимальную сумму набора

Обозначим числа на доске $x_1 < x_2 < \dots < x_{100}$. Все они натуральные и различные, значит $x_k \geqslant k$ для любого $k$. Минимальная сумма ста различных натуральных чисел: $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$. Значит, $x_1 + x_2 + \dots + x_{100} \geqslant 5050$. По условию сумма равна $5120$, то есть запас над минимумом составляет $5120 - 5050 = 70$.

Пункт а: ищем противоречие для числа 230

Проверим, можно ли включить число $230$ в набор. Пусть одно из чисел равно $230$. Тогда сумма остальных $99$ чисел равна $5120 - 230 = 4890$. Эти $99$ чисел - натуральные, различные, и среди них нет $230$. Их минимальная возможная сумма (если взять $1, 2, \dots, 99$) равна $\dfrac{99 \cdot 100}{2} = 4950$. Но $4950 > 4890$. Противоречие: сумма $99$ чисел не может быть меньше $4950$. Ответ: нет.

Пункт б: оцениваем сумму без числа 14

Пусть числа $14$ на доске нет. Тогда все $100$ чисел - различные натуральные, не равные $14$. Оценим минимальную сумму такого набора. Если исключить $14$ и взять наименьшие: $1, 2, \dots, 13, 15, 16, \dots, 101$. Сумма: $(1 + 2 + \dots + 101) - 14 - 102 + 102 = \dfrac{101 \cdot 102}{2} - 14$. Посчитаем иначе: сумма $\{1, \dots, 101\}$ без $14$ равна $\dfrac{101 \cdot 102}{2} - 14 = 5151 - 14 = 5137$. Итак, если $14$ отсутствует, то сумма всех чисел не меньше $5137$. Но по условию сумма равна $5120 < 5137$. Противоречие. Ответ: нет.

Пункт в: строим замены и считаем их цену

Минимальная сумма $1 + 2 + \dots + 100 = 5050$ достигается на наборе $\{1, 2, \dots, 100\}$. В нём кратные $14$ - это $14, 28, 42, 56, 70, 84, 98$. Всего $7$ штук. Мы хотим уменьшить количество кратных $14$. Для этого нужно заменить кратное $14$ на некратное. Но любая замена увеличивает сумму - нужно доплатить за разницу.

Пусть мы убираем из набора число вида $14m$ (кратное $14$) и заменяем его на число $y$, не кратное $14$ и не входящее в набор. Минимальный выигрыш (наименьшее $y$, превышающее хоть что-то в наборе) такой: заменить самое большое кратное $14$, то есть $98$, на первое свободное число $101$ - это даёт прирост суммы $101 - 98 = 3$. Следующую замену сделать сложнее: $84 \to 102$ даёт $+18$ и так далее.

Посмотрим, сколько всего лишней суммы мы можем позволить: $5120 - 5050 = 70$.

Перебор замен (заменяем кратные $14$ на следующие по величине свободные числа):

• Заменить $98 \to 101$: $+3$, всего $+3$ (кратных стало $6$).

• Заменить $84 \to 102$: $+18$, всего $+21$ (кратных стало $5$).

• Заменить $70 \to 103$: $+33$, всего $+54$ (кратных стало $4$).

• Заменить $56 \to 104$: $+48$, всего $+102 > 70$. Не умещается.

Пункт в: предъявляем пример и завершаем оценку

После трёх замен на доске остаются кратные $14$: это $14, 28, 42, 56$ - всего $4$ штуки. Прирост суммы $54 \leqslant 70$, остаток $70 - 54 = 16$ распределим другой заменой, не трогающей кратные $14$: $100 \to 116$ даёт $+16$, причём $116$ не кратно $14$.

Получаем пример: берём $\{1, 2, \dots, 100\}$, удаляем $\{70, 84, 98, 100\}$, добавляем $\{101, 102, 103, 116\}$. Сумма: $5050 - 70 - 84 - 98 - 100 + 101 + 102 + 103 + 116 = 5120$. Кратных $14$ ровно $4$: числа $14, 28, 42, 56$.

Оценка: чтобы кратных $14$ было $\leqslant 3$, нужно сделать четвёртую замену, а она стоит уже $48$, и суммарный прирост превысит $70$. Значит, меньше $4$ кратных $14$ быть не может.

Формализуем условие

Упорядочим числа по возрастанию: $x_1 < x_2 < \dots < x_8$. Из условия:

Сумма всех чисел: $S = 36 + x_4 + x_5 + 135 = 171 + x_4 + x_5$.

Пункт а: проверяем сумму 190

Проверим, возможно ли $S = 190$, то есть $x_4 + x_5 = 19$. Так как числа различные натуральные и идут по возрастанию, то $x_3 \geqslant 3$. Но сумма первой тройки равна $36$: если $x_3 \leqslant 12$, то $x_1 + x_2 + x_3 \leqslant 10 + 11 + 12 = 33 < 36$. Противоречие. Значит, $x_3 \geqslant 13$. Тогда $x_4 \geqslant 14$, $x_5 \geqslant 15$, и $x_4 + x_5 \geqslant 29$. Но мы хотели $x_4 + x_5 = 19$, а получили $x_4 + x_5 \geqslant 29 > 19$. Противоречие. Ответ: нет.

Пункт б: проверяем, может ли шестое число равняться 45

Пусть $x_6 = 45$. Так как числа различные натуральные и возрастают, то $x_7 \geqslant 46$, $x_8 \geqslant 47$. Тогда $x_6 + x_7 + x_8 \geqslant 45 + 46 + 47 = 138$. Но по условию $x_6 + x_7 + x_8 = 135$, а мы получили $\geqslant 138$. Значит, $135 \geqslant 138$ - противоречие. Ответ: нет.

Пункт в: строим оценку сверху

Нужно максимизировать $S = 171 + x_4 + x_5$, то есть сделать $x_4$ и $x_5$ как можно больше. Из строгой возрастающей цепочки $x_5 < x_6 < x_7 < x_8$: чтобы увеличить $x_5$, нужно увеличить $x_6$. Сумма $x_6 + x_7 + x_8 = 135$ при $x_7 \geqslant x_6 + 1$, $x_8 \geqslant x_6 + 2$ даёт:

Значит, $x_6 \leqslant 44$, $x_5 \leqslant 43$, $x_4 \leqslant 42$. Оценка суммы: $S \leqslant 171 + 42 + 43 = 256$.

Пункт в: предъявляем пример

Нужно подобрать первую тройку с суммой $36$ и $x_3 < x_4 = 42$. Подходит $1, 2, 33$. Полный набор: $1, 2, 33, 42, 43, 44, 45, 46$. Проверка: числа различные натуральные, возрастают. $44 + 45 + 46 = 135$ (среднее $45$). $1 + 2 + 33 = 36$ (среднее $12$). Сумма всех: $1 + 2 + 33 + 42 + 43 + 44 + 45 + 46 = 256$.