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

Проект МЦНМО
при участии
школы 57
Задача 109634
Темы:    [ Объединение, пересечение и разность множеств ]
[ Подсчет двумя способами ]
[ Классическая комбинаторика (прочее) ]
[ Классические неравенства (прочее) ]
Сложность: 5
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение 1

  Обозначим  n = 16000.  Предположим, что каждые два комитета имеют не более трёх общих членов. Пусть двое секретарей A и B составляют списки всевозможных председателей на три заседания Думы. A считает, что любой депутат может быть председателем на каждом из этих заседаний, поэтому у него получилось 1600³ списков. B считает, что на каждом заседании могут председательствовать только члены одного (неважно какого именно) комитета, поэтому сначала он запросил соответствующие списки от каждого комитета и получил 80³n списков. После этого B выбросил из списков, поданных i-м комитетом, те тройки, которые уже вошли в списки одного из предыдущих  i – 1  комитетов. Так как каждые два комитета (а таких пар  ) выдвинули всех своих общих членов, то B при формировании своих списков выбросил не более, чем    списков. Очевидно, что списков, которые составил A, не меньше, чем списков, которые составил B, то есть   1600³ ≥ 80³·n – ½ n(n – 1)·3³ > 80³·n – 16n² = (80³ – 16n)n = (29·10³ – 28·10³) = 1600³. Противоречие.


Решение 2

  Пусть всего имеется n комитетов, и ni – число комитетов, куда входит i-й депутат. Выпишем для каждого депутата все пары комитетов, куда он входит. Всего будет выписано     пар. По условию     согласно неравенству между средним квадратичным и средним арифметическим     Поэтому  S ≥ 2n² – 40n.
  С другой стороны, если у каждой пары комитетов имеется не более трёх общих членов, то  S3/2 n(n – 1).  Отсюда  2n² – 40n3/2 n(n – 1),  то есть
4n – 80 ≤ 3n – 3.  Следовательно,  n ≤ 77.  Противоречие.

Замечания

См. обсуждение и решение этой задачи в решениях Задачника "Кванта".

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

журнал
Название "Квант"
год
Год 1996
выпуск
Номер 5
Задача
Номер М1566
олимпиада
Название Всероссийская олимпиада по математике
год
Год 1996
Этап
Вариант 5
Класс
Класс 9
задача
Номер 96.5.9.4

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

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