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

Проект МЦНМО
при участии
школы 57
Задача 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

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

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