Международная олимпиада 2021, Санкт-Петербург, Россия, 2021 год

Дано целое число $m > 2.$ В конечном множестве $A$, состоящем из (не обязательно положительных) целых чисел, нашлись такие подмножества $B_1,$ $B_2,$ $B_3,$ $\ldots,$ $B_m$, что при каждом $k = 1, 2, \ldots ,m$ сумма элементов множества $B_k$ равна $m^k$. Докажите, что $A$ содержит хотя бы $m/2$ элементов.

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

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано

Пусть $A = \{x_1,x_2, \dots , x_n\}$ и $y_i=m^i$. Представим все числа делящееся на $m$ и меньше $m^{m+1}$ как:

$a_1y_1+a_2y_2+\dots+a_my_m$, где $a_i \in \{0, 1, \dots, m-1\}$, для всех $1 \leq i \leq m$.

По условию эти число еще можно представить как:

$b_1x_1+b_2x_2+\dots+b_nx_n$, где $b_i \in \{0, 1, \dots, m(m-1)\}$.

Заметим что так можно представить не более $m^m \leq (m(m-1)+1)^n \leq m^{2n}$ $\implies$ $m^m \leq m^{2n}$ $\implies m/2 \leq n$ что и требовалось.