Задача 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