Решение
Чичиков не прав, вот контрпример. Пусть есть хозяин,
три его сына и три гостя. Гости попарно незнакомы, хозяин с ними всеми
знаком, а три сына знакомы с тремя разными парами гостей. Хорды гостей
пересекают хорду хозяина в трех различных точках. Одна точка - средняя, две -
крайние, соотвественно назовем средними и крайними
и хорды гостей, и самих гостей. Ясно, что крайние хорды лежат по разные стороны
от средней.
Хорда сына, знакомого лишь с крайними гостями должна пересечь крайние
хорды, но не пересечь среднюю. Противоречие.
|
|
Замечание. Есть контрпример и на
6 человек, но его несколько сложнее обосновать. Пусть граф знакомств -
пятиугольная пирамида. Хорды, соответствующие вершинам
основания пирамиды, должны образовать 5-угольник с "хвостиками" (см. рис.), а
хорда, со-ответствующая вершине, не может пересечь
все пять его "сторон".
Идея неконструктивного решения для
знатоков. "Легко" видеть, что все
"схемы Чичикова" на 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.
Следовательно, существует
граф знакомств, который не может быть реализован схемой Чичикова.