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

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

Условие

Из набора гирь весом 1, 2, ..., 26 выделить шесть гирь так, чтобы среди них не было выбрать двух кучек равного веса.
Доказать, что нельзя выбрать семь гирь, обладающих тем же свойством.


Решение


  Набор гирь 26, 25, 24, 22, 19 и 11 удовлетворяет условию.
  Пусть выбраны какие-то семь гирь. Заметим, что нельзя брать одновременно гири 26, 25, 24, 23 (среди них уже есть две кучки равного веса), и поэтому сумма весов любых четырёх гирь из этих семи будет меньше 98. Но существует ровно    разных наборов из семи гирь по 1, 2, 3 и 4 гири. Поэтому веса каких-то двух наборов будут совпадать.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 29
Год 1966
вариант
1
Класс 9,10,11
Тур 2
задача
Номер 4

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

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