Задача 111039

Темы:    [ Объединение, пересечение и разность множеств ] [ Сочетания и размещения ]

Сложность: 4+ Классы: 9,10,11

Условие

Автор: Канель-Белов А.Я.

Дано 101-элементное подмножество A множества  S = {1, 2, ..., 1000000}.
Докажите, что для некоторых  t₁, ..., t₁₀₀  из S множества   A_j = {x + t_j | x ∈ A;  j = 1, ..., 100}   попарно не пересекаются.

Решение

Рассмотрим множество  D = {x – y|  x, y ∈ A}.  В нём не более чем  10101 = 101·100 + 1  элемент. Ясно, что условие  A_i ∩ A_j = ∅  равносильно тому, что  t_i – t_j ∉ D.  Будем выбирать t_i по одному. t₁ выберем произвольно. Предположим, что  t₁, ..., t_m,  m ≤ 99,  уже выбраны. Новое t_m+1 можно выбрать произвольно из дополнения к   .   Это дополнение не пусто, ибо число элементов в множестве     не превосходит
|D|m ≤ 10101m < 10⁶.

Замечания

Из приведённого решения следует, что оценка в условии задачи далеко не точна. Для k-элементного подмножества A n-элементного множества S количество m элементов t_i, удовлетворяющее условию, оценивается снизу из неравенства  

Источники и прецеденты использования

олимпиада
Название	Международная Математическая Олимпиада
год
Год	2003
задача
Номер	1