40-я Балканская математическая олимпиада. Анталья, 2023 год

Найдите наибольшее целое число $k \leq 2023$, для которого верно следующее свойство: как 6ы Алиса не раскрасила ровно $k$ чисел из множества $\{1,2, \ldots, 2023\}$ в красный цвет, Бо6 сможет покрасить в синий цвет некоторые из оставшихся, непокрашенных чисел таким образом, что сумма всех чисел, покрашенных в красный цвет окажется равной сумме всех чисел, покрашенных в синий цвет.

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

Если $k$ слишком велико, Алиса может раскрасить $k$ самых больших чисел в наборе, и Боб не сможет повторить сумму, даже если он выберет все оставшиеся числа. Итак, это первое ограничение.

Сумма крупнейших $k$ чисел равна (при $n=2023$) $kn - k(k-1)/2$.

Сумма первых $n-k$ чисел равна $(n-k)(n-k+1)/2$.

Собрав ограничение вместе, мы должны иметь:

$$k^2 - (2n+1)k + \frac{n(n+1)}{2} \geq 0$$ Пусть $n=2023$ имеем:

$$k < \frac{4047 - \sqrt{2023^2 + 2024^2}}{2}$$ Рассчитано с помощью калькулятора, это означает $k <= 592$, хотя я не уверен, как бы я это получил. номер в конкурсе. Теперь нам нужно показать, что для этого $k$ Боб действительно может воспроизвести любую сумму, которую выберет Алиса. Я не сделал эту часть.