Олимпиада имени Леонарда Эйлера 2025-2026 учебный год, II тур заключительного этапа

Үстелде салмақтары әртүрлі 50 гір тұр. Олардан кез келген 24 гір алғанда, қалған гірлердің ішінен салмақтар қосындысы дәл сондай болатын бірнеше гірді таңдап ала алатындай жағдай туындай алады ма? ( С. Берлов )

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

Ответ: Не может.

Допустим может.

Распишем числа в порядке убывания: $a_1 > a_2 > \dots > a_{50}$.

Пусть $S_i = a_1 + a_2 + \dots + a_i$.

Рассмотрим 46 сумм всех чисел наборов из 24 чисел:

$A_1 = S_{24}$,

$A_2 = S_{23} + a_{25}$,

$A_3 = S_{23} + a_{26}$,

.

.

.

$A_{24} = S_{23} + a_{47}$,

$A_{25} = S_{22} + a_{24} + a_{47}$,

$A_{26} = S_{22} + a_{25} + a_{47}$,

.

.

.

$A_{46} = S_{22} + a_{45} + a_{47}$.

Назовем эти наборы «крутыми».

Заметим, что суммы идут в строгом порядке убывания (сверху вниз) и у всех крутых наборов при расстановке чисел в порядке возрастания, число на $i$-том месте будет больше числа на $i$-том месте среди оставшихся 26 чисел. Это значит, что для любого крутого набора и набора из менее чем 25 чисел из оставшихся 26, сумма чисел этого набора будет меньше суммы чисел крутого набора. Значит, суммы чисел крутых наборов могут быть представлены только в виде суммы 25 или 26 из оставшихся чисел.

Обозначим для каждого крутого набора один «классный» набор из $a_i$, в котором сумма его чисел равна сумме чисел крутого набора, и эти наборы непересекающиеся. Понятно, что классные наборы состоят из 25 или 26 $a_i$. Значит, есть ровно 1 $a_k$, который не входит в оба набора, где $22 < k \le 51$ (будем считать, что $k = 51$ в случае, когда все $a_i$ входят в какой-то набор, т.е. $a_{51} = 0$).

$$S_{50} - a_k = 2A_i$$

Здесь левая часть принимает не более 29 различных значений, а правая 46, противоречие.

Камбэк?