ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110061
Темы:    [ Принцип Дирихле (прочее) ]
[ Сочетания и размещения ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.


Решение

  Покажем, что среди произвольных 106 трехзначных чисел существуют даже четыре непересекающиеся пары с равными суммами.
  Из 106 чисел можно образовать  106·105 : 2 = 5460  пар, сумма чисел в каждой паре лежит между 200 и 2000. Если пар с каждой суммой не более трёх, то всего пар не более  1800·3 = 5400,  что не так.
  Следовательно, у каких-то четырёх пар суммы совпадают. Пары, для которых совпадают суммы, не могут пересекаться: если  x + y = x + z,  то  y = z,  и пары совпадают.

Замечания

Выбирая не только пары, но также тройки и четвёрки, можно показать, что четыре непересекающиеся подмножества с равными суммами можно выбрать среди любых 97 трёхзначных чисел.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2001
Этап
Вариант 4
Класс
Класс 11
задача
Номер 01.4.11.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .