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

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

Условие

Автор: Власова Н.

По кругу стоят n мальчиков и n девочек. Назовём пару из мальчика и девочки хорошей, если на одной из дуг между ними стоит поровну мальчиков и девочек (в частности, стоящие рядом мальчик и девочка образуют хорошую пару). Оказалось, что есть девочка, которая участвует ровно в 10 хороших парах. Докажите, что есть и мальчик, который участвует ровно в 10 хороших парах.


Решение

  Заметим, что на любой дуге между членами хорошей пары поровну девочек и мальчиков.
  Пусть D – девочка, участвующая в 10 хороших парах. Обозначим всех детей по часовой стрелке K1, K2, ..., K2n так, что K1 – это D, и продолжим нумерацию циклически (например,  K0 = K2n  и  K2n+1 = K1).  При  i = 1, 2, ..., 2n  обозначим через di разность между количествами девочек и мальчиков среди K1, K2, ..., Ki; в частности,  d1 = 1 – 0 = 1  и  d2n = 0  (поэтому можно продолжить эту последовательность, полагая  d2n+1 = d1  и т. д.). Девочка D образует с Ki хорошую пару тогда и только тогда, когда  di = 0  и  Ki – мальчик, то есть  di = 0  и  di–1 = 1.  Итак, найдутся ровно 10 индексов i с такими свойствами.
  Рассмотрим любого мальчика  M = Ks,  образующего с D хорошую пару; тогда  ds= 0  и  ds–1 = 1.  Аналогично получаем, что мальчик M образует хорошую пару с Ki ровно тогда, когда  ds = di–1  и Ki – девочка (то есть  di–1 = 0  и  di = 1).
  Заметим, что любые два числа di и di+1 отличаются на единицу. Разобьём их на группы последовательных чисел, не меньших единицы, и группы последовательных чисел, не больших нуля. Тогда при обходе круга по часовой стрелке "переходов" из первых групп во вторые будет столько же, сколько и "переходов" из вторых групп в первые. Значит, у M столько же хороших напарниц, сколько у D хороших напарников. Это и требовалось доказать.

Замечания

1. Это решение можно визуализировать, нарисовав "график" последовательности (di). Тогда появление хорошего напарника у D означает, что график пересекает прямую  d = ½  сверху вниз, а появление хорошей напарницы у M – пересечение той же прямой снизу вверх.

2. Из решения следует, что если девочка образует хорошую пару с двумя мальчиками, то любая девочка, образующая хорошую пару с одним из этих мальчиков, образует её и с другим. Более того, все дети разбиваются на непересекающиеся группы (в каждой группе поровну мальчиков и девочек) так, что каждый мальчик образует хорошие пары со всеми девочками из своей группы и только с ними, и то же верно для любой девочки. При этом, при обходе по кругу мальчики и девочки из одной группы чередуются. Существуют решения, доказывающие этот факт напрямую (например, индукцией по числу детей).

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 4
класс
Класс 10
задача
Номер 10.7
олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 4
класс
Класс 11
задача
Номер 11.7

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

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