Республиканская олимпиада по математике, 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

для нечетных n не нужно $\lfloor \dfrac{n}{2} \rfloor +1$, достаточно $\lfloor \dfrac{n}{2} \rfloor$. И еще а что если будет ничьи

P.S. мне не засчитали эту задачу я брал верхнюю часть и решил как в решения)

Про формулу $\lfloor n/2 \rfloor + 1$. Она абсолютно верна и для нечетных $n$. Если $n=3$, то $\lfloor 3/2 \rfloor + 1 = 2$. Это и есть минимальное целое число голосов для строгой победы (2 из 3). Если взять меньше (как ты предлагаешь, $\lfloor 3/2 \rfloor = 1$), то это будет проигрыш, а не победа. Формула универсальна для любого $n$.

Про ничьи: В задаче партия $A$ сама распределяет жителей. Ей невыгодно допускать ничьи, так как это не помогает ей выиграть больше округов, чем партия $B$. У $A$ есть ресурс всего на 11 побед ($x=11$). Чтобы $A$ победила на выборах, у $B$ должно быть строго меньше побед, то есть максимум $y=10$. Итого $11 + 10 = 21$.

Любая попытка добавить 22-й округ (даже ничейный) потребует либо забрать голоса у $A$, либо отдать победу $B$, что не увеличит итоговый результат $k$.

А что если у А выиграл 9 округов, В выиграл 8 округов и было 5 ничьи? Вы не доказали что такое невозможно

я хочу вы ответили на этот вопрос

типо если А выиграл х округов В х-1 и было у ничьи и нужно доказать у<11-x

А да та формула правильеа просто мне скащали что нет на апел

Рад слышать.