Международная олимпиада 2021, Санкт-Петербург, Россия, 2021 год
Дано целое число m>2. В конечном множестве A, состоящем из (не обязательно положительных) целых чисел, нашлись такие подмножества B1, B2, B3, …, Bm, что при каждом k=1,2,…,m сумма элементов множества Bk равна mk. Докажите, что A содержит хотя бы m/2 элементов.
посмотреть в олимпиаде
Комментарий/решение:
Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано
Пусть A={x1,x2,…,xn} и yi=mi. Представим все числа делящееся на m и меньше mm+1 как:
a1y1+a2y2+⋯+amym, где ai∈{0,1,…,m−1}, для всех 1≤i≤m.
По условию эти число еще можно представить как:
b1x1+b2x2+⋯+bnxn, где bi∈{0,1,…,m(m−1)}.
Заметим что так можно представить не более mm≤(m(m−1)+1)n≤m2n ⟹ mm≤m2n ⟹m/2≤n что и требовалось.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.