Задача 116242

Темы:    [ Комбинаторика (прочее) ] [ Примеры и контрпримеры. Конструкции ] [ Принцип Дирихле ]

Сложность: 4- Классы: 8,9,10,11

Условие

Автор: Эвнин А.Ю.

На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека объявляются друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?

Решение

  Оценка. Всего было отправлено 2000000 приглашений, а пар на сайте  1000·1999 = 1999000.  Приглашений на 1000 больше, чем пар, поэтому внутри хотя бы 1000 пар было отправлено два приглашения. Значит, образовалось хотя бы 1000 пар.
  Пример: расставим всех в вершинах правильного 2000-угольника, и пусть каждый пригласит 1000 следующих за ним по часовой стрелке. Тогда друзьями окажутся только те, кто расположен в противоположных вершинах.

Ответ

1000 пар.

Замечания

баллы: 5 (младшие кл), 4 (старшие кл.)

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

олимпиада
Название	Турнир городов
Турнир
Дата	2009/2010
Номер	31
вариант
Вариант	осенний тур, базовый вариант, 8-9 класс
Задача
Номер	5