«ЗАДАЧИ ПО ПЛАНИМЕТРИИ УЧЕБНОЕ ПОСОБИЕ 5-е издание, исправленное и дополненное Допущено Министерством образования и науки Российской Федерации Издательство МЦНМО ОАО Московские учебники Москва 2006 УДК 514.112 ББК ...»

20.34. Рассмотрим все окружности, проходящие через две соседние вершины Ai и Ai+1 и такую вершину Aj, что Ai Aj Ai+1 < 90. Хотя бы одна такая окружность есть. В самом деле, один из углов Ai Ai+2 Ai+1 и Ai+1 Ai Ai+ меньше 90 ; в первом случае положим Aj = Ai+2, а во втором Aj = Ai. Выберем среди всех таких окружностей (для всех i и j) окружность S наибольшего радиуса; пусть для определённости она проходит через точки A1, A2 и Ak.

Предположим, что вершина Ap лежит вне окружности S. Тогда точки Ap и Ak лежат по одну сторону от прямой A1 A2 и A1 Ap A2 < A1 Ak A2 < 90.

Из теоремы синусов следует, что радиус описанной окружности у треугольника A1 Ap A2 больше, чем у треугольника A1 Ak A2. Получено противоречие, поэтому окружность S содержит весь многоугольник A1... An.

Пусть для определённости A2 A1 Ak A1 A2 Ak. Докажем, что тогда A и Ak — соседние вершины. Если Ak = A3, то 180 A2 A3 Ak A2 A1 Ak < 90, поэтому радиус описанной окружности у треугольника A2 A3 Ak больше, чем у треугольника A1 A2 Ak. Получено противоречие, поэтому окружность S проходит через соседние вершины A1, A2 и A3.

ПРИНЦИП ДИРИХЛЕ

1. Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причём m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле.

А главное, этот метод даёт неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путём явного построения или указания требуемого объекта, может привести к гораздо большим трудностям.

2. Некоторые задачи решаются также методами, в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения (все они легко доказываются методом от противного).

а) Если на отрезке длиной 1 расположено несколько отрезков, сумма длин которых больше 1, то по крайней мере два из них имеют общую точку.

б) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2p, то по крайней мере две из них имеют общую точку.

в) Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше 1, то по крайней мере две из них имеют общую точку.

§ 1. Конечное число точек, прямых и т. д.

21.1. Узлы бесконечной клетчатой бумаги раскрашены в два цвета.

Докажите, что существуют две горизонтальные и две вертикальные прямые, на пересечении которых лежат точки одного цвета.

21.2. Внутри равностороннего треугольника со стороной 1 расположено пять точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5.

21.3. В прямоугольнике 3 4 расположено 6 точек. Докажите, что среди них найдутся две точки, расстояние между которыми не превосходит 5.

21.4. На шахматной доске 8 8 отмечены центры всех полей.

Можно ли тринадцатью прямыми разбить доску на части так, чтобы внутри каждой из них лежало не более одной отмеченной точки?

21.5. На плоскости дано 25 точек, причём среди любых трёх из них найдутся две на расстоянии меньше 1. Докажите, что существует круг радиуса 1, содержащий не меньше 13 из этих точек.

21.6*. В квадрате со стороной 1 находится 51 точка. Докажите, что какие-то три из них можно накрыть кругом радиуса 1/7.

21.7*. Каждый из двух дисков разделён на 1985 равных секторов и на каждом окрашено произвольным образом (одним цветом) по 200 секторов. Диски наложили друг на друга и один стали поворачивать на углы, кратные 360 /1985. Докажите, что существует по крайней мере 80 положений, при которых совпадает не более 20 окрашенных секторов.

21.8*. Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2 : 3. Докажите, что по крайней мере три из этих девяти прямых проходят через одну точку.

21.9*. В парке растёт 10 000 деревьев, посаженных квадратно-гнездовым способом (100 рядов по 100 деревьев). Какое наибольшее число деревьев можно срубить, чтобы выполнялось следующее условие: если встать на любой пень, то не будет видно ни одного другого пня?

(Деревья можно считать достаточно тонкими.) 21.10*. Какое наименьшее число точек достаточно отметить внутри выпуклого n-угольника, чтобы внутри любого треугольника с вершинами в вершинах n-угольника содержалась хотя бы одна отмеченная точка?

21.11*. Внутри выпуклого 2n-угольника взята точка P. Через каждую вершину и точку P проведена прямая. Докажите, что найдётся сторона многоугольника, с которой ни одна из проведённых прямых не имеет общих внутренних точек.

21.12*. Докажите, что в любом выпуклом 2n-угольнике найдётся диагональ, не параллельная ни одной из его сторон.

21.13*. Узлы бесконечной клетчатой бумаги раскрашены в три цвета. Докажите, что существует равнобедренный прямоугольный треугольник с вершинами одного цвета.

21.14. На плоскости дано n попарно непараллельных прямых. Докажите, что угол между некоторыми двумя из них не больше 180 /n.

21.15. В окружности радиуса 1 проведено несколько хорд. Докажите, что если каждый диаметр пересекает не более k хорд, то сумма длин хорд меньше pk.

21.16. На плоскости отмечена точка O. Можно ли расположить на плоскости: а) пять кругов; б) четыре круга, не покрывающих точку O, так, чтобы любой луч с началом в точке O пересекал не менее двух кругов? («Пересекает» — имеет общую точку.) 21.17*. Внутри окружности радиуса n расположено 4n отрезков длиной 1. Докажите, что можно провести прямую, параллельную или перпендикулярную данной прямой l и пересекающую по крайней мере два данных отрезка.

21.18*. Внутри квадрата со стороной 1 расположено несколько окружностей, сумма длин которых равна 10. Докажите, что найдётся прямая, пересекающая по крайней мере четыре из этих окружностей.

21.19*. На отрезке длиной 1 закрашено несколько отрезков, причём расстояние между любыми двумя закрашенными точками не равно 0,1. Докажите, что сумма длин закрашенных отрезков не превосходит 0,5.

21.20*. Даны две окружности, длина каждой из которых равна 100 см. На одной из них отмечено 100 точек, а на другой — несколько дуг, сумма длин которых меньше 1 см. Докажите, что эти окружности можно совместить так, чтобы ни одна отмеченная точка не попала на отмеченную дугу.

21.21*. Даны две одинаковые окружности. На каждой из них отмечено по k дуг, угловая величина каждой из которых меньше · 180, причём окружности можно совместить так, чтобы отмеченные дуги одной окружности совпали с отмеченными дугами другой. Докажите, что эти окружности можно совместить так, чтобы все отмеченные дуги оказались на неотмеченных местах.

21.22. В квадрате со стороной 15 расположено 20 попарно непересекающихся квадратиков со стороной 1. Докажите, что в большом квадрате можно разместить круг радиуса так, чтобы он не пересекался ни с одним из квадратиков.

21.23*. Дана бесконечная клетчатая бумага и фигура, площадь которой меньше площади клетки. Докажите, что эту фигуру можно положить на бумагу, не накрыв ни одной вершины клетки.

21.24*. Назовём крестом фигуру, образованную диагоналями квадрата со стороной (рис. 21.1). Докажите, что в круге радиуса 100 можно разместить лишь конечное число непересекающихся крестов. Рис. 21. 21.25*. Попарные расстояния между точками A1,..., An больше 2. Докажите, что любую фигуру, площадь которой меньше p, можно сдвинуть на вектор длиной не более 1 так, что она не будет содержать точек A1,..., An.

21.26*. В круге радиуса 16 расположено 650 точек. Докажите, что найдётся кольцо с внутренним радиусом 2 и внешним радиусом 3, в котором лежит не менее 10 из данных точек.

21.27*. На плоскости дано n фигур. Пусть Si1...ik — площадь пересечения фигур с номерами i1,..., ik, a S — площадь части плоскости, покрытой данными фигурами; Mk — сумма всех Si1...ik. Докажите, что:

+ M3... + (1)m+1 Mm при m нечётном.

21.28*. а) В квадрате площади 6 расположены три многоугольника, площадь каждого из которых равна 3. Докажите, что среди них найдутся два многоугольника, площадь общей части которых не меньше 1.

б) В квадрате площади 5 расположено девять многоугольников площадь каждого из которых равна 1. Докажите, что среди них найдутся два многоугольника, площадь общей части которых не меньше 1/9.

21.29*. На кафтане площади 1 имеется пять заплат, причём площадь каждой их них не меньше 0,5. Докажите, что найдутся две заплаты, площадь общей части которых не меньше 0,2.

21.30*. На отрезке длиной 1 расположены попарно не пересекающиеся отрезки, сумма длин которых равна p. Обозначим эту систему отрезков A. Пусть B — дополнительная система отрезков (отрезки систем A и B не имеют общих внутренних точек и полностью покрывают данный отрезок). Докажите, что существует параллельный перенос T, для которого пересечение B и T(A) состоит из отрезков, сумма длин которых не меньше p(1 p)/2.

21.1. Возьмём три вертикальные прямые и девять горизонтальных. Будем рассматривать только точки пересечения этих прямых. Так как имеется лишь 23 = 8 вариантов раскраски трёх точек в два цвета, то найдутся две горизонтальные прямые, на которых лежат одинаково раскрашенные тройки точек. Среди трёх точек, раскрашенных в два цвета, найдутся две одинаково раскрашенные точки. Вертикальные прямые, проходящие через эти точки, вместе с ранее выбранными двумя горизонтальными являются искомыми.

21.2. Средние линии правильного треугольника со стороной 1 разбивают его на четыре правильных треугольника со стороной 0,5. Поэтому в одном из них лежат по крайней мере две данные точки, причём эти точки не могут попасть в вершины треугольника. Расстояние между этими точками меньше 0,5.

21.3. Разрежем прямоугольник на пять фигур, как показано на рис. 21.2.

В одну из них попадут по крайней мере две точки, а расстояние между любыми двумя точками каждой из этих фигур не превосходит 5.

21.4. К краю шахматной доски 8 8 прилегает 28 полей. Проведём 28 отрезков, соединяющих центры соседних крайних полей. Каждая прямая может пересекать не более двух таких отрезков, поэтому 13 прямых могут пересекать не более 26 отрезков, т. е. найдутся по крайней мере 2 отрезка, не пересекающихся ни с одной из 13 проведённых прямых. Поэтому тринадцатью прямыми нельзя разбить шахматную доску так, чтобы в каждой части лежало не более одной отмеченной точки, поскольку оба конца отрезка, не пересекающегося с прямыми, лежат в одной части.

21.5. Пусть A — одна из данных точек. Если все остальные точки лежат в круге S1 радиуса 1 с центром A, то доказывать больше нечего. Пусть теперь B — данная точка, лежащая вне круга S1, т. е. AB > 1. Рассмотрим круг S2 радиуса 1 с центром B. Среди точек A, B и C, где C — любая из данных точек, найдутся две на расстоянии меньше 1, причём это не могут быть точки A и B. Поэтому круги S1 и S2 содержат все данные точки, т. е. один из них содержит не менее 13 точек.

21.6. Разрежем данный квадрат на 25 одинаковых квадратиков со стороной 0,2. В один из них попадает не меньше трёх точек. Радиус описанной окружности квадрата со стороной 0,2 равен 1/5 2 < 1/7, поэтому его можно накрыть кругом радиуса 1/7.

21.7. Возьмём 1985 дисков, раскрашенных так же, как второй из наших дисков, и положим их на первый диск так, чтобы они занимали все возможные положения. Тогда над каждым окрашенным сектором первого диска расположено 200 окрашенных секторов, т. е. всего имеется 2002 пар совпадающих окрашенных секторов. Пусть имеется n положений второго диска, при которых совпадает не менее 21 пары окрашенных секторов. Тогда число совпадений окрашенных секторов не меньше 21n. Поэтому 21n 2002, т. е. n 1904,8. Так как n — целое число, то n 1904. Следовательно, по крайней мере при 1985 1904 = 81 положениях совпадает не более 20 пар окрашенных секторов.

21.8. Данные прямые не могут пересекать соседние стороны квадрата ABCD, так как иначе образуются не два четырёхугольника, а треугольник и пятиугольник. Пусть прямая пересекает стороны BC и AD в точках M и N.

Трапеции ABMN и CDNM имеют равные высоты, поэтому их площади относятся как средние линии, т. е. MN делит отрезок, соединяющий середины сторон AB и CD, в отношении 2 : 3. Точек, делящих средние линии квадрата в отношении 2 : 3, имеется ровно четыре. Так как данные девять прямых проходят через эти четыре точки, то через одну из точек проходят по крайней мере три прямые.

21.9. Разобьём деревья на 2500 четвёрок, как показано на рис. 21.3.

В каждой такой четвёрке нельзя срубить более одного дерева. С другой стороны, можно срубить все деревья, растущие в левых верхних углах квадратов, образованных нашими четвёрками деревьев. Поэтому наибольшее число деревьев, которые можно срубить, равно 2500.

21.10. Так как диагонали, выходящие из одной вершины, делят n-угольник на n 2 треугольника, n 2 точки необходимы.

Из рис. 21.4 можно понять, как обойтись n 2 точками: достаточно отметить по одной точке в каждом зачернённом треугольнике. В самом деле, внутри треугольника Ap Aq Ar, где p < q < r, всегда содержится зачернённый треугольник, прилегающий к вершине Aq.

21.11. Возможны два случая:

1. Точка P лежит на некоторой диагонали AB. Тогда прямые PA и PB совпадают и не пересекают сторон. Остаются 2n 2 прямые; они пересекают 21.12. Количество диагоналей 2n-угольника равно 2n(2n 3)/2 = n(2n 3). Легко проверить, что диагоналей, параллельных данРис. 21. 2n(n 2). А так как 2n(n 2) < n(2n 3), то найдётся диагональ, не параллельная ни одной из сторон.

21.13. Предположим, что нет равнобедренного прямоугольного треугольника с катетами, параллельными сторонами клеток, и вершинами одного цвета.

Для удобства можно считать, что раскрашены не узлы, а клетки. Разобьём лист на квадраты со стороной 4; тогда на диагонали каждого такого квадрата найдутся две клетки одного цвета. Пусть число n больше количества различных раскрасок квадрата со стороной 4. Рассмотрим квадрат, состоящий из n2 квадратов со стороной 4. На его диагонали найдутся два одинаково раскрашенных квадрата со стороной 4. Возьмём, наконец, квадрат K, на диагонали которого найдутся два одинаково раскрашенных квадрата со стороной 4n.

Рассмотрев квадрат со стороной 4n и в нём два одинаково раскрашенных квадрата со стороной 4, получим четыре клетки первого цвета, две клетки второго цвета и одну клетку третьего цвета (см. рис. 21.6). Аналогично, рассмотрев квадрат K, получим клетку, которая не может быть ни первого, ни второго, ни третьего цвета.

21.14. Возьмём на плоскости произвольную точку и проведём через неё прямые, параллельные данным. Они разделят плоскость на 2n углов, в сумме дающих 360. Поэтому один из этих углов не превосходит 180 /n.

21.15. Предположим, что сумма длин хорд не меньше pk, и докажем, что тогда найдётся диаметр, пересекающий по крайней мере k + 1 хорду. Так как длина дуги, стягиваемой хордой, больше длины этой хорды, то сумма длин дуг, стягиваемых данными хордами, больше pk. Если мы к этим дугам добавим ещё и дуги, симметричные им относительно центра окружности, то сумма длин всех рассматриваемых дуг будет больше 2pk. Поэтому найдётся точка, которую покрывает по крайней мере k + 1 из этих дуг. Диаметр, проведённый через эту точку, пересекает по крайней мере k + 1 хорду.

21.16. а) Можно. Пусть O — центр правильного пятиугольника ABCDE.

Тогда круги, вписанные в углы AOC, BOD, COE, DOA и EOB, обладают требуемым свойством.

б) Нельзя. Рассмотрим для каждого из четырёх кругов угол, образованный касательными к нему, проходящими через точку O. Так как каждый из этих четырёх углов меньше 180, в сумме они дают меньше 2 · 360. Поэтому найдётся точка плоскости, покрытая не более чем одним из этих углов. Луч, проведённый через эту точку, пересекает не более одного круга.

21.17. Пусть l1 — произвольная прямая, перпендикулярная l. Обозначим длины проекций i-го отрезка на прямые l и l1 через ai и bi соответственно. Так как длина каждого отрезка равна 1, то ai + bi 1. Поэтому (a1 +... + a4n ) + (b1 +... + b4n ) 4n. Пусть для определённости a1 +... + a4n b1 +... + b4n. Тогда a1 +... + a4n 2n. Все данные отрезки проецируются на отрезок длиной 2n, так как они лежат внутри окружности радиуса n. Если бы проекции данных отрезков на прямую l не имели общих точек, то выполнялось бы неравенство a1 +... + a4n < 2n. Поэтому на l есть точка, в которую проецируются точки по крайней мере двух данных отрезков. Перпендикуляр к l, проведённый через эту точку, пересекает по крайней мере два данных отрезка.

21.18. Спроецируем все данные окружности на сторону AB квадрата ABCD.

Проекцией окружности длиной l является отрезок длиной l/p. Поэтому сумма есть точка, принадлежащая проекциям по крайней мере четырёх окружностей. Перпендикуляр точку. Поэтому ни в одну точку не могут проецироваться окрашенные точки более чем пяти отрезков. Следовательно, сумма длин проекций окрашенных отрезков (равная сумме их длин) не превосходит 5 · 0,1 = 0,5.

21.20. Совместим данные окружности и посадим в фиксированную точку одной из них маляра. Будем вращать эту окружность и поручим маляру красить ту точку окружности, мимо которой он проезжает, всякий раз, когда какая-либо отмеченная точка лежит на отмеченной дуге. Нужно доказать, что после полного оборота часть окружности останется неокрашенной. Конечный результат работы маляра будет такой же, как если бы ему поручили на i-м обороте красить окружность, когда i-я отмеченная точка лежит на одной из отмеченных дуг, и сделали бы 100 оборотов. Так как в этом случае при каждом обороте окрашивается меньше 1 см, после 100 оборотов будет окрашено меньше 100 см. Поэтому часть окружности останется неокрашенной.

21.21. Совместим данные окружности и посадим в фиксированную точку одной из них маляра. Будем вращать эту окружность и поручим маляру красить ту точку окружности, мимо которой он проезжает, всякий раз, когда пересекаются какие-либо отмеченные дуги. Нужно доказать, что после полного оборота часть окружности останется неокрашенной. Конечный результат работы маляра будет такой же, как если бы ему поручили на i-м обороте красить окружность, когда i-я отмеченная дуга окружности, на которой сидит маляр, пересекается с какой-либо отмеченной дугой другой окружности, и сделали бы k оборотов.

Пусть f1,..., fn — угловые величины отмеченных дуг. По условию f1 < a,..., fn < a, где a = 180 /(k2 k + 1). За то время, пока пересекаются отмеченные дуги с номерами i и j, маляр окрашивает дугу величиной fi + fj. Поэтому сумма угловых величин дуг, окрашенных маляром на i-м обороте, не превосходит kfi + (f1 +... + fk ), а сумма угловых величин дуг, окрашенных за все k оборотов, не превосходит 2k(f1 +... + fk ). Заметим, чески k раз. В частности, точка A, мимо которой проезжает маляр в тот момент, когда совпадают отмеченные дуги, заведомо покрашена k раз. Поэтому целесообразно выбросить из рассмотрения те дуги окружности, которые маляр красит в моменты пересечения каких-либо отмеченных дуг с одинаковыми номерами. Так как все эти дуги содержат точку A, то фактически мы выбросили только одну дугу, причём угловая величина этой дуги не превосходит 2a. Сумма угловых величин оставшейся части дуг, окрашенных на i-м обороте, не превосходит (k 1)f1 + (f1 +... + fk fi ), а сумма угловых величин оставшейся части дуг, окрашенных за все k оборотов, не превосходит (2k 2)(f1 +... + fk ) < (2k2 2k)a. Часть окружности останется неокрашенной, если выполняется неравенство (2k2 2k)a 360 2a, т. е. a 180 /(k2 k + 1).

21.22. Рассмотрим фигуру, состоящую из всех точек, удалённых от квадратика со стороной 1 на расстояние не больше 1 (рис. 21.8). Ясно, что круг радиуса 1, центр которого расположен вне этой фигуры, не пересекается с квадратиком. Площадь такой фигуры равна p + 5. Центр нужного круга должен также находиться на расстоянии больше 1 от сторон большого квадрата, т. е. внутри квадрата со стороной 13. Ясно, что 20 фигур площадью p + не могут покрыть квадрат со стороной 13, так как 20(p + 5) < 132. Круг с центром в непокрытой точке обладает требуемым свойством.

21.23. Приклеим фигуру к клетчатой бумаге произвольным образом, разрежем бумагу по клеткам и сложим их в стопку, перенося их параллельно и не переворачивая. Спроецируем эту стопку на клетку. Рис. 21. Проекции частей фигуры не могут покрыть всю клетку, так как их площадь меньше. Вспомним теперь, как была расположена фигура на клетчатой бумаге, и сдвинем клетчатую бумагу параллельно, чтобы её вершины попали в точки, проецирующиеся в какую-либо непокрытую точку. В результате получим искомое расположение фигуры.

21.24. Для каждого креста рассмотрим круг радиусом 1/2 2 с центром в центре креста. Докажем, что если пересекаются два таких круга, то пересекаются и сами кресты. Расстояние между центрами пересекающихся равных кругов не превосходит их удвоенного радиуса, поэтому расстояние между центрами соответствующих им крестов не превосходит 1/ 2. Рассмотрим прямоугольник, заданный перекладинами первого креста и центром второго (рис. 21.9).

Одна из перекладин второго креста проходит через этот прямоугольник, поэтому она пересекает первый крест, так как длина перекладины равна 1/ 2, а длина диагона- ли прямоугольника не превосходит 1/ 2.

В круге конечного радиуса можно разместить лишь конечное число непересекающихся кругов радиуса 1/2 2.

21.25. Пусть — данная фигура, S1,...

..., Sn — круги радиуса 1 с центрами в точРис. 21. ках A1,..., An. Так как круги S1,..., Sn попарно не пересекаются, то фигуры Vi = Si попарно не пересекаются, а значит, сумма их площадей не превосходит площади фигуры, т. е. она меньше p. Пусть O — произвольная точка и Wi — образ фигуры Vi при переносе на вектор Ai O. Фигуры Wi лежат внутри круга S радиуса 1 с центром O и сумма их площадей меньше площади этого круга.

Поэтому некоторая точка B круга S не принадлежит ни одной из фигур Wi.

Перенос на вектор BO — искомый. Действительно, рассмотрим точку Bi, для которой BO = Bi Ai. При сдвиге на вектор Bi Ai фигура переходит в фигуру, содержащую точку Ai, тогда и только тогда, когда точка Bi принадлежит Vi, т. е. точка B принадлежит Wi.

21.26. Заметим сначала, что точка X принадлежит кольцу с центром O тогда и только тогда, когда точка O принадлежит такому же кольцу с центром X. Поэтому достаточно доказать, что если построить кольца с центрами в данных точках, то одну из точек рассматриваемого круга покроет не менее 10 колец. Рассматриваемые кольца лежат внутри круга радиуса 16 + 3 = 19, площадь которого равна 361p. Остаётся заметить, что 9 · 361p = 3249p, а суммарная площадь колец равна 650 · 5p = 3250p.

21.27. а) Пусть Ck — число способов выбрать k элементов из n. Можно проверить, что (x + y)n = Ck xk ynk (бином Ньютона).

Обозначим через Wm площадь части плоскости, покрытой ровно m фигурами. Эта часть состоит из кусков, каждый из которых покрыт какими-то сечений k фигур. Поэтому Mk = Ck Wk + Ck Wk+1 +... + Ck Wn. Следовательно, = (1 1)m + 1 = 1. Остаётся заметить, что S = W1 +... + Wn.

б) Согласно задаче а) S (M1 M2 +... + (1)m+1 Mm ) = (1)m+2 Mm+1 + (1)m+3 Mm+2 +...

(считается, что если k > i, то Ck = 0). Поэтому достаточно проверить, что Cm+1 Cm+2 + Cm+3... + (1)m+n+1 Cn 0 при i n. Из тождества (x + y)i = = (x + y)i1 (x + y) следует равенство Cj = Cj1 + Cj. Поэтому Cm+1 Ci m+... + (1)m+n+1 Cn = Cm ± Cn. Остаётся заметить, что Cn = 0 при i n.

21.28. а) Согласно задаче 21.27 а) 6 = 9 (S12 + S23 + S13 ) + S123, т. е. S12 + + S23 + S13 = 3 + S123 3. Поэтому одно из чисел S12, S23, S13 не меньше 1.

б) Согласно задаче 21.27 б) 5 9 M2, т. е. M2 4. Так как из девяти многоугольников можно образовать 9 · 8/2 = 36 пар, площадь общей части одной из этих пар не меньше M2 /36 1/9.

21.29. Пусть площадь кафтана равна M, площадь пересечения заплат с номерами i1,..., ik равна Si1...ik, а Mk = Si1...ik. Согласно задаче 21.27 а) платы: если мы рассмотрим заплату S1 как кафтан с заплатами S12, S13, S14, S15, то получим S1 S1ij S1ijk + S12345 0. Сложив такие неравенства для всех пяти заплат, получаем M1 2M2 + 3M3 4M4 + 5M (слагаемое Si1...ik входит в неравенства для заплат i1,..., ik, поэтому в сумму всех неравенств оно входит с коэффициентом k). Складывая неравенства получаем неравенство 3M 2M1 + M2 M4 + 2M5 0. Прибавив к нему неравенство M4 2M5 0 (оно следует из того, что S12345 входит во все Si1 i2 i3 i4, т. е. M4 5M5 2M5 ), получаем 3M 2M1 + M2 0, т. е. M2 2M1 3M Так как из пяти заплат можно образовать десять пар, площадь пересечения одной из этих пар не меньше M2 /10 0,2.

21.30. Пусть 1 c 1. Сдвинем данный отрезок на c вдоль себя, а затем сдвинем его на c в ортогональном направлении. Заштрихованная на рис. 21. область соответствует пересечению отрезков Ai и Bj. Её площадь равна произведению длин этих отрезков. Если рассмотреть все пары отрезков систем A и B, то заштрихованная область будет иметь площадь p(1 p). Поэтому некоторое горизонтальное сечение заштрихованных областей имеет длину не меньше p(1 p)/2.

З а м е ч а н и е. Если вместо отрезка рассматривать окружность (и вместо параллельного переноса поворот), то p(1 p)/2 можно заменить на p(1 p).

ВЫПУКЛЫЕ И НЕВЫПУКЛЫЕ МНОГОУГОЛЬНИКИ

1. Есть несколько разных (но эквивалентных) определений выпуклого многоугольника. Приведём наиболее известные и часто встречающиеся из них.

Многоугольник называют выпуклым, если выполнено одно из следующих условий:

а) он лежит по одну сторону от любой из своих сторон (т. е. продолжения сторон многоугольника не пересекают других его сторон);

б) он является пересечением (т. е. общей частью) нескольких полуплоскостей;

в) любой отрезок с концами в точках, принадлежащих многоугольнику, целиком ему принадлежит.

2. Фигуру называют выпуклой, если любой отрезок с концами в точках фигуры целиком принадлежит ей.

3. При решении некоторых задач этой главы используются понятия выпуклой оболочки и опорной прямой.

22.1. На плоскости дано n точек, причём любые четыре из них являются вершинами выпуклого четырёхугольника. Докажите, что эти точки являются вершинами выпуклого n-угольника.

22.2. На плоскости дано пять точек, причём никакие три из них не лежат на одной прямой. Докажите, что четыре из этих точек расположены в вершинах выпуклого четырёхугольника.

22.3. Внутри квадрата A1 A2 A3 A4 лежит выпуклый четырёхугольник A5 A6 A7 A8. Внутри A5 A6 A7 A8 выбрана точка A9. Докажите, что из этих девяти точек можно выбрать 5 точек, расположенных в вершинах выпуклого пятиугольника.

22.4. На плоскости дано несколько правильных n-угольников. Докажите, что выпуклая оболочка их вершин имеет не менее n углов.

22.5. Среди всех таких чисел n, что любой выпуклый 100-угольник можно представить в виде пересечения (т. е. общей части) n треугольников, найдите наименьшее.

22.6. Назовём выпуклый семиугольник особым, если три его диагонали пересекаются в одной точке. Докажите, что, слегка пошевелив одну из вершин особого семиугольника, можно получить неособый семиугольник.

22.7. Выпуклый многоугольник A1... An лежит внутри окружности S1, а выпуклый многоугольник B1... Bm — внутри S2. Докажите, что если эти многоугольники пересекаются, то одна из точек A1,...

..., An лежит внутри S2 или одна из точек B1,..., Bm лежит внутри S1.

22.8*. Докажите, что существует такое число N, что среди любых N точек, никакие три из которых не лежат на одной прямой, можно выбрать 100 точек, являющихся вершинами выпуклого многоугольника.

22.9*. Выпуклый n-угольник разрезан на треугольники непересекающимися диагоналями. Рассмотрим преобразование такого разбиения, при котором треугольники ABC и ACD заменяются на треугольники ABD и BCD. Пусть P(n) — наименьшее число преобразований, за которое любое разбиение можно перевести в любое другое. Докажите, что:

22.10*. Докажите, что в любом выпуклом многоугольнике, кроме параллелограмма, можно выбрать три стороны, при продолжении которых образуется треугольник, объемлющий данный многоугольник.

22.11*. Дан выпуклый n-угольник, никакие две стороны которого не параллельны. Докажите, что различных треугольников, о которых идёт речь в задаче 22.10, не менее n 2.

22.12*. Точка O лежит внутри выпуклого n-угольника A1... An. Докажите, что среди углов Ai OAj не менее n 1 не острых.

22.13*. В окружность вписан выпуклый n-угольник A1... An, причём среди его вершин нет диаметрально противоположных точек.

Докажите, что если среди треугольников Ap Aq Ar есть хотя бы один остроугольный, то таких остроугольных треугольников не менее n 2.

22.14*. а) Докажите, что параллелограмм нельзя покрыть тремя меньшими гомотетичными ему параллелограммами.

б) Докажите, что любой выпуклый многоугольник, кроме параллелограмма, можно покрыть тремя меньшими гомотетичными ему многоугольниками.

Мы будем рассматривать фигуры, ограниченные гладкими или кусочно гладкими1 кривыми. Периметром фигуры называют длину кривой, ограничивающей эту фигуру.

22.15. Докажите, что для любой невыпуклой фигуры существует выпуклая фигура с меньшим периметром и большей площадью.

1 Состоящими из конечного числа дуг гладких кривых.

432 Глава 22. Выпуклые и невыпуклые многоугольники 22.16. Докажите, что если существует фигура, площадь которой не меньше площади фигуры, а периметр — меньше, то существует фигура того же периметра, что и, но большей площади.

22.17. Докажите, что если какая-либо хорда выпуклой фигуры делит её на две части равного периметра, но разной площади, то существует выпуклая фигура, имеющая тот же периметр, что и, но большую площадь.

22.18*. Докажите, что если выпуклая фигура отлична от круга, то существует фигура, имеющая тот же периметр, что и, но большую площадь.

22.19*. а) Докажите, что среди всех выпуклых четырёхугольников с данными углами и данным периметром наибольшую площадь имеет описанный четырёхугольник.

б) Докажите, что среди всех выпуклых n-угольников A1... An с данными величинами углов Ai и данным периметром наибольшую площадь имеет описанный n-угольник.

22.20*. Докажите, что площадь круга больше площади любой другой фигуры того же периметра. Другими словами, если площадь фигуры равна S, а её периметр равен P, то S P2 /4p, причём равенство достигается только в случае круга (изопериметрическое неравенство).

22.21*. Докажите, что если соответственные стороны выпуклых многоугольников A1... An и B1... Bn равны, причём многоугольник B1... Bn вписанный, то его площадь не меньше площади многоугольника A1... An.

22.22*. Несамопересекающаяся ломаная расположена в данной полуплоскости, причём концы ломаной лежат на границе этой полуплоскости. Длина ломаной равна L, а площадь многоугольника, ограниченного ломаной и границей полуплоскости, равна S. Докажите, что S L2 /2p.

22.23*. Найдите кривую наименьшей длины, делящую равносторонний треугольник на две фигуры равной площади.

Пусть M — выпуклый многоугольник, l — некоторая прямая. Симметризация по Штейнеру многоугольника M относительно прямой l — это фигура, которая получается следующим образом. Через каждую точку X прямой l проведём прямую m, перпендикулярную l. Если прямая m пересекает многоугольник M по отрезку длины a, то построим на m отрезок длины a с серединой в точке X. Построенные отрезки образуют фигуру.

22.24*. Докажите, что симметризация по Штейнеру выпуклого многоугольника является выпуклым многоугольником.

22.25*. Докажите, что при симметризации по Штейнеру площадь многоугольника не изменяется, а его периметр не увеличивается.

22.26*. Пусть A и B — фиксированные точки, l и m — фиксированные числа. Выберем произвольную точку X и зададим точку P равенством XP = lXA + mXB. Докажите, что положение точки P не зависит от выбора точки X тогда и только тогда, когда l + m = 1.

Докажите также, что в этом случае точка P лежит на прямой AB.

Если l + m = 1, то точку P из задачи 22.26 будем обозначать lA + mB.

Пусть M1 и M2 — выпуклые многоугольники, l1 и l2 — положительные числа, сумма которых равна 1. Фигуру l1 M1 + l2 M2, состоящую из всех точек вида l1 A1 + l2 A2, где A1 — точка M1, а A2 — точка M2, называют суммой Минковского многоугольников M1 и M2. Сумму Минковского можно рассматривать не только для выпуклых многоугольников, но и для произвольных фигур (не обязательно выпуклых).

Аналогично для положительных чисел l1,..., ln, сумма которых равна 1, можно рассмотреть фигуру l1 M1 +... + ln Mn. Можно рассматривать и фигуры l1 M1 +... + ln Mn для l1 +... + ln = 1, но в этом случае фигура определена с точностью до параллельного переноса: при изменении точки X фигура сдвигается на некоторый вектор.

22.27*. а) Докажите, что если M1 и M2 — выпуклые многоугольники, то l1 M1 + l2 M2 — выпуклый многоугольник, число сторон которого не превосходит суммы чисел сторон многоугольников M1 и M2.

б) Пусть P1 и P2 — периметры многоугольников M1 и M2. Докажите, что периметр многоугольника l1 M1 + l2 M2 равен l1 P1 + l2 P2.

22.28*. Пусть S1 и S2 — площади многоугольников M1 и M2. Докажите, что площадь S(l1, l2 ) многоугольника l1 M1 + l2 M2 равна где S12 зависит только от M1 и M2.

22.29*. Докажите, что S (Брунн).

22.30*. а) Пусть M — выпуклый многоугольник, площадь которого равна S, а периметр равен P; D — круг радиуса R. Докажите, что площадь фигуры l1 M + l2 D равна б) Докажите, что S P2 /4p.

22.31*. Докажите, что выпуклый многоугольник имеет центр симметрии тогда и только тогда, когда его можно представить в виде суммы нескольких отрезков.

22.32*. а) На плоскости даны четыре выпуклые фигуры, причём любые три из них имеют общую точку. Докажите, что тогда и все они имеют общую точку.

434 Глава 22. Выпуклые и невыпуклые многоугольники б) На плоскости дано n выпуклых фигур, причём любые три из них имеют общую точку. Докажите, что все n фигур имеют общую точку (теорема Хелли).

22.33*. Решите с помощью теоремы Хелли задачу 20.33.

22.34*. а) Дан выпуклый многоугольник. Известно, что для любых трёх его сторон можно выбрать точку O внутри многоугольника так, что перпендикуляры, опущенные из точки O на эти три стороны, попадают на сами стороны, а не на их продолжения. Докажите, что тогда такую точку O можно выбрать для всех сторон одновременно.

б) Докажите, что в случае выпуклого четырёхугольника такую точку O можно выбрать, если её можно выбрать для любых двух сторон.

22.35*. Докажите, что внутри любого выпуклого семиугольника есть точка, не принадлежащая ни одному из четырёхугольников, образованных четвёрками его соседних вершин.

22.36*. Дано несколько параллельных отрезков, причём для любых трёх из них найдётся прямая, их пересекающая. Докажите, что найдётся прямая, пересекающая все отрезки.

22.37. Верно ли, что любой пятиугольник лежит по одну сторону от не менее чем двух своих сторон?

22.38. а) Нарисуйте многоугольник и точку O внутри его так, чтобы ни одна сторона не была видна из неё полностью.

б) Нарисуйте многоугольник и точку O вне его так, чтобы ни одна сторона не была видна из неё полностью.

22.39. Докажите, что если многоугольник таков, что из некоторой точки O виден весь его контур, то из любой точки плоскости полностью видна хотя бы одна его сторона.

22.40. Докажите, что сумма внешних углов любого многоугольника, прилегающих к меньшим 180 внутренним углам, не меньше 360.

22.41*. а) Докажите, что у любого n-угольника (n 4) есть хотя бы одна диагональ, целиком лежащая внутри его.

б) Выясните, какое наименьшее число таких диагоналей может иметь n-угольник.

22.42*. Чему равно наибольшее число вершин невыпуклого n-угольника, из которых нельзя провести диагональ?

22.43*. Докажите, что любой n-угольник можно разрезать на треугольники непересекающимися диагоналями.

22.44*. Докажите, что сумма внутренних углов любого n-угольника равна (n 2) · 180.

22.45*. Докажите, что количество треугольников, на которые непересекающиеся диагонали разбивают n-угольник, равно n 2.

22.46*. Многоугольник разрезан непересекающимися диагоналями на треугольники. Докажите, что по крайней мере две из этих диагоналей отсекают от него треугольники.

22.47*. Докажите, что для любого тринадцатиугольника найдётся прямая, содержащая ровно одну его сторону, однако при любом n > существует n-угольник, для которого это неверно.

22.48*. Чему равно наибольшее число острых углов в невыпуклом n-угольнике?

22.49*. С невыпуклым несамопересекающимся многоугольником производятся следующие операции. Если он лежит по одну сторону от прямой AB, где A и B — несмежные вершины, то одна из частей, на которые контур многоугольника делится точками A и B, отражается относительно середины отрезка AB. Докажите, что после нескольких таких операций многоугольник станет выпуклым.

22.50*. Числа a1,..., an, сумма которых равна (n 2)p, удовлетворяют неравенствам 0 < ai < 2p. Докажите, что существует n-угольник A1... An с углами a1,..., an при вершинах A1,..., An.

См. также задачи 9.29 а), 9.94, 23.1, 23.35.

22.1. Рассмотрим выпуклую оболочку данных точек. Она является выпуклым многоугольником. Нужно доказать, что все данные точки — его вершины.

Предположим, что одна из данных точек (точка A) не является вершиной, т. е. лежит внутри или на стороне этого многоугольника. Диагоналями, выходящими из одной вершины, выпуклую оболочку можно разрезать на треугольники; точка A принадлежит одному из них.

Вершины этого треугольника и точка A не могут быть вершинами выпуклого четырёхугольника. Получено противоречие.

22.2. Рассмотрим выпуклую оболочку данных точек. Если она является четырёхили пятиугольником, то всё ясно. Допустим теперь, что выпуклая оболочка является треугольником ABC, а точки D и E лежат внутри его. Точка E лежит внутри одного из треугольников ABD, BCD, CAD;

пусть для определённости она лежит внут- Рис. 22. ри треугольника ABD. Обозначим точку пересечения прямых CD и AB через H. Точка E лежит внутри одного из треугольников ADH и BDH. Если, например, E лежит внутри треугольника ADH, то AEDC — выпуклый четырёхугольник (рис. 22.1).

22.3. Предположим, что требуемого выпуклого пятиугольника нет. Проведём из точки A9 лучи через точки A5, A6, A7, A8. Эти лучи разбивают плоскость на 4 угла, каждый из которых меньше 180. Если внутри одного 436 Глава 22. Выпуклые и невыпуклые многоугольники из этих углов лежат две из точек A1, A2, A3, A4, то мы немедленно получаем требуемый пятиугольник. Поэтому внутри каждого из этих углов лежит ровно одна из указанных точек. Но тогда внутри каждого из двух углов, образованных лучами A9 A5 и A9 A7, лежат две из указанных точек.

Рассмотрев тот из углов, который меньше 180, снова получаем требуемый пятиугольник.

22.4. Пусть выпуклая оболочка вершин данных n-угольников является m-угольником и f1,..., fm — его углы. Так как к каждому углу выпуклой оболочки прилегает угол правильного n-угольника, то fi (1 (2/n))p (справа стоит величина угла правильного n-угольника). Поэтому f1 +... + fm m(1 (2/n))p = (m (2m/n))p. С другой стороны, f1 +... + fm = (m 2)p.

Следовательно, (m 2)p (m (2m/n))p, т. е. m n.

22.5. Заметим сначала, что 50 треугольников достаточно. В самом деле, пусть k — треугольник, стороны которого лежат на лучах Ak Ak1 и Ak Ak+ и который содержит выпуклый многоугольник A1... A100. Тогда этот многоугольник является пересечением треугольников 2, 4,..., 100. С другой стороны, 100-угольник, изображённый на рис. 22.2, нельзя представить в виде пересечения менее чем 50 треугольников. В самом деле, если три его стороны лежат на сторонах одного треугольника, то одна из этих сторон — сторона A1 A2. Все стороны этого многоугольника лежат на сторонах n треугольников, поэтому 2n + 1 100, т. е. n 50.

22.6. Пусть P — точка пересечения диагоналей A1 A4 и A2 A5 выпуклого семиугольника A1... A7. Одна из диагоналей A3 A7 и A3 A6, для определённости диагональ A3 A6, не проходит через точку P. Точек пересечения диагоналей шестиугольника A1... A6 конечное число, поэтому вблизи точки A7 можно выбрать такую точку A7, что прямые A1 A7,..., A6 A7 не проходят через эти точки, т. е. семиугольник A1... A7 неособый.

22.7. Предположим, что точки A1,..., An лежат вне S2, а точки B1,..., Bm лежат вне S1. Тогда окружность S1 не может лежать внутри S2, а окружность S2 — внутри S1. Окружности S1 и S2 не могут также быть расположены вне друг друга (или касаться внешним образом), поскольку иначе многоугольники A1... An и B1... Bm не могли бы пересекаться. Таким образом, окружности S1 и S2 пересекаются. При этом многоугольник A1... An лежит внутри S1 и вне S2, а многоугольник B1... Bm — внутри S2 и вне S1. Следовательно, эти многоугольники расположены по разные стороны от прямой, проходящей через точки пересечения окружностей S1 и S2. Но тогда они не могут пересекаться. Приходим к противоречию.

22.8. Мы докажем более общее утверждение. Пусть p, q и r — натуральные числа, причём p, q r. Тогда существует число N = N(p, q, r), обладающее следующим свойством: если все r-элементные подмножества N-элементного множества S произвольным образом разбиты на два непересекающихся семейства a и b, то либо существует p-элементное подмножество множества S, все r-элементные подмножества которого содержатся в a, либо существует q-элементное подмножество, все r-элементные подмножества которого содержатся в b (теорема Рамсея).

Требуемое утверждение легко следует из теоремы Рамсея. В самом деле, пусть N = N(n, 5, 4) и семейство a состоит из тех четырёхэлементных подмножеств N-элементного множества точек, выпуклые оболочки которых — четырёхугольники. Тогда существует n-элементное подмножество данного множества точек, выпуклые оболочки любых четырёхэлементных подмножеств которого — четырёхугольники, так как пятиэлементного подмножества, выпуклые оболочки любых четырёхэлементных подмножеств которого — треугольники, не существует (см. задачу 22.2). Остаётся воспользоваться результатом задачи 22.1.

Докажем теперь теорему Рамсея. Легко проверить, что в качестве N(p, q, 1), N(r, q, r) и N(p, r, r) можно взять числа p + q 1, q и p соответственно. Докажем теперь, что если p > r и q > r, то в качестве N(p, q, r) можно взять число N(p1, q1, r 1) + 1, где p1 = N(p 1, q, r) и q1 = N(p, q 1, r). В самом деле, выбросим из N(p, q, r)-элементного множества S один элемент и разобьём (r 1)-элементные подмножества оставшегося множества S на два семейства: семейство a (соответственно b ) состоит из тех подмножеств, объединения которых с выброшенным элементом входят в семейство a (соответственно b). Тогда либо существует p1 -элементное подмножество множества S, все (r 1)-элементные подмножества которого содержатся в семействе a, либо существует q1 -элементное подмножество, все (r 1)-элементные подмножества которого содержатся в семействе b. Рассмотрим первый случай. Так как p1 = N(p 1, q, r), то либо существует q-элементное подмножество множества S, все r-элементные подмножества которого лежат в b (тогда эти q элементов искомые), либо существует (p 1)-элементное подмножество множества S, все r-элементные подмножества которого содержатся в a (тогда эти p 1 элементов вместе с выброшенным элементом искомые). Второй случай рассматривается аналогично.

Итак, доказательство теоремы Рамсея можно провести индукцией по r, причём при доказательстве шага индукции используется индукция по p + q.

22.9. а) Пусть A и B — соседние вершины n-угольника. Рассмотрим разбиение n-угольника диагоналями, выходящими из вершины A, и разбиение диагоналями, выходящими из вершины B. У этих разбиений нет общих диагоналей, а каждое преобразование изменяет только одну диагональ.

б) Индукцией по n легко доказать, что любое разбиение можно перевести в разбиение диагоналями, выходящими из данной вершины A, не более чем за n 3 преобразования. Действительно, при n = 4 это очевидно. При n > всегда можно сделать одно преобразование так, чтобы появилась диагональ, выходящая из вершины A (если такой диагонали не было). Эта диагональ разбивает n-угольник на k-угольник и l-угольник, где k + l = n + 2. Остаётся заметить, что (k 3) + (l 3) + 1 = n 3.

438 Глава 22. Выпуклые и невыпуклые многоугольники Ясно также, что если m диагоналей разбиения уже выходят из вершины A, то нужно не более n 3 m преобразований, т. е. m преобразований можно сэкономить.

Если заданы два разбиения, то их можно перевести в разбиение диагоналями, выходящими из вершины A, за 2(n 3) преобразований. Одно преобразование можно сэкономить, выбрав в качестве A вершину, из которой выходит одна из диагоналей одного из разбиений. Поэтому от любого разбиения можно перейти к любому другому не более чем за 2n 7 преобразований (пройдя через разбиение диагоналями, выходящими из вершины A).

в) Два разбиения содержат 2(n 3) диагоналей, поэтому в среднем из ений. При n 13 это число больше 3, поэтому найдётся вершина, из которой выходят по крайней мере 4 диагонали данных разбиений. Выбрав её, можно параллелограмм, то у него найдутся две непараллельные несоседние стороны. Продолжив их до пересечения, получим новый многоугольник, содержащий исходный и имеющий меньшее число сторон. После нескольких таких операций получим треугольник параллелограмм ABCD. На каждой его стороне лежит сторона исходного многоугольника, и одна из Рис. 22.3 его вершин, например A, не принадлежит исходному к A вершина многоугольника, лежащая на AD, а KL — сторона, не лежащая на AD. Тогда многоугольник заключён внутри треугольника, образованного прямыми KL, BC и CD.

22.11. Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Согласно задаче 22.10 существуют прямые a, b и c, являющиеся продолжениями сторон данного n-угольника и образующие треугольник T, который содержит данный n-угольник. Пусть прямая l является продолжением какой-либо другой стороны данного n-угольника. Продолжения всех сторон n-угольника, кроме стороны, лежащей на прямой l, образуют выпуклый (n 1)-угольник, лежащий внутри треугольника T. По предположению индукции для этого (n 1)-угольника найдётся n 3 нужных треугольника.

Кроме того, прямая l и две из прямых a, b и c тоже образуют нужный треугольник.

З а м е ч а н и е. Если точки A2,..., An лежат на окружности с центром A1, причём A2 A1 An < 90 и n-угольник A1... An выпуклый, то для этого n-угольника существует ровно n 2 нужных треугольников.

22.12. Доказательство проведём индукцией по n. При n = 3 доказательство очевидно. Рассмотрим теперь n-угольник A1... An, где n 4. Точка O лежит внутри некоторого треугольника Ap Aq Ar. Пусть Ak — вершина данного n-угольника, отличная от точек Ap, Aq и Ar. Выбросив вершину Ak, из n-угольника ние индукции. Кроме того, углы Ak OAp, Ak OAq и Ak OAr не могут быть все острыми, так как сумма некоторых двух из этих углов больше 180.

22.13. Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Пусть n 4. Фиксируем один остроугольный треугольник Ap Aq Ar и выбросим вершину Ak, отличную от вершин этого треугольника. К полученному (n 1)-угольнику можно применить предположение индукции. Кроме того, если, например, точка Ak лежит на дуге Ap Aq и Ak Ap Ar Ak Aq Ar, то треугольник Ak Ap Ar остроугольный. В самом деле, Ap Ak Ar = Ap Aq Ar, Ap Ar Ak < Ap Ar Aq и Ak Ap Ar 90, а значит, Ak Ap Ar < 90.

22.14. а) Пусть ABCD — данный параллелограмм. В меньшем параллелограмме, гомотетичном ему, любой отрезок, параллельный стороне AB, строго меньше AB. То же самое верно не только для сторон, но и для диагоналей.

Поэтому каждую из четырёх вершин параллелограмма должен покрывать свой параллелограмм.

б) Пусть выпуклый многоугольник M отличен от параллелограмма. Воспользовавшись результатом задачи 22.10, выберем три стороны многоугольника M, при продолжении которых образуется треугольник ABC, объемлющий многоугольник M. Затем выберем на этих трёх сторонах точки A1, B1 и C1, отличные от вершин многоугольника (точка A1 лежит на прямой BC и т. д.).

Наконец, выберем произвольную точку O внутри многоугольника M. Отрезки OA1, OB1 и OC1 разрезают M на три части. Рассмотрим гомотетию с центром A. Если коэффициент этой гомотетии достаточно близок к 1, то образ многоугольника M полностью покрывает ту часть, которую отрезают OB1 и OC1. Две остальные части покрываются аналогично.

22.15. Для каждого направления проведём опорные прямые к фигуре и рассмотрим пересечение всех полуплоскостей, заданных этими прямыми и содержащих. В результате получим выпуклую фигуру. Она содержит, поэтому её площадь больше. Кривая, ограничивающая, отличается от кривой, ограничивающей, тем, что некоторые криволинейные участки (или ломаные) заменены прямолинейными отрезками. Поэтому периметр меньше периметра.

22.16. Пусть P и P — периметры фигур и, S и S — их площади. При гомотетии с коэффициентом P/P > 1 фигура переходит в фигуру, периметр которой равен P, а площадь равна (P/P )2 S > S.

22.17. Пусть хорда AB делит фигуру на две части 1 и 2, периметры которых равны, а площадь 1 больше площади 2. Тогда фигура, состоящая из 1 и фигуры, симметричной 1 относительно AB, имеет тот же периметр, что и, но большую площадь.

Полученная фигура может оказаться невыпуклой. В этом случае, пользуясь результатами задач 22.15 и 22.16, можно построить выпуклую фигуру того же периметра и ещё большей площади.

22.18. Рассмотрим хорду AB, делящую пополам периметр фигуры. Если AB делит фигуру на две части разной площади, то согласно задаче 22. существует фигура, которая имеет тот же периметр, что и, но большую площадь. Поэтому будем считать, что хорда AB делит фигуру на две части равной площади. На границе есть точка P, для которой APB = 90, поскольку иначе — круг с диаметром AB. Займёмся построением требуемой фигуры. Построим прямоугольный треугольник P1 A1 B1 с катетами P1 A1 = PA и P1 B1 = PB и приставим к его катетам сегменты, отсекаемые 440 Глава 22. Выпуклые и невыпуклые многоугольники хордами PA и PB (рис. 22.4). Если такой сегмент будет теперь разрезан прямой A1 B1, то, отразив одну из его частей относительно точки пересечения границы с прямой A1 B1, получим фигуру, лежащую по одну сторону от прямой A1 B1. Сегменты, прилегающие к катетам A1 P1 и P1 B1, не могут пересечься, поскольку угол между опорными прямыми в точке P1 равен 90 + f1 + f2 = 90 + (180 APB) < 270.

Пусть — фигура, состоящая из построенной нами фигуры и фигуры, симметричной ей относительно прямой A1 B1. Тогда имеет тот же периметр, что и, но большую площадь, так как З а м е ч а н и е. Этими рассуждениями мы не доказали, что среди всех фигур данного периметра наибольшую площадь имеет круг. Мы не доказывали, что среди всех фигур данного периметра есть фигура наибольшей площади.

22.19. Для всех подобных многоугольников отношение площади к квадрату периметра постоянно. Поэтому достаточно доказать, что среди всех выпуклых многоугольников с данными углами отношение площади к квадрату периметра будет наибольшим для описанного многоугольника.

а) Рассмотрим сначала случай, когда четырёхугольник ABCD — параллелограмм с заданным углом a. Если его стороны равны a и b, то отношение площади к квадрату периметра равно причём равенство достигается только при a = b, т. е. в случае, когда ABCD — ромб. Ромб является описанным четырёхугольником.

Будем теперь считать, что ABCD — не параллелограмм. Тогда продолжения двух его сторон пересекаются. Пусть для определённости лучи AB и DC пересекаются в точке E. Проведём прямую B C BC, касающуюся вписанной в треугольник AED окружности (рис. 22.5; точки B и C лежат на сторонах AE и DE). Пусть r — радиус вписанной окружности треугольника AED, O — её центр. Тогда

SEB C O C

где q = (EB + EC B C )/2. Поэтому где p — полупериметр треугольника AED, k = EB/EB. Вычислим теперь периметр ABCD. Сумма периметров ABCD и EBC равна сумме периметра AED и 2BC, поэтому периметр ABCD равен 2p (EB + EC BC) = 2p 2kq.

Следовательно, отношение площади четырёхугольника ABCD к квадрату его периметра равно. Для описанного четырёхугольника AB C D такое отношение равно, поскольку для него k = 1. Остаётся доказать нераp q) потому что p > q). Неравенство (p k2 q)(p q) (p kq)2 верно, поскольку его можно привести к виду pq(1 k)2 0. Равенство достигается только при k = 1, т. е. в случае, когда четырёхугольник ABCD описанный.

б) Доказательство проведём индукцией по n. Для n = 4 утверждение доказано в задаче а). Доказательство шага индукции начнём с доказательства того, что при n 5 у любого n-угольника есть сторона, для которой сумма прилегающих к ней углов больше 180. Действительно, сумма всех пар углов, прилегающих к сторонам, равна удвоенной сумме углов n-угольника, поэтому сумма углов, прилегающих к одной из сторон, не меньше (n 2) · 360 /n 360 · 3/5 > 180.

442 Глава 22. Выпуклые и невыпуклые многоугольники Пусть для определённости сумма углов при вершинах A1 и A2 больше 180.

Тогда лучи An A1 и A3 A2 пересекаются в точке B (рис. 22.6). Рассмотрим также вспомогательный описанный n-угольник A1... An со сторонами, параллельными сторонам n-угольника A1... An. Обозначим точку пересечения лучей An A1 и A3 A2 через B. Для облегчения вычислений будем считать, что периметры (n 1)-угольников BA3 A4... An1 и B A3 A4... An1 одинаковы и равны P (этого можно добиться переходом к подобным многоугольникам).

Пусть r — радиус вписанной окружности многоугольника A1... An. Тогда площадь многоугольника B A3 A4... An1 равна rP/2. По предположению индукции площадь (n 1)-угольника BA3 A4... An1 не больше площади B A3 A4... An1, т. е. она равна arP/2, где a 1, причём a = 1 только в случае, когда многоугольник B A3 A4... An1 описанный.

Пусть площадь треугольника A1 A2 B равна S, а коэффициент подобия треугольников A1 A2 B и A1 A2 B равен k. Тогда площадь треугольника A1 A2 B равна k2 S. Ясно, что где q=A1 B +A2 B A1 A2. Поэтому площади многоугольников A1... An и A1... An равны r(P q)/2 и r(aP k2 q)/2, а их периметры равны P q и P kq.

Остаётся доказать, что причём равенство достигается только при a = 1 и k = 1 (если a = 1, то многоугольники BA3 A4... An1 и B A3 A4... An1 равны, а если при этом ещё и k = 1, то A1 A2 B = A1 A2 B, т. е. многоугольники A1... An и A1... An равны). Несложные вычисления показывают, что неравенство (P q)(aP k2 q) (P kq)2 эквивалентно неравенству Последнее неравенство справедливо, причём равенство достигается только при 22.20. Для любой невыпуклой фигуры существует выпуклая фигура того же периметра и большей площади (задачи 22.15 и 22.16). Поэтому можно ограничиться выпуклыми фигурами.

Пусть — выпуклая фигура, отличная от круга, K — круг. Нужно доказать, что для K отношение площади к квадрату периметра больше, чем для. Площадь и периметр и K можно определить как предел площадей и периметров описанных вокруг и K многоугольников, все внешние углы которых стремятся к нулю. Пусть некоторый многоугольник описан вокруг K. Рассмотрим другой многоугольник, соответственные стороны которого параллельны сторонам первого, а описан он вокруг.

Для первого многоугольника отношение площади к квадрату периметра больше, чем для второго (задача 22.19). Переходя к пределу, получаем, что отношение площади к квадрату периметра для K не меньше, чем для.

Если фигура периметра 1 отлична от круга, то её площадь не может равняться площади круга периметра 1, поскольку тогда существовала бы фигура периметра 1, площадь которой была бы больше площади (задача 22.18), т. е. больше площади круга периметра 1.

емого утверждения приведено в решении задачи 22.30 б).

22.21. Пусть K — круг, в который вписан многоугольник B1... Bn. Построим на каждой стороне Ai Ai+1 многоугольника A1... An внешним образом сегмент, равный сегменту, отсекаемому стороной Bi Bi+1 от круга K, и рассмотрим фигуру, состоящую из многоугольника A1... An и этих сегментов. Два таких сегмента могут пересечься только если Ai1 Ai Ai+1 Bi1 Bi Bi+1 > (рис. 22.7), а этого не может быть, поскольку многоугольник A1... An выпуклый. Поэтому Рис. 22. S = SA1...An + S и SK = SB1...Bn + S, где S — сумма площадей сегментов. Ясно также, что P = PK. Следовательно, согласно изопериметрическому неравенству SK S, т. е. SB1...Bn SA1...An, причём равенство достигается только в том случае, когда — круг, а многоугольник A1... An вписанный.

22.22. Добавим к данному многоугольнику многоугольник, симметричный ему относительно границы полуплоскости. Полученный многоугольник имеет площадь 2S и периметр 2L. Поэтому согласно изопериметрическому неравенству 2S (2L)2 /4p, т. е. S L2 /2p.

22.23. Рассмотрим кривую, делящую равносторонний треугольник ABC на две фигуры площади S/2. Возможны два случая: либо кривая отделяет одну из вершин треугольника (для определённости вершину A) от противоположной стороны, либо кривая замкнута. Во втором случае согласно задаче 22. длина кривой не меньше 2pS. Рассмотрим теперь первый случай. Образы кривой при последовательных симметриях относительно прямых AC, AB1, 444 Глава 22. Выпуклые и невыпуклые многоугольники C2 B Штейнеру выпуклого многоугольника M относительно прямой l. Нужно доказать, что отрезков является трапецией, целиком лежащей в M. При симметризации этой трапеции получается трапеция, лежащая в M. Отрезок AB принадлежит полученной трапеции, поэтому он принадлежит M.

22.25. Проведём через каждую вершину многоугольника M прямую, перпендикулярную прямой l. Эти прямые разрезают многоугольник на трапеции (некоторые из трапеций могут вырождаться в треугольники). При симметризации по Штейнеру каждая такая трапеция заменяется на равнобочную трапецию с теми же основаниями и той же высотой. Ясно, что при такой замене площадь трапеции не изменяется. Остаётся проверить, что периметр не увеличивается. При этом достаточно рассмотреть случай, когда трапеция вырождается в треугольник. Действительно, если ABCD — трапеция с основаниями AB и CD, где AB CD, то от неё можно отрезать параллелограмм ABCD.

Итак, пусть ABC — треугольник, у которого сторона AB фиксирована, а вершина C движется по прямой m, параллельной AB. Пусть точка B симметрична точке B относительно прямой m. Тогда AC + CB = AC + CB AB.

Равенство достигается тогда и только тогда, когда AC = CB.

22.26. Если XP = lXA + mXB, то AP = AX + XP = (l 1)XA + mXB = = (l 1 + m)XA + mAB. Поэтому вектор AP не зависит от выбора точки X тогда и только тогда, когда l 1 + m = 0. В этом случае AP = mAB, поэтому точка P лежит на прямой AB.

22.27. Пусть l1 A1 + l2 A2 и l1 B1 + l2 B2 — точки фигуры l1 M1 + l2 M2 (здесь Ai и Bi — точки многоугольника Mi ). Тогда фигура l1 M1 + l2 M2 содержит параллелограмм с вершинами l1 A1 + l2 A2, l1 B1 + l2 A2, l1 B1 + l2 B2, l1 A1 + l2 B2.

Выпуклость фигуры l1 M1 + l2 M2 следует из того, что она содержит диагональ этого параллелограмма.

Предположим, что многоугольники M1 и M2 лежат по одну стороны от некоторой прямой l. Будем сдвигать эту прямую параллельно самой себе до тех пор, пока она впервые не соприкоснётся с M1 и с M2 (вообще говоря, в разные моменты времени). Пусть a1 и a2 — длины отрезков, по которым l пересекает M1 и M2 в момент соприкосновения (ai = 0, если прямая l не параллельна сторонам многоугольника Mi ). Тогда в момент соприкосновения с фигурой l1 M1 + l2 M2 прямая l пересекает её по отрезку длины l1 a1 + l2 a2.

Число l1 a1 + l2 a2 отлично от нуля лишь в том случае, когда одно из чисел a1 и a2 отлично от нуля.

22.28. Выберем внутри многоугольника Mi точку Oi и разрежем его на треугольники с вершиной Oi ; многоугольник l1 M1 + l2 M2 разрежем на треугольники с вершиной O = l1 O1 + l2 O2. Снова, как и в решении задачи 22.27, возьмём прямую l и рассмотрим отрезки, по которым прямая l пересекает M1 и M2 в первые моменты соприкосновения. Пусть a1 и a2 — длины этих отрезков. Паре треугольников с основаниями a1 и a2 и высотами h1 и h соответствует треугольник с основанием l1 a1 + l2 a2 и высотой l1 h1 + l2 h2.

Остаётся заметить, что 22.29. Рассмотрим сначала случай, когда M1 и M2 — прямоугольники с параллельными сторонами. Пусть a1 и b1 — длины сторон прямоугольника M1, a2 и b2 — длины сторон прямоугольника M2 (сторона a1 параллельна стороне a2 ). Тогда l1 M1 + l2 M2 — прямоугольник со сторонами l1 a1 + l2 a и l1 b1 + l2 b2. Таким образом, нужно проверить неравенство т. е. a1 b2 + a2 b1 2 a1 a2 b1 b2. Это — неравенство между средним арифметическим и средним геометрическим двух чисел.

Рассмотрим теперь случай, когда многоугольник M1 устроен следующим образом: n 1 горизонтальных прямых разрезают его на n прямоугольников площади S1 /n; многоугольник M2 устроен аналогично. Тогда площадь суммы прямоугольников с одинаковыми номерами не меньше Каждая из таких сумм содержится в многоугольнике l1 M1 + l2 M2. Ясно также, что все n таких сумм прямоугольников не перекрываются, поскольку сумма полосы, ограниченной параллельными прямыми l1 и l1, и полосы, ограниченной параллельными прямыми l2 и l2, является полосой, ограниченной прямыми l1 l1 + l2 l2 и l1 l1 + l2 l2 (предполагается, что прямая l1 расположена выше прямой l1, а прямая l2 — выше l2 ). Следовательно, площадь многоугольника l1 M1 + l2 M2 не меньше (l1 S1 + l2 S2 )2.

Многоугольники M1 и M2 можно с любой точностью приблизить многоугольниками рассмотренного выше вида, поэтому требуемое неравенство в случае выпуклых многоугольников общего вида доказывается предельным З а м е ч а н и е. Неравенство S12 S1 S2 называют неравенством Брунна—Минковского в связи с тем, что Минковский доказал, что это неравенство обращается в равенство тогда и только тогда, когда многоугольники M1 и M гомотетичны.

22.30. а) Фигура l1 M + l2 D состоит из точек, удалённых не более чем на l2 R от многоугольника, гомотетичного M с коэффициентом l1. Площадь такой фигуры равна l2 S + l1 l2 PR + l2 pR2. (см. решение задачи 9.44).

б) Согласно неравенству Брунна т. е. PR 2 SpR2. Поэтому S P2 /4p.

446 Глава 22. Выпуклые и невыпуклые многоугольники 22.31. Если I1,..., In — отрезки, расположенные на плоскости, а O1,...

..., On — их середины, то многоугольник l1 I1 +... + ln In симметричен относительно точки l1 O1 +... + ln On.

Рассмотрим теперь выпуклый многоугольник A1... A2n с центром симметрии O. Перенесём отрезки A1 A2, A2 A3,..., An An+1 параллельно так, чтобы их середины попали в точку O. Увеличим эти отрезки в n раз, оставив их середины неподвижными. Пусть I1,..., In — полученные отрезки. Тогда сумма I1 +... + In — исходный многоугольник.

22.32. а) Обозначим данные фигуры через M1, M2, M3 и M4. Пусть Ai — точка пересечения всех фигур, кроме Mi. Возможны два варианта расположения точек Ai.

1. Одна из точек, например A4, лежит внутри треугольника, образованного остальными точками. Так как точки A1, A2, A3 принадлежат выпуклой фигуре M4, то и все точки треугольника A1 A2 A3 принадлежат M4. Поэтому точка A4 принадлежит M4, а остальным фигурам она принадлежит по своему определению.

2. A1 A2 A3 A4 — выпуклый четырёхугольник. Пусть C — точка пересечения диагоналей A1 A3 и A2 A4. Докажем, что точка C принадлежит всем данным фигурам. Обе точки A1 и A3 принадлежат фигурам M2 и M4, поэтому отрезок A1 A3 принадлежит этим фигурам. Аналогично отрезок A2 A4 принадлежит фигурам M1 и M3. Следовательно, точка пересечения отрезков A1 A3 и A2 A принадлежит всем данным фигурам.

б) Доказательство проведём индукцией по числу фигур. Для n = 4 утверждение доказано в предыдущей задаче. Докажем, что если утверждение верно для n 4 фигур, то оно верно и для n + 1 фигуры. Пусть даны выпуклые фигуры 1,..., n, n+1, каждые три из которых имеют общую точку.

Рассмотрим вместо них фигуры 1,..., n1, n, где n является пересечением n и n+1. Ясно, что фигура n тоже выпукла. Докажем, что любые три из новых фигур имеют общую точку. Сомнение в этом может возникнуть только для тройки фигур, содержащей n, но из предыдущей задачи следует, что фигуры i, j, n и n+1 всегда имеют общую точку. Следовательно, по предположению индукции 1,..., n1, n имеют общую точку, т. е. 1,..., n, n+1 имеют общую точку.

22.33. Круг радиуса 1 с центром O накрывает некоторые точки тогда и только тогда, когда круги радиуса 1 с центрами в этих точках содержат точку O. Поэтому наша задача допускает следующую переформулировку:

«На плоскости дано n точек, причём любые три круга радиуса 1 с центрами в этих точках имеют общую точку. Докажите, что все эти круги имеют общую точку». Это утверждение очевидным образом следует из теоремы Хелли.

22.34. а) Для каждой стороны AB данного многоугольника рассмотрим полосу, ограниченную перпендикулярами к прямой AB, проведёнными через точки A и B. К этому набору выпуклых фигур добавим ещё и сам многоугольник. По условию любые три из этих фигур имеют общую точку. Поэтому по теореме Хелли все они имеют общую точку.

б) Пусть ABCD — данный выпуклый четырёхугольник. Согласно задаче а) достаточно проверить, что требуемую точку O можно выбрать для любых трёх его сторон. Докажем, например, что её можно выбрать для сторон AB, BC и CD. Пусть X — множество всех точек четырёхугольника, для которых основания перпендикуляров, опущенных на стороны AB и CD, лежат на самих этих сторонах. По условию это множество не пусто. Рассмотрим три случая.

1) Углы B и C оба не тупые. Тогда нам подходит любая точка множества X.

2) Углы B и C оба тупые. Тогда нам подходит точка пересечения перпендикуляров к AB и CD, восставленных из точек B и C.

3) Угол B не тупой, а угол C тупой. Тогда нам подходит любая точка множества X, лежащая на перпендикуляре к прямой CD, восставленном из точки C.

22.35. Рассмотрим пятиугольники, остающиеся при выбрасывании пар соседних вершин семиугольника. Достаточно проверить, что любые три из них имеют общую точку. Для трёх пятиугольников выбрасывается не более шести различных вершин, т. е. одна вершина остаётся. Если вершина A не выброшена, то заштрихованный на рис. 22.9 треугольник принадлежит всем трём пятиугольникам.

22.36. Введём систему координат с осью Oy, параллельной данным отрезкам. Для каждого Рис. 22. отрезка рассмотрим множество всех таких точек (a, b), что прямая y = ax + b его пересекает. Достаточно проверить, что эти множества выпуклые, и применить к ним теорему Хелли. Для отрезка с концами (x0, y1 ) и (x0, y2 ) рассматриваемое множество является полосой, заключённой между параллельными прямыми ax0 + b = y и axo + b = y2.

22.37. Нет, не верно. Пример приведён на рис. 22.10.

22.38. Требуемые многоугольники и точки изображены на рис. 22.11.

22.39. Пусть из точки O виден весь контур многоугольника A1... An.

Тогда угол Ai OAi+1 не содержит других сторон многоугольника, кроме Ai Ai+1, 448 Глава 22. Выпуклые и невыпуклые многоугольники то утверждение очевидно. Предположим теперь, что внутренний угол многоугольника б) Из рис. 22.15 видно, как построить n-угольник, у которого ровно n диагонали лежат внутри его. Остаётся доказать, что у любого n-угольника есть по крайней мере n 3 диагонали. При n = 3 это утверждение очевидно.

Предположим, что утверждение верно для всех k-угольников, где k < n, и доРис. 22.14 Рис. 22. кажем его для n-угольника. Согласно задаче а) n-угольник можно разрезать диагональю на два многоугольника: (k + 1)-угольник и (n k + 1)-угольник, причём k + 1 < n и n k + 1 < n. У них имеется соответственно по крайней мере (k + 1) 3 и (n k + 1) 3 диагоналей, лежащих внутри. Поэтому у n-угольника имеется по крайней мере 1 + (k 2) + (n k 2) = n 3 диагоналей, лежащих внутри.

22.42. Докажем сначала, что если A и B — соседние вершины n-угольника, то из A или из B можно провести диагональ. Случай, когда внутренний угол многоугольника при вершине A больше 180, разобран в решении задачи 22.41 а). Предположим теперь, что угол при вершине A меньше 180.

Пусть B и C — вершины, соседние с A. Если внутри треугольника ABC нет других вершин многоугольника, то BC — диагональ, а если P — ближайшая к A вершина многоугольника, лежащая внутри треугольника ABC, то AP — диагональ. Следовательно, число вершин, из которых нельзя провести диагональ, не превосходит [n/2] (т. е. целой части числа n/2). С другой стороны, существуют n-угольники, для которых эта оценка достигается (рис. 22.16).

22.43. Докажем это утверждение индукцией по n. При n = 3 оно очевидно.

Предположим, что утверждение доказано для всех k-угольников, где k < n, и докажем его для любого n-угольника. Любой n-угольник можно разрезать диагональю на два многоугольника (см. задачу 22.41 а), причём число вершин у каждого из них строго меньше n, т. е. их можно разрезать на треугольники по предположению индукции.

22.44. Докажем это утверждение по индукции. При n = 3 оно очевидно.

Предположим, что оно доказано для всех k-угольников, где k < n, и докажем его для любого n-угольника. Любой n-угольник можно разрезать диагональю на два многоугольника (см. задачу 22.41 а). Если число сторон одного из них равно k + 1, то число сторон второго равно n k + 1, причём оба числа меньше n. Поэтому суммы углов этих многоугольников равны (k 1) · 180 и (n k 1) · 180 соответственно. Ясно также, что сумма углов n-угольника равна сумме углов этих многоугольников, т. е. она равна 22.45. Сумма всех углов полученных треугольников равна сумме углов многоугольника, т. е. она равна (n 2) · 180 (см. задачу 22.44). Поэтому количество треугольников равно n 2.

450 Глава 22. Выпуклые и невыпуклые многоугольники 22.46. Пусть ki — количество треугольников данного разбиения, у которых ровно i сторон является сторонами многоугольника. Требуется доказать, что k2 2. Число сторон n-угольника равно n, а число треугольников разбиения равно n 2 (см. задачу 22.45), поэтому 2k2 + k1 = n и k2 + k1 + k0 = n 2.

Вычитая из первого равенства второе, получаем k2 = k0 + 2 2.

22.47. Предположим, что существует тринадцатиугольник, у которого на любой прямой, содержащей сторону, есть ещё хотя бы одна сторона. Проведём через все стороны этого тринадцатиугольника прямые. Так как у него тринадцать сторон, то на одной из проведённых прямых лежит нечётное число сторон, т. е. на одной прямой лежат по крайней мере три стороны. У них есть 6 вершин и через каждую вершину проходит прямая, на которой лежат по крайней мере две стороны. Поэтому всего у этого тринадцатиугольника не менее 3 + 2 · 6 = 15 сторон, чего не может быть.

Для чётного n 10 требуемый пример — контур «звезды» (рис. 22.17, а);

идея построения примера для нечётного n показана на рис. 22.17, б.

22.48. Пусть k — число острых углов n-угольника. Тогда сумма его углов меньше k · 90 + (n k) · 360. С другой стороны, сумма углов n-угольника равна (n 2) · 180 (см. задачу 22.44), поэтому k · 90 + (n k) · 360 > (n 2) · 180, т. е. 3k < 2n + 4. Следовательно, k [2n/3] + 1, где через [x] обозначено наибольшее целое число, не превосходящее x.

Примеры n-угольников, имеющих [2n/3] + 1 острых углов, приведены на рис. 22.18.

22.49. При этих операциях векторы сторон многоугольника остаются теми же самыми;

изменяется только их порядок (рис. 22.19).

Поэтому имеется лишь конечное число многоугольников, которые могут получиться. Кроме того, после каждой операции площадь многоугольника строго возрастает. Следовательно, процесс конечен.

22.50. Доказательство проведём индукцией по n. При n = 3 утверждение очевидно.

Если одно из чисел ai, равно p, то шаг индукции очевиден, поэтому можно считать, что все числа ai отличны от p. Если n 4, ко для четырёхугольника. Значит, в любом случае, кроме параллелограмма (a1 = p a2 = a3 = p a4 ), найдутся два соседних числа, сумма которых больше p. Более того, найдутся такие числа ai и ai+1, что p < ai + ai+1 < 3p.

В самом деле, если все данные числа меньше p, то можно взять вышеукаРис. 22. 452 Глава 22. Выпуклые и невыпуклые многоугольники занную пару чисел; если же aj > p, то можно взять такие числа ai и ai+1, му по предположению индукции существует (n 1)-угольник M с углами Возможны три случая: 1) a* < p, 2) a* = p, 3) p < a* < 2p. В первом случае ai + ai+1 < 2p, поэтому одно из этих чисел, например ai, меньше p.

Если ai+1 < p, то отрежем от M треугольник с углами p ai, p ai+1, a* i (рис. 22.20, а), если ai+1 > p, то приставим к M треугольник с углами ai, ai+1 p, p a* (рис. 22.20, б). Во втором* случае отрежем от M трапецию с основанием, лежащим на стороне Ai1 Ai Ai+2 (рис. 22.20, в). В третьем случае ai + ai+1 > p, поэтому одно из этих чисел, например ai, больше p. Если ai+1 > p, то приставим к M треугольник с углами ai p, ai+1 p, 2p a* i (рис. 22.20, г), если ai+1 < p, то отрежем от M треугольник с углами 2p ai, p ai+1 и a* p (рис. 22.20, д).

ДЕЛИМОСТЬ, ИНВАРИАНТЫ, РАСКРАСКИ

1. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, связанной с состоянием системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т. е. система не может оказаться в состоянии с другим значением инварианта.

2. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах.

3. Наиболее простым и часто встречающимся инвариантом является чётность числа; инвариантом может быть также и остаток от деления не только на 2, но и на какое-нибудь другое число.

Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т. е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).

23.1. Может ли прямая пересекать (во внутренних точках) все стороны невыпуклого: а) (2n + 1)-угольника; б) 2n-угольника?

23.2. На плоскости дана замкнутая ломаная с конечным числом звеньев. Прямая l пересекает её в 1985 точках. Докажите, что существует прямая, пересекающая эту ломаную более чем в 1985 точках.

23.3. На плоскости лежат три шайбы A, B и C. Хоккеист бьёт по одной из шайб так, чтобы она прошла между двумя другими и остановилась в некоторой точке. Могут ли все шайбы вернуться на свои места после 25 ударов?

23.4. Можно ли окрасить на клетчатой бумаге 25 клеток так, чтобы у каждой из них было нечётное число окрашенных соседей? (Соседними клетками считаем те, у которых есть общая сторона.) 23.5*. Окружность разбита точками на 3k дуг: по k дуг длиной 1, 2 и 3. Докажите, что найдутся две диаметрально противоположные точки деления.

454 Глава 23. Делимость, инварианты, раскраски 23.6*. На плоскости дана несамопересекающаяся замкнутая ломаная, никакие три вершины которой не лежат на одной прямой.

особой, если продолжение одного из них пересекает другое. Докажите, что число особых пар чётно.

Вершинам исходного треугольника оставлены старые пометки, а дополнительные вершины получают номера 0, 1, 2, причём люРис. 23.1 бая вершина на стороне исходного треугольника должна быть помечена одной из пометок вершин этой стороны (рис. 23.1). Докажите, что существует треугольник разбиения, помеченный цифрами 0, 1, 2 (лемма Шпернера).

23.8*. Вершины правильного 2n-угольника A1... A2n разбиты на n пар. Докажите, что если n = 4m + 2 или n = 4m + 3, то две пары вершин являются концами равных отрезков.

23.9*. На рис. 23.2 изображён шестиугольник, разбитый на чёрные и белые треугольники так, что любые два треугольника имеют либо сторона шестиугольника является стороной одного из чёрных треугольников. Докажите, что десятиугольник разбить таким образом нельзя.

23.11. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна чёрная клетка?

23.12. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки, расположенные внутри квадрата размером 2 2. Может ли при этом на доске остаться ровно одна чёрная клетка?

23.13*. Дан выпуклый 2m-угольник A1... A2m. Внутри его взята точка P, не лежащая ни на одной из диагоналей. Докажите, что точка P принадлежит чётному числу треугольников с вершинами в точках A1,..., A2m.

23.14*. В центре каждой клетки шахматной доски стоит по фишке.

Фишки переставили так, что попарные расстояния между ними не уменьшились. Докажите, что в действительности попарные расстояния не изменились.

23.15*. Многоугольник разрезан на несколько многоугольников.

Пусть p — количество полученных многоугольников, q — количество отрезков, являющихся их сторонами, r — количество точек, являющихся их вершинами. Докажите, что p q + r = 1 (формула Эйлера).

23.16*. Выпуклый многоугольник разрезан на p треугольников так, что на их сторонах нет вершин других треугольников. Пусть n и m — количества вершин этих треугольников, лежащих на границе исходного многоугольника и внутри его.

а) Докажите, что p = n + 2m 2.

б) Докажите, что количество отрезков, являющихся сторонами полученных треугольников, равно 2n + 3m 3.

23.17*. Квадратное поле разбито на 100 одинаковых квадратных участков, 9 из которых поросли бурьяном. Известно, что бурьян за год распространяется на те и только те участки, у которых не менее двух соседних (т. е. имеющих общую сторону) участков уже поросли бурьяном. Докажите, что поле никогда не зарастёт бурьяном полностью.

23.18*. Докажите, что существуют равновеликие многоугольники, которые нельзя разбить на многоугольники (возможно, невыпуклые), переводящиеся друг в друга параллельным переносом.

23.19*. Докажите, что выпуклый многоугольник нельзя разрезать на конечное число невыпуклых четырёхугольников.

23.20*. Даны точки A1,..., An. Рассмотрим окружность радиуса R, содержащую некоторые из них. Построим затем окружность радиуса R с центром в центре масс точек, лежащих внутри первой окружности, и т. д. Докажите, что этот процесс остановится, т. е. окружности начнут совпадать.

§ 4. Вспомогательные раскраски в шахматном порядке 23.21. В каждой клетке доски 5 5 клеток сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикали) клетки. Обязательно ли при этом останется пустая клетка?

456 Глава 23. Делимость, инварианты, раскраски 23.22. а) Можно ли замостить костями домино размером шахматную доску размером 8 8, из которой вырезаны два противоположных угловых поля?

б)* Докажите, что если из шахматной доски размером 8 8 вырезаны две произвольные клетки разного цвета, то оставшуюся часть доски всегда можно замостить костями домино размером 1 2.

23.23. Докажите, что доску размером 10 10 клеток нельзя разрезать на фигурки в форме буквы T, состоящие из четырёх клеток.

23.24*. Детали полотна игрушечной железной дороги имеют форму четверти окружности радиуса R. Докажите, что последовательно присоединяя их концами так, чтобы они плавно переходили друг в друга, нельзя составить путь, у которого начало совпадает с концом, а первое и последнее звенья образуют тупик, 23.25*. В трёх вершинах квадрата находятся три кузнечика, играющие в чехарду. При этом если кузнечик A прыгает через кузнечика B, то после прыжка он оказывается на том же расстоянии от него, но, естественно, нескольких прыжков один из кузнечиков попасть в четвёртую вершину квадрата?

23.26*. Дан квадратный лист клетчатой бумаги размером 100 100 клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не Рис. 23. имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами обязательно выходят на границу. Докажите, что кроме вершин квадрата найдётся ещё узел (внутри квадрата или на границе), не принадлежащий ни одной ломаной.

§ 5. Другие вспомогательные раскраски 23.27. Правильный треугольник разбит на n2 одинаковых правильных треугольников (рис. 23.4). Часть из них занумерована числами 1, 2,..., m, причём треугольники с последовательными номерами имеют смежные стороны.

2 2. Вместо неё достали плитку 1 4. Докажите, что выложить дно коробки плитками 23.29. Из листа клетчатой бумаги размером 29 29 клеток вырезано 99 квадратиков размером 2 2 клетки. Докажите, что из него можно вырезать ещё один такой квадратик.

23.30. Выпуклый n-угольник разбит на треугольники непересекающимися диагоналями, причём в каждой его вершине сходится нечётное число треугольников. Докажите, что n делится на 3.

23.31. Можно ли шашечную доску размером 10 10 замостить плитками размером 1 4?

23.32. На клетчатой бумаге даны произвольные n клеток. Докажите, что из них можно выбрать не менее n/4 клеток, не имеющих общих точек.

23.33*. Докажите, что если вершины выпуклого n-угольника лежат в узлах клетчатой бумаги, а внутри и на его сторонах других узлов нет, то n 4.

23.34*. Из 16 плиток размером 1 3 и одной плитки 1 1 сложили квадрат со стороной 7. Докажите, что плитка 1 1 лежит в центре квадрата или примыкает к его границе.

23.35*. Картинная галерея представляет собой невыпуклый n-угольник. Докажите, что для обзора всей галереи достаточно [n/3] сторожей.

23.36. Плоскость раскрашена в два цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно 1.

23.37*. Плоскость раскрашена в три цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно 1.

23.38*. Плоскость раскрашена в семь цветов. Обязательно ли найдутся две точки одного цвета, расстояние между которыми равно 1?

23.39*. Точки сторон правильного треугольника раскрашены в два цвета. Докажите, что найдётся прямоугольный треугольник с вершинами одного цвета.

23.40*. Триангуляцией многоугольника называют его разбиение на треугольники, обладающее тем свойством, что эти треугольники либо имеют общую сторону, либо имеют общую вершину, либо не имеют общих точек (т. е. вершина одного треугольника не может лежать на стороне другого). Докажите, что треугольники триангуляции можно раскрасить в три цвета так, что имеющие общую сторону треугольники будут разного цвета.

23.41*. Многоугольник разрезан непересекающимися диагоналями на треугольники. Докажите, что вершины многоугольника можно раскрасить в три цвета так, что все вершины каждого из полученных треугольников будут разного цвета.

458 Глава 23. Делимость, инварианты, раскраски 23.42*. Несколько кругов одного радиуса положили на стол так, что никакие два не перекрываются. Докажите, что круги можно раскрасить в четыре цвета так, что любые два касающихся круга будут разного цвета.

См. также задачу 24.11.

23.1. а) Пусть прямая пересекает все стороны многоугольника. Рассмотрим все вершины, лежащие по одну сторону от неё. Каждой из этих вершин можно поставить в соответствие пару сторон, из неё выходящих. При этом получим разбиение всех сторон многоугольника на пары. Поэтому если прямая пересекает все стороны m-угольника, то m чётно.

б) Из рис. 23.5 видно, как построить 2n-угольник и прямую, пересекающую все его стороны, при любом n.

23.2. Прямая l задаёт две полуплоскости; одну из них будем называть верхней, а другую нижней. Пусть n1 (соответственно n2 ) — число вершин ломаной, лежащих на прямой l, для которых оба выходящих из них звена лежат в верхней (соответственно в нижней) полуплоскости, а m — число всех остальных точек пересечения прямой l и ломаной. Совершим обход ломаной, выйдя из некоторой точки, не лежащей на прямой l, и вернувшись в ту же точку. При этом мы переходим из одной полуплоскости в другую, только проходя через любую из m точек пересечения. Так как мы вернёмся в ту же точку, из которой начали обход, то m чётно. По условию n1 + n2 + m = 1985, поэтому число n1 + n2 нечётно; в частности, n1 = n2. Пусть для определённости n1 > n2. Проведём тогда в верхней полуплоскости прямую l1, параллельную l и удалённую от неё на расстояние меньшее, чем любое ненулевое расстояние от l до вершин ломаной (рис. 23.6). Число точек пересечения ломаной с прямой l1 равно 2n1 + m > n1 + n2 + m = 1985, т. е. l1 — искомая прямая.

23.3. Нет, не могут. После каждого удара изменяется ориентация (т. е. направление обхода) треугольника ABC.

23.4. Пусть на клетчатой бумаге окрашено несколько клеток и nk — число окрашенных клеток, имеющих ровно k окрашенных соседей. Пусть N — число общих сторон окрашенных клеток. Так как каждая из них принадлежит ровно двум окрашенным клеткам, то N = (n1 + 2n2 + 3n3 + 4n4 )/2 = (n1 + n3 )/2 + n2 + + n3 + 2n4. Поскольку N — целое число, то число n1 + n3 чётно.

Мы доказали, что число окрашенных клеток, имеющих нечётное число окрашенных соседей, всегда чётно. Поэтому нельзя окрасить 25 клеток так, чтобы у каждой из них было нечётное число окрашенных соседей.

23.5. Предположим, что окружность разбита на дуги указанным образом, причём диаметрально противоположных точек деления нет. Тогда против концов любой дуги длиной 1 не лежат точки разбиения, поэтому против неё лежит дуга длиной 3. Выбросим одну из дуг длиной 1 и противолежащую ей дугу длиной 3. При этом окружность разбивается на две дуги. Если на одной из них лежит m дуг длиной 1 и n дуг длиной 3, то на другой лежит m дуг длиной 3 и n дуг длиной 1. Общее количество дуг длиной 1 и 3, лежащих на этих двух «больших» дугах, равно 2(k 1), поэтому n + m = k 1. Так как кроме дуг длиной 1 и 3 есть только дуги с чётной длиной, то чётность длины каждой из двух рассматриваемых дуг совпадает с чётностью числа k 1. С другой стороны, длина каждой из них равна (6k 1 3)/2 = 3k 2.

Получено противоречие, так как числа k 1 и 3k 2 имеют разную чётность.

23.6. Возьмём соседние звенья AB и BC и назовём уголком угол, симметричный углу ABC относительно точки B (на рис. 23.7 уголок заштрихован). Такие же уголки можно рассмотреть для всех вершин ломаной. Ясно, что число особых пар равно числу точек пересечения звеньев с уголками. Остаётся заметить, что число звеньев ломаной, пересекающихся с одним уголком, чётно, так как по пути от A к C ломаная входит в уголок столько же раз, сколько выходит из него.

23.7. Рассмотрим отрезки, на которые разбита сторона 01. Пусть a — число отрезков вида 00, b — число отрезков вида 01. Для каждого отрезка рассмотрим число нулей, стоящих на его концах, и сложим все эти числа.

В итоге получим 2a + b. С другой стороны, все «внутренние» нули входят в эту сумму дважды, а есть ещё один нуль, стоящий в вершине исходного треугольника. Поэтому число 2a + b нечётно, т. е. b нечётно.

Перейдём теперь к разбиению треугольника. Пусть a1 — общее количество треугольников вида 001 и 011, а b1 — число треугольников вида 012. Для каждого треугольника рассмотрим число его сторон вида 01 и сложим все эти числа. В итоге получим 2a1 + b1. С другой стороны, все «внутренние»

стороны входят в эту сумму дважды, а все «граничные» лежат на стороне исходного треугольника и число их нечётно по предыдущему рассуждению.

Поэтому число 2a1 + b1 нечётно, в частности, b1 = 0.

23.8. Предположим, что все пары вершин задают отрезки разной длины. Отрезку Ap Aq поставим в соответствие наименьшее из чисел |p q| и 2n |p q|. В результате для данных n пар вершин получим числа 1, 2,..., n; пусть среди этих чисел k чётных и n k нечётных. Нечётным числам соответствуют отрезки Ap Aq, где числа p и q разной чётности. Поэтому 460 Глава 23. Делимость, инварианты, раскраски среди вершин остальных отрезков будет k вершин с чётными номерами и k вершин с нечётными номерами, причём отрезки соединяют вершины с номерами одной чётности. Следовательно, число k чётно. Для чисел n вида 4m, 4m + 1, 4m + 2 и 4m + 3 количество k чётных чисел равно 2m, 2m, 2m + и 2m + 1 соответственно, поэтому n = 4m или n = 4m + 1.

23.9. Предположим, что мы разбили десятиугольник требуемым образом.

Пусть n — число сторон чёрных треугольников, m — число сторон белых треугольников. Так как каждая сторона чёрного треугольника (кроме сторон многоугольника) является также и стороной белого треугольника, то n m = 10. С другой стороны, оба числа n и m делятся на 3. Получено противоречие.

23.10. Пусть Q — квадратный лист бумаги, L(Q) — сумма длин тех сторон клеток, которые лежат внутри его. Тогда L(Q) делится на 4, так как все рассматриваемые стороны разбиваются на четвёрки сторон, получающихся друг из друга поворотами на ±90 и 180 относительно центра квадрата.

Если квадрат Q разделён на квадраты Q1,..., Qn, то сумма длин отрезков деления равна L(Q) L(Q1 )... L(Qn ). Ясно, что это число делится на 4, так как числа L(Q), L(Q1 ),..., L(Qn ) делятся на 4.

23.11. При перекрашивании горизонтали или вертикали, содержащей k чёрных и 8 k белых клеток, получится 8 k чёрных и k белых клеток.

Поэтому число чёрных клеток изменится на (8 k) k = 8 2k, т. е. на чётное число. Так как чётность числа чёрных клеток сохраняется, из исходных 32 чёрных клеток мы не сможем получить одну чёрную клетку.

23.12. При перекрашивании квадрата 2 2, содержащего k чёрных и 4 k белых клеток, получится 4 k чёрных и k белых клеток. Поэтому число чёрных клеток изменится на (4 k) k = 4 2k, т. е. на чётное число. Так как чётность числа чёрных клеток сохраняется, из исходных 32 чёрных клеток мы не сможем получить одну чёрную клетку.

23.13. Диагонали разбивают многоугольник на несколько частей. Будем называть соседними те из них, у которых есть общая сторона. Ясно, что из любой внутренней точки многоугольника можно попасть в любую другую, переходя каждый раз только в соседнюю часть. Часть плоскости, лежащую вне многоугольника, также можно считать одной из этих частей. Число рассматриваемых треугольников для точек этой части равно нулю, поэтому достаточно доказать, что при переходе в соседнюю часть чётность числа треугольников сохраняется.

Пусть общая сторона двух соседних частей лежит на диагонали (или стороне) PQ. Тогда всем рассматриваемым треугольникам, кроме треугольников со стороной PQ, обе эти части одновременно либо принадлежат, либо не принадлежат. Поэтому при переходе из одной части в другую число треугольников изменяется на k1 k2, где k1 — число вершин многоугольника, лежащих по одну сторону от PQ, k2 — число вершин, лежащих по другую сторону от PQ.

Так как k1 + k2 = 2m 2, то число k1 k2 чётно.

23.14. Если хотя бы одно из расстояний между фишками увеличилось бы, то увеличилась бы и сумма всех попарных расстояний между фишками, но сумма всех попарных расстояний между фишками не изменяется при любой перестановке.