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

Условие

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

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

Решение

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

Рис.1

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

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

Рис.2

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

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

Н.Васильев

Задача М2098

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

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

Решение

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

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

Замечания

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

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