|
|
 |
Условие
Попав в новую компанию, Чичиков узнавал, кто с кем знаком. А чтобы запомнить это, он рисовал окружность и изображал каждого члена компании хордой, причём хорды знакомых между собой пересекались, а незнакомых – нет. Чичиков уверен, что такой набор хорд есть для любой компании. Прав ли он? (Совпадение концов хорд считается пересечением.)
Решение
Вот контрпример для семи человек. Пусть есть хозяин, три его сына и три гостя. Гости попарно незнакомы, хозяин с ними всеми знаком, а три сына знакомы с тремя разными парами гостей. Хорды гостей пересекают хорду хозяина в трёх различных точках. Одна точка – средняя, две – крайние, соответственно назовём средними и крайними и хорды гостей, и самих гостей. Ясно, что крайние хорды лежат по разные стороны от средней. Хорда сына, знакомого лишь с крайними гостями должна пересечь крайние хорды, но не пересечь среднюю. Противоречие.
Ответ
Не прав.
Замечания
1. Есть контрпример и на шесть человек, но его несколько сложнее обосновать. Пусть граф знакомств – пятиугольная пирамида. Хорды, соответствующие вершинам основания пирамиды, должны образовать пятиугольник с "хвостиками" (см. рис.), а хорда, соответствующая вершине, не может пересечь все пять его "сторон".
2. Идея неконструктивного решения. "Легко" видеть, что все
"схемы Чичикова" на n человек можно реализовать на сторонах и диагоналях правильного 2n-угольника. Число таких схем Чичикова (с указанием номеров) равно (2n)!·2–n. При этом разным схемам может соответствовать один и тот же граф знакомств. Но число всевозможных графов знакомств (с нумерацией вершин) равно 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.
