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

Қалада 2026 тұрғын бар. Сайлауда $A$ партиясына 41 тұрғын дауыс беруге дайын, ал қалған 1985 тұрғын $B$ партиясына дауыс береді. Қаланың барлық тұрғындары сайлаушылар болып табылады. $A$ партиясы барлық сайлаушыларды $k$ округке бөледі. Барлық округтердегі сайлаушылар саны әртүрлі болуы тиіс және әрбір округте кемінде бір тұрғын дауыс беруі керек. Округте қай партия қатаң көп дауыс алса, сол жеңеді (дауыс саны тең болса, тең нәтиже жарияланады). $A$ партиясы $B$ партиясынан қатаң көп округ ұтып, сайлауда жеңе алатындай ең үлкен $k$ мәнін табыңыз. ( Сарсенгали Д. )

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

Пусть $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

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

Рад слышать.