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

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

Условие

Попав в новую компанию, Чичиков узнавал, кто с кем знаком. А чтобы запомнить это, он рисовал окружность и изображал каждого члена компании хордой, причём хорды знакомых между собой пересекались, а незнакомых – нет. Чичиков уверен, что такой набор хорд есть для любой компании. Прав ли он? (Совпадение концов хорд считается пересечением.)


Решение

Вот контрпример для семи человек. Пусть есть хозяин, три его сына и три гостя. Гости попарно незнакомы, хозяин с ними всеми знаком, а три сына знакомы с тремя разными парами гостей. Хорды гостей пересекают хорду хозяина в трёх различных точках. Одна точка – средняя, две – крайние, соответственно назовём средними и крайними и хорды гостей, и самих гостей. Ясно, что крайние хорды лежат по разные стороны от средней. Хорда сына, знакомого лишь с крайними гостями должна пересечь крайние хорды, но не пересечь среднюю. Противоречие.


Ответ

Не прав.

Замечания

1. Есть контрпример и на шесть человек, но его несколько сложнее обосновать. Пусть граф знакомств – пятиугольная пирамида. Хорды, соответствующие вершинам основания пирамиды, должны образовать пятиугольник с "хвостиками" (см. рис.), а хорда, соответствующая вершине, не может пересечь все пять его "сторон".

2. Идея неконструктивного решения. "Легко" видеть, что все "схемы Чичикова" на n человек можно реализовать на сторонах и диагоналях правильного 2n-угольника. Число таких схем Чичикова (с указанием номеров) равно  (2n)!·2n.  При этом разным схемам может соответствовать один и тот же граф знакомств. Но число всевозможных графов знакомств (с нумерацией вершин) равно 2n(n–1)/2. При  n = 14  второе число больше:
20! = 2·(3·5)·4·(6·10)·(7·9)·8·(11·21)·(12·20)·(13·19)·(14·18)·(15·17)·16·22·...·28 < 2·43·85·1611·329 = 2·26·215·244·235 = 2101 = 291·214.  Следовательно, существует граф знакомств, который не может быть реализован схемой Чичикова.

3. Баллы: 8-9 кл. – 5, 10-11 кл. – 4.

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

олимпиада
Название Турнир городов
Турнир
Номер 28
Дата 2006/2007
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 1
олимпиада
Название Турнир городов
Турнир
Номер 28
Дата 2006/2007
вариант
Вариант осенний тур, основной вариант, 8-9 класс
задача
Номер 2

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

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