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

Проект МЦНМО
при участии
школы 57
Задача 98326
Темы:    [ Четность и нечетность ]
[ Степень вершины ]
[ Принцип Дирихле (прочее) ]
Сложность: 3
Классы: 8,9
В корзину
Прислать комментарий

Условие

При каком  n > 1  может случиться так, что в компании из  n + 1  девочек и n мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?


Решение

  Девочка может быть знакома с  0, 1, ..., n  мальчиками. Поскольку девочек  n + 1  и вариантов  n + 1,  то все эти варианты реализуются. При этом общее число пар знакомых равно  (0 + 1 + ... + n) = n(n+1)/2,  поэтому каждый мальчик знаком с (n+1)/2  девочками. Значит, n нечётно.
  При любом нечётном  n = 2m + 1  можно осуществить требуемые знакомства: разобьём девочек на пары (всего  m + 1  пара); первую девочку k-й пары
(k = 0, 1, ..., m)  познакомим с k мальчиками, вторую – с остальными  n – k  мальчиками. При этом каждый мальчик знаком ровно с одной девочкой из каждой пары.


Ответ

При любом нечётном  n > 1.

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Номер 18
Дата 1996/1997
вариант
Вариант осенний тур, тренировочный вариант, 10-11 класс
Задача
Номер 4

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

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