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

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

Условие

У Пети всего 28 одноклассников. У каждых двух из 28 различное число друзей в этом классе. Сколько друзей у Пети?


Решение

  У одноклассников Пети может быть 0, 1, 2, ..., 28 друзей – всего 29 вариантов. Но если кто-то дружит со всеми, то у всех не меньше одного друга. Поэтому либо кто-то дружит со всеми, либо кто-то не дружит ни с кем. В обоих случаях остается 28 вариантов: 1, 2, ..., 28 или 0, 1, ..., 27.
  Пусть у A больше всего друзей, а у B – меньше всего. В первом случае A дружит со всеми, а B – только с A. Во втором случае B не дружит ни с кем, а A – со всеми, кроме B. В каждом из случаев A дружит с Петей, а B – нет. Переведём A и B в другой класс. Как мы уже видели, A дружит со всеми из оставшихся, а B – ни с кем из оставшихся. Поэтому после перевода у каждого стало на одного друга меньше (среди одноклассников). Значит, у оставшихся Петиных одноклассников снова будет разное число друзей среди одноклассников.
  Cнова переведём самого "дружелюбного" и самого "нелюдимого" в другой класс и т. д.
  Повторяя эти рассуждения 14 раз, мы переведём в другой класс 14 пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети 14.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 56
Год 1993
вариант
Класс 9
задача
Номер 4

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

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