Наименьшее значение x

Разбор задачи

Имеется набор гирь массами

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

Обозначим:

• $S$ — сумма всех «известных» гирь (без $x$): $$S = 1+3+5+\dots+25 + 27 + 225.$$
• Подсчитаем отдельно сумму нечётных чисел от $1$ до $25$. Известно, что $$1 + 3 + 5 + \dots + 25 = 13^2 = 169,$$ а добавляя $27$ и $225$, получаем $$S = 169 + 27 + 225 = 169 + 252 = 421.$$
• Общая сумма всех гирь вместе с $x$ равна $421 + x$. Для равновесия необходимо разбить весь набор на две группы (две чаши) с одинаковой суммой, то есть каждая чаша должна иметь суммарный вес $$\frac{421 + x}{2}.$$ Отсюда сразу видно, что $421 + x$ должно быть чётным, то есть $x$ должен быть нечётным (ведь $421$ — число нечётное).

Почему часто сводят задачу к поиску «разности»?

Если мы возьмём какую-то подпользу (подмножество) гирь массой $s$, то оставшиеся гири (из известного набора без $x$) дадут суммарно $421 - s$. Разность масс этих двух групп будет

• Если $\Delta > 0$, то первая группа тяжелее на $\Delta$.
• Чтобы уравнять весы, нужно «добросить» в более лёгкую чашу гирю массой $\Delta$ (то есть $x = \Delta$).

Мы ищем минимально возможную положительную $\Delta$, которую можно получить как $2s - 421$.

Главная тонкость: в наборе есть очень тяжёлая гиря 225 г. Посмотрим, какие суммы вообще достижимы:

1. Если не включать 225 в рассматриваемую подпользу, то максимум, что мы можем набрать из остальных ( $1,3,5,\dots,25,27$ ) — это $196$ граммов (поскольку $169 + 27 = 196$). Но тогда

   $$s \le 196 \quad \Longrightarrow\quad 2s \le 392,\quad 2s - 421 \le 392 - 421 = -29.$$

   То есть разность будет либо нулевой/отрицательной, либо меньше 29 по модулю, но не положительной (точнее, равенство «по модулю 29» указывает, что мы не можем так получить положительную $\Delta$).

2. Если включать 225, то сумма подпользы $s$ будет $\ge 225$. Тогда

   $$s \ge 225 \quad\Longrightarrow\quad 2s \ge 450, \quad 2s - 421 \ge 450 - 421 = 29.$$

   Следовательно, минимальная положительная $\Delta$, которую вообще можно получить, — это $29$.

Быстрее всего эта $\Delta = 29$ достигается «очевидным» разбиением:

• Одна чаша: гиря 225 г (сумма $=225$).
• Другая чаша: все остальные «известные» гири $\{1,3,5,\dots,25,27\}$ (сумма $=196$).

Разность между чашами выходит:

Чтобы «дотянуть» вторую чашу до 225, надо добавить гирю массы $x = 29$.

Вывод: наименьшее $x$, с которым можно уравновесить весы, равно

Анализ условия

Нам даны числа от $1$ до $4500$, каждое из которых покрашено либо в красный, либо в синий цвет. Условие окраски таково:

Если сумма двух различных чисел $a$ и $b$ является простым числом, то $a$ и $b$ должны быть покрашены в разные цвета.

Дополнительно известно, что число $1$ — красное. Требуется найти, сколько в итоге окажется синих чисел.

Шаг 1. Проверка небольшой выборки

Проверим первые несколько чисел вручную, пользуясь условием:

1. $1$ – красное (задано).
2. Рассмотрим $2$:
   • $1 + 2 = 3$ (простое), значит $1$ и $2$ — разные цвета.
     Так как $1$ красное, то $2$ — синее.
3. Рассмотрим $3$:
   • $1 + 3 = 4$ (не простое) — нет ограничения.
   • $2 + 3 = 5$ (простое), значит $2$ и $3$ — разные цвета.
     $2$ у нас синее, значит $3$ — красное.
4. Рассмотрим $4$:
   • $1 + 4 = 5$ (простое), значит $1$ и $4$ — разные цвета.
     $1$ — красное, значит $4$ — синее.
   • (Дополнительно можно проверить $3 + 4 = 7$ — тоже простое, и действительно $3$ красное, $4$ синее.)

Если проделать подобные проверки дальше, легко заметить закономерность:

• Любое нечётное число $n$ при сложении с каким-нибудь уже покрашенным чётным числом может дать простое.
• Любое простое число, кроме $2$, — нечётное. Следовательно, чтобы сумма $a + b$ была нечётным простым, одно из чисел почти всегда должно быть чётным, а другое — нечётным.
• Единственное чётное простое — это $2$, но сумма «двух различных положительных чисел = 2» невозможна (так как это требовало бы $a = 1$ и $b = 1$, что не «два различных»).

Иными словами, каждый раз, когда сумма $a + b$ оказывается простым числом больше 2, мы имеем (чётное $+$ нечётное) $\to$ разный цвет. Это наводит на гипотезу:

Все нечётные числа идут в один цвет, а все чётные — в другой.

Раз условие задачи ещё и зафиксировало, что $1$ (нечётное) — красное, то получается:

• Все нечётные числа $= \text{красные}$.
• Все чётные числа $= \text{синие}$.

Шаг 2. Проверка корректности гипотезы

1. $1$ — красное, по условию.
2. Если $m$ чётное и $n$ нечётное, то $m + n$ — нечётное. Если оно простое, то условие задачи требует разных цветов для $m$ и $n$. Действительно, по нашей раскраске $m$ (чётное) синее, $n$ (нечётное) красное, то есть цвета разные — всё выполняется.
3. Если $m$ и $n$ оба чётные, их сумма — чётная. Простейшее чётное простое — это 2, но сумма двух разных чётных чисел $\ge 2 + 4 = 6$. То есть либо это не простое (6, 8, 10 и т. д.), либо $2$ вообще не достигается, поскольку нет пары «два разных числа», которые бы давали $2$. Таким образом, никакого противоречия нет.
4. Если $m$ и $n$ оба нечётные, их сумма — чётная ($\ge 2 + 3 = 5$, но 5 — это нечётное число, значит у нас хотя бы один из них должен быть чётным, чтобы получить 5). В итоге пара «оба нечётные» тоже не приводит к простому числу-тройке и т. п. Так что тут ограничений нет.

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

Шаг 3. Подсчёт синих чисел

Вся «чётная половина» из диапазона $1,2,\dots,4500$ будет синей. Сколько чётных чисел от 1 до 4500?

• Чётные — это $2,4,6,\dots,4500$.
• Общее число таких элементов: $$\frac{4500}{2} = 2250.$$

Следовательно, синих чисел ровно $2250$.

Ответ