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

Проект МЦНМО
при участии
школы 57
Задача 110126
Темы:    [ Разбиения на пары и группы; биекции ]
[ Задачи с ограничениями ]
[ Степень вершины ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?


Решение

  Поскольку  45 = 1 + 2 + 3 + ... + 9,  можно разбить 45 человек на группы по 1, 2, ..., 9 человек. Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из k-й группы имеет  45 – k  знакомых.

При этом условие задачи выполнено, и общее количество пар знакомых людей равно  
  Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое k,  0 ≤ k ≤ 44.  Пусть некоторый выпускник знаком ровно с k другими. По условию никакой из его знакомых не может иметь ровно k знакомых. Поэтому количество выпускников, знакомых ровно с k другими, не превосходит
45 – k.
  Обозначим через  A0, A1, ..., A44  количество выпускников, имеющих соответственно 0, 1, ..., 44 знакомых. Как показано выше,  Ak ≤ 45 – k,  кроме того,  A0 + A1 + ... + A44 = 45.
  Оценим общее число знакомств:   2S = A1 + 2A2 + ... + 44A44 = A44 + (A44 + A43) + ... + (A44 + A43 + ... + A36) + ... + (A44 + A43 + ... + A0) ≤
≤ 1 + (1 + 2) + ... + (1 + 2 + ... + 9) + 45 + 45 + ... + 45 = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 36·45 = 1740.


Ответ

870 пар.

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

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

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

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