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