|
|
 |
Условие
Окружность разбита точками A1, A2,..., An наДокажите, что если для каждой точки разбиения Ak можно указать две непересекающиеся одинаково окрашенные дуги с общим
Решение
Мы ограничимся тем, что приведем схему доказательства, оставив читателям детали промежуточных рассуждений.
Сначала условимся о терминологии и обозначениях. Большими латинскими буквами
будем обозначать точки разбиения, малыми греческими– окрашенные дуги
с концами в точках разбиения. Запись α=β будет означать, что дуги
α и β одинаково окрашены. В дальнейшем одинаково окрашенные дуги
будем называть равными. Через |α| обозначим длину дуги α .
Направление обхода окружности по часовой стрелке примем за положительное (это
позволит нам естественным образом различать начала и концы дуг). Через
βγ обозначим дугу, получающуюся, если к концу дуги β
приклеить начало дуги γ (рис.12).
Симметричной дугой назовем такую дугу, на которой лежат равные меньшие
дуги в начале и конце, т.е. α – симметричная дуга, если существуют
дуги β , γ и δ такие, что α=β γ=δ β
(рис.13).
По условию для каждой точки разбиения можно указать пару непересекающихся
равных дуг с общим концом в этой точке. Вообще говоря, таких пар дуг для каждой
точки, может оказаться и несколько– попробуйте привести пример. Поэтому
уточним, какую именно пару мы будем рассматривать: сопоставим каждой точке
разбиения ту пару непересекающихся равных дуг (с общим концом), дуги которой
имеют минимальную длину; в дальнейшем только такие пары и будем рассматривать.
Нам понадобится следующая
Лемма1. Если дуга α является минимальной дугой, то она
несимметрична (докажите эту лемму самостоятельно).
Пусть среди всех минимальных пар дуг, соответствующих различным точкам
разбиения, пара, соответствующая точке A , имеет максимальную длину, и пусть
отличные от A концы дуг этой пары– точки B и C (см.рис.14, а)–
не совпадают.
Центральным местом доказательства является
Основная лемма. Если из окружности вырезать дугу BA и "склеить"
точку A с точкой B , то новая окружность будет снова обладать тем свойством,
что для любой точки разбиения можно указать пару непересекающихся равных дуг
с общим концом в этой точке.
С помощью этой леммы "периодичность" окраски доказывается индукцией по числу
точек разбиения. Индукцию мы проведем позднее, а сейчас наметим доказательство
основной леммы.
Обозначим дуги BA и AC буквой α . Рассмотрим часть новой окружности,
получающейся из старой после вырезания дуги BA и "склеивания" точки A
с точкой B (см.рис.14, б); обозначим точки разбиения новой окружности
буквами со штрихами.
Пусть M' – некоторая точка разбиения новой окружности, не лежащая на дуге
A'C' , и пусть M – соответствующая ей точка старой окружности. Точке M
отвечает минимальная пара равных (например, дуге – см.рис.14, а) дуг
LM и MK . По условию леммы |α| || , следовательно, дуга MK
целиком лежит на дуге MA .
Но дуга MA равна дуге M'C' ; значит, дуга лежит в начале дуги M'C' ,
т.е. точка M' служит ее началом. Рассуждая аналогично, построим по дуге
LM дугу на новой окружности, равную , с концом в точке M' .
Однако могло бы получиться так, что построенные две дуги (одна– с началом
в точке M' , другая– концом в этой точке) пересекаются (рис.15). Покажем,
что этого на самом деле быть не может.
Обозначим дуги M'L' , L'K' и K'M' (в направлении по часовой стрелке) через
β , и δ соответственно; тогда =β = δ ,
т.е. – симметричная дуга; но это противоречит лемме1, и значит, дуги
L'M' и M'K' – не пересекаются.
Тем самым для точек M' , не лежащих на дуге A'C' , все доказано.
Пусть теперь точка M' лежит на дуге A'C' , и пусть для определенности |A'M'|
|M'C'| (см.рис.16. б). Тогда на старой окружности точке M'
соответствуют две точки– обозначим их через M и M1 , точка M
лежит на дуге BA , точка M1 – на дуге AC (рис.16, а). Случай, когда
дуга MK (минимальная дуга с началом в точке M ) не пересекается
с дугой AC , разбирается также, как и первый (когда точка M' не лежит
на A'C' ). На рис.16, а, изображен наиболее сложный случай, когда дуги MK
и AC пересекаются. В этом случае (см.обозначения рис.16, а) выполняются
следующие соотношения:
1) δ α α= γ ;
2) |δ|<|γ| , |γ|<|α| .
Лемма2. Если выполнены соотношения 1) и 2) и если дуги
и α несимметричны, то найдется дуга β такая, что
α=βγ , =γβ .
Из этой леммы вытекает, что точка K совпадает с точкой M1 и
δ=γ (см.рис.17, а.)
Используя лемму2 и то, что |A'M'| |M'C'| , легко показать, что точке
M1 соответствует пара дуг, равных дуге =γβ , откуда следует,
что C – начало дуги, равной β (рис.17, а); поэтому точке M'
соответствует пара дуг, равных γβ (рис.17, б).
Этим доказательство основной леммы заканчивается. Из него, в частности,
вытекает, что длина максимальной пары дуг на новой окружности не превосходят
длины максимальной пары дуг на старой окружности.
Перейдем к доказательству периодичности окраски. Проведем индукцию по числу
n точек разбиения. Для n=2 это очевидно. Предположим, что мы доказали
периодичность для n k , и докажем его для n=k+1 . Пусть для
определенности точке A соответствует максимальная по длине пара дуг. Если
вся окружность является объединением этой пары дуг, то индукционное
предположение верно. Если нет, то вырежем одну из этих дуг, а концы склеим.
В силу основной леммы новая окружность удовлетворяет условиям задачи, причем
точек разбиения на ней меньше, чем на старой; поэтому по предположению индукции
окраска новой окружности периодическая; причем длина периода не превосходит
длины вырезанной дуги– обозначим ее через α .
Лемма3. Если |α| 0 , α – несимметричная дуга
и αα... αβ=... , то |α|=|| .
Из этой леммы следует, что длина периода равна α , и значит, новая окружность имеет вид, изображенный на рис.18. Старая окружность получится, если мы разрежем новую в точке A и вставим дугу α ; понятно, что эта операция периодичности окраски не нарушит. Доказательство закончено.
