Республиканская олимпиада по математике, 2026 год, 9 класс

В городе 2026 жителей. На выборах за партию $A$ готовы голосовать 41 житель, а остальные 1985 жителей — за партию $B$. Все жители города являются избирателями на выборах. Партия $A$ распределяет всех избирателей по $k$ округам. Все округа должны иметь разное количество избирателей и в каждом округе должен голосовать хотя бы один житель. В округе побеждает та партия, которая набрала строго больше голосов (при равенстве голосов объявляется ничья). При каком наибольшем $k$ партия $A$ сможет победить на выборах, выиграв строго больше округов, чем партия $B$? ( Сарсенгали Д. )

Комментарий/решение

Пусть $k$ это количество округов. Пусть $n_1 < n_2 < \dots < n_k$ это количество жителей в них. Сумма всех жителей $S = \sum_{i=1}^{k} n_i \ge \frac{k(k+1)}{2}$. По условию $S = 2026$ значит $k \le 63$.

Пусть $x$ это количество округов где победила партия $A$ а $y$ это количество округов где победила партия $B$. Условие победы партии $A$ это $x > y$. Чтобы $k$ было максимальным выгодно взять $x = y + 1$ и $x + y = k$. Тогда $k = 2x - 1$.

В округе размером $n$ для победы партии $A$ нужно $v(n) = \lfloor \frac{n}{2} \rfloor + 1$ голосов. Чтобы сэкономить 41 голос партия $A$ должна выигрывать в самых маленьких округах с размерами $1, 2, 3, \dots, x$.

Суммарные затраты голосов $V$ для $x$ побед:

$V = \sum_{i=1}^{x} (\lfloor \frac{i}{2} \rfloor + 1)$

Распишем сумму для разных $x$:

Если $x = 11$ то $V = 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 = 41$

Если $x = 12$ то $V = 41 + 7 = 48$ это больше чем 41 голос.

Значит максимум побед у партии $A$ это $x = 11$. Чтобы $A$ победила на выборах нужно $y \le 10$. Тогда общее число округов $k = x + y = 11 + 10 = 21$.

При $k = 21$ сумма жителей в первых 21 округах $\frac{21 \cdot 22}{2} = 231$ это меньше 2026. Остаток жителей можно добавить в последний округ. Условие разных размеров будет соблюдено.

Ответ: 21