Processing math: 100%

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


Дано целое число m>2. В конечном множестве A, состоящем из (не обязательно положительных) целых чисел, нашлись такие подмножества B1, B2, B3, , Bm, что при каждом k=1,2,,m сумма элементов множества Bk равна mk. Докажите, что A содержит хотя бы m/2 элементов.
посмотреть в олимпиаде

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

  0
1 месяца 29 дней назад #

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

  4
1 месяца 11 дней назад #

Пусть A={x1,x2,,xn} и yi=mi. Представим все числа делящееся на m и меньше mm+1 как:

a1y1+a2y2++amym, где ai{0,1,,m1}, для всех 1im.

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

b1x1+b2x2++bnxn, где bi{0,1,,m(m1)}.

Заметим что так можно представить не более mm(m(m1)+1)nm2n mmm2n m/2n что и требовалось.