М1604. Задача об опорных хордах многоугольника

Задача из журнала «Квант» (1997, №4)

Условие

Внутри выпуклого многоугольника [latex]F[/latex] расположен второй выпуклый многоугольник [latex]G[/latex]. Хорда многоугольника [latex]F[/latex] — отрезок, концы которого лежат на границе [latex]F[/latex], — называется опорной к многоугольнику [latex]G[/latex], если она пересекается с [latex]G[/latex] только по границе: содержит либо одну вершину, либо сторону [latex]G[/latex]. Докажите, что:

  • найдется опорная хорда, середина которой лежит на границе [latex]G[/latex];
  • найдутся по крайней мере две такие хорды.

Решение

Идею решения можно сформулировать одной фразой. Рассмотрим площади сегментов, отрезаемых от [latex]F[/latex] хордами, опорными к [latex]G[/latex] (рис.1), и выберем среди них наибольшую и наименьшую. Соответствующие хорды касаются [latex]G[/latex] своими серединами.

М1604_1

Рис.1

Изложим теперь решение более подробно. Пусть [latex]l\left(\varphi \right)[/latex] — опорная к [latex]G[/latex] прямая, составляющая угол [latex]\varphi [/latex] с некоторым фиксированным направлением [latex]l_{0}[/latex]. Мы считаем, что [latex]l\left(\varphi \right)[/latex] — направленная прямая, [latex]G[/latex] содержится в её правой полуплоскости; [latex]G\left(\varphi \right)=G\bigcap{l\left(\varphi \right)}[/latex] — одна точка (вершина [latex]G[/latex]) или отрезок (сторона [latex]G[/latex]). Ясно, что для каждого [latex]\varphi [/latex], [latex]0\leq \varphi <2\pi [/latex], прямая [latex]l\left(\varphi \right)[/latex] определена однозначно. Рассмотрим площадь [latex]S=S\left(\varphi \right)[/latex] «сегмента», отрезаемого прямой [latex]l\left(\varphi \right)[/latex] от [latex]F[/latex], — пересечения [latex]F[/latex] с левой полуплоскостью этой прямой. Очевидно, что [latex]S=S\left(\varphi \right)[/latex] — непрерывная функция от [latex]\varphi [/latex] на отрезке [latex]0\leq \varphi <2\pi [/latex], где [latex]S\left(2\pi \right)=S\left(0 \right)[/latex].

Пусть [latex]AB[/latex] — хорда, высекаемая многоугольником [latex]F[/latex] на прямой [latex]l\left(\varphi \right)[/latex], и [latex]K[/latex] — её середина. Докажем, что если [latex]K[/latex] не лежит на границе с [latex]G[/latex], то в некоторой окрестности [latex]\varphi [/latex] функция [latex]S[/latex] монотонна (возрастает или убывает). Рассмотрим близкую к [latex]l\left(\varphi \right)[/latex] прямую [latex]l\left(\varphi +\delta \right)[/latex] и соответствующую хорду [latex]A_{1}B_{1}[/latex]. При достаточно малом [latex]\delta [/latex] прямая [latex]l\left(\varphi +\delta \right)[/latex] получается из [latex]l\left(\varphi \right)[/latex] поворотом вокруг некоторой точки [latex]P\in G\left(\varphi \right)[/latex], лежащей на границе [latex]G[/latex], а разность площадей [latex]S\left(\varphi +\delta \right)-S\left(\varphi \right)[/latex] равна разности площадей треугольников [latex]APA_{1}[/latex] и [latex]BPB_{1}[/latex] (рис.2). Если [latex]PA<PB[/latex], то (при малом [latex]\delta [/latex]) [latex]PA_{1}<PB_{1}[/latex] и площадь треугольника [latex]APA_{1}[/latex] меньше площади треугольника [latex]BPB_{1}[/latex] (треугольник, симметричный [latex]APA_{1}[/latex] относительно [latex]P[/latex], лежит внутри [latex]BPB_{1}[/latex]); таким образом, при всех достаточно малых [latex]\delta >0[/latex] выполнено неравенство [latex]S\left(\varphi +\delta \right)<S\left(\varphi \right)[/latex].

М1604_2

Рис.2

Аналогично, [latex]S\left( \varphi \right)<S\left(\varphi -\varepsilon \right)[/latex] при достаточно малом [latex]\varepsilon [/latex] — прямая [latex]l\left(\varphi -\varepsilon \right)[/latex] получается поворотом [latex]l\left(\varphi \right)[/latex] вокруг точки [latex]P’\in G\left(\varphi \right)[/latex], либо совпадающей с [latex]P[/latex], либо, во всяком случае, лежащей по ту же сторону от середины [latex]K[/latex], так что [latex]AP'<BP'[/latex]. Итак, если [latex]G\left(\varphi \right)[/latex] лежит по одну (на рисунке 2 — левую) сторону от [latex]K[/latex], то в окрестности [latex]\varphi[/latex] функция [latex]S[/latex] убывает. Если [latex]G\left(\varphi \right)[/latex] расположена по другую сторону от [latex]K[/latex], то в окрестности [latex]\varphi [/latex] функция [latex]S[/latex] возрастает.

Однако непрерывная функция [latex]S = S\left(\varphi \right)[/latex] (принимающая равные значения на концах отрезка [latex]\left[0, 2\pi \right][/latex]) должна достигать максимума и минимума. По доказанному выше, в этих точках середина хорды [latex]K[/latex] должна лежать в [latex]G\left(\varphi \right)[/latex], т.е. принадлежать границе [latex]G[/latex].

Н.Васильев

M2098

Задача М2098

Двое играют в игру, делая ходы по очереди: первый рисует на плоскости многоугольник, не налегающий на уже нарисованные, а второй ответным ходом раскрашивает его в один из 2008 цветов. Второй игрок хочет, чтобы любые два многоугольника, граничащие по отрезку сторны, имели разные цвета. Сможет ли первый игрок помешать ему?

Ответ: сможет

Решение

М2098Докажем индукцией по [latex]n[/latex], что первый может играть так, что нарисованные им многоугольники будут давать в объединении некоторый многоугольник [latex]P_{n}[/latex], на границу которого выходят многоугольники не менее [latex]n[/latex] цветов. Отсюда будет следовать, что никакого конечного числа цветов недостаточно.

База индукции очевидна. Пусть утверждение верно для [latex]n=k[/latex], докажем его для [latex]n=k+1[/latex]. Из предположения индукции следует, что первый игрок может играть так, чтобы нарисованные многоугольники давали в объединении [latex]k[/latex] многоугольников [latex]P_{k}^{(1)},P_{k}^{(2)},’cdots,P_{k}^{(k)}[/latex], на границу каждого из которых выходят многоугольники не менее [latex]k[/latex] цветов. На границе многоугольника [latex]P_{k}^{(1)}[/latex] выделим отрезок [latex]Delta_{1}[/latex] некоторго цвета 1, на границе многоугольника [latex]P_{k}^{(2)}[/latex] выделим отрезок [latex]Delta_{2}[/latex] некоторго цвета 2, отличного от 1, и т.д., на границе многоугольника [latex]P_{k}^{(k)}[/latex] выделим отрезок [latex]Delta_{k}[/latex] некоторго цвета k, отличного от уже определенных цветов [latex]1,2,cdots,k-1[/latex]. Пусть теперь первый нарисует многоугольник [latex]P[/latex], пересекающийся с многоугольником [latex]P_{k}^{(i)}[/latex] по части отрезка [latex]Delta_{i}[/latex] для всех [latex]i=1,2,cdots,k[/latex] (рис.). Второй игрок должен раскрасить многоугольник [latex]P[/latex] в цвет, отличный от цветов [latex]1,2,cdots,k[/latex]. Тогда на границу многоугольника, являющего объединением многоугольников [latex]P,P_{k}^{(1)},P_{k}^{(2)},cdots,P_{k}^{(k)}[/latex], выходят не менее [latex]k+1[/latex] цветов. Переход индукции доказан.

Замечания

Строгое доказательство существования многоугольника [latex]P[/latex] из решения задачи далеко не просто (хотя интуитивно все очевидно), оно следует из известной топологической теоремы Жордана.

Отметим, что вопрос, поставленный в задаче, уже рассматривался в «Задачнике «Кванта»» для случая, когда первому игроку позволяется рисовать многоугольники лишь специального вида. Результат этой задачи интресно сопоставить также со знаменитой теоремой о четырех красках, согласно которой для раскрашивания правильным образом любой карты на плоскости достаточно лишь четырех цветов.

Е.Гик, П.Кожевников