Формула. В. В. Прасолов задачи по планиметрии
 Скачать 6.7 Mb.
|
|
22.8. Мы докажем более общее утверждение. Пусть p, q и r — натуральные числа, причём p, q > r. Тогда существует число N = N(p, q, r), обладающее Решения задач 437 следующим свойством если все элементные подмножества элементного множества S произвольным образом разбиты на два непересекающихся семейства и b , то либо существует элементное подмножество множества S, все r-элементные подмножества которого содержатся в a , либо существует элементное подмножество, все элементные подмножества которого содержатся в b (теорема Рамсея). Требуемое утверждение легко следует из теоремы Рамсея. В самом деле, пусть N = N(n, 5, 4) и семейство состоит из тех четырёхэлементных подмножеств элементного множества точек, выпуклые оболочки которых — четы- рёхугольники. Тогда существует элементное подмножество данного множества точек, выпуклые оболочки любых четырёхэлементных подмножеств которого четырёхугольники, так как пятиэлементного подмножества, выпуклые оболочки любых четырёхэлементных подмножеств которого — треугольники, не существует (см. задачу. Остаётся воспользоваться результатом задачи Докажем теперь теорему Рамсея. Легко проверить, что в качестве N(p, q, 1), N(r, q, r) и N(p, r, r) можно взять числа p + q − 1, q и p со- ответственно. Докажем теперь, что если > и > тов качестве, q, r) можно взять число N(p 1 , q 1 , r − 1) + 1, где p 1 = N(p − 1, q, и q 1 = N(p, q − 1, r). В самом деле, выбросим из N(p, q, элементного множества один элемент и разобьём (r − элементные подмножества оставшегося множества на два семейства семейство соответственно состоит из тех подмножеств, объединения которых с выброшенным элементом входят в семейство соответственно b ). Тогда либо существует p 1 -элементное подмножество множества S 0 , все (r − элементные подмножества которого содержатся в семействе a 0 , либо существует элементное подмножество, все (r − элементные подмножества которого содержатся все- мействе b 0 . Рассмотрим первый случай. Так как p 1 = N(p − 1, q, r), то либо существует элементное подмножество множества S 0 , все элементные подмножества которого лежат в тогда эти q элементов искомые, либо существует (p − элементное подмножество множества S 0 , все элементные подмножества которого содержатся в тогда эти p − 1 элементов вместе с выброшенным элементом искомые. Второй случай рассматривается анало- гично. Итак, доказательство теоремы Рамсея можно провести индукцией по r, причём при доказательстве шага индукции используется индукция по + а) Пусть A и B — соседние вершины угольника. Рассмотрим разбиение угольника диагоналями, выходящими из вершины A, и разбиение диагоналями, выходящими из вершины B. У этих разбиений нет общих диагоналей, а каждое преобразование изменяет только одну диа- гональ. б) Индукцией по n легко доказать, что любое разбиение можно перевести в разбиение диагоналями, выходящими изданной вершины A, не более чем за n − 3 преобразования. Действительно, при n = 4 это очевидно. При n > всегда можно сделать одно преобразование так, чтобы появилась диагональ, выходящая из вершины A если такой диагонали не было. Эта диагональ разбивает угольник наугольник и угольник, где k + l = n + 2. Остаётся заметить, что (k − 3) + (l − 3) + 1 = n − 3. Глава 22. Выпуклые и невыпуклые многоугольники Ясно также, что если m диагоналей разбиения уже выходят из вершины то нужно не более n − 3 − m преобразований, те преобразований можно сэкономить. Если заданы два разбиения, то их можно перевести в разбиение диагоналями, выходящими из вершины A, за 2(n − 3) преобразований. Одно преобразование можно сэкономить, выбрав в качестве A вершину, из которой выходит одна из диагоналей одного из разбиений. Поэтому от любого разбиения можно перейти к любому другому не более чем за 2n − 7 преобразований (пройдя через разбиение диагоналями, выходящими из вершины в) Два разбиения содержат 2(n − 3) диагоналей, поэтому в среднем из каждой вершины выходит − 3) n = 4 диагоналей двух данных разбиений. При n > 13 это число больше 3, поэтому найдётся вершина, из которой выходят по крайней мере 4 диагонали данных разбиений. Выбрав е, можно Рис. сэкономить не одно, а четыре преобразования. 22.10. Если многоугольник не треугольники не параллелограмм, то у него найдутся две непараллель- ные несоседние стороны. Продолжив их до пересечения, получим новый многоугольник, содержащий исходный и имеющий меньшее число сторон. После нескольких таких операций получим треугольник или параллелограмм. Если получится треугольник, то всё доказано поэтому будем считать, что получился параллелограмм ABCD. На каждой его стороне лежит сторона исходного многоугольника, и одна из его вершин, например A, не принадлежит исходному многоугольнику (рис. 22.3). Пусть K — ближайшая к A вершина многоугольника, лежащая на AD, а KL — сторона, не лежащая на AD. Тогда многоугольник заключён внутри треугольника, образованного прямыми KL, BC и Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Согласно задаче 22.10 существуют прямые a, b и c, являющиеся продолжениями сторон данного угольника и образующие треугольник который содержит данный угольник. Пусть прямая l является продолжением какой-либо другой стороны данного угольника. Продолжения всех сторон угольника, кроме стороны, лежащей на прямой l, образуют выпуклый угольник, лежащий внутри треугольника T. По предположению индукции для этого (n − угольника найдётся n − 3 нужных треугольника. Кроме того, прямая l и две из прямых a, b и c тоже образуют нужный треугольник. З а меча ни е. Если точки A 2 , . . . , лежат на окружности с центром A 1 , причём ∠A 2 A 1 A n < и угольник A 1 . . . выпуклый, то для этого угольника существует ровно n − 2 нужных треугольников. 22.12. Доказательство проведём индукцией по n. При n = 3 доказательство очевидно. Рассмотрим теперь угольник A 1 . . . A n , где n > 4. Точка O лежит внутри некоторого треугольника A p A q A r . Пусть A k — вершина данного угольника, отличная от точек A p , и A r . Выбросив вершину A k , из угольника. . . получим (n − угольник, к которому можно применить предположе- Решения задач 439 ние индукции. Кроме того, углы A k OA p , и не могут быть все острыми, так как сумма некоторых двух из этих углов больше Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Пусть n > 4. Фиксируем один остроугольный треугольники выбросим вершину A k , отличную от вершин этого треугольника. К полученному угольнику можно применить предположение индукции. Кроме того, если, например, точка лежит на дуге и ∠A k A p A r 6 то треугольник остроугольный. В самом деле, ∠A p A k A r = ∠A p A q A r , ∠A p A r A k < и ∠A k A p A r 6 90 ◦ , а значит, ∠A k A p A r < а) Пусть ABCD — данный параллелограмм. В меньшем параллелограмме, гомотетичном ему, любой отрезок, параллельный стороне AB, строго меньше AB. Тоже самое верно не только для сторон, но и для диагоналей. Поэтому каждую из четырёх вершин параллелограмма должен покрывать свой параллелограмм. б) Пусть выпуклый многоугольник M отличен от параллелограмма. Воспользовавшись результатом задачи, выберем три стороны многоугольника, при продолжении которых образуется треугольник ABC, объемлющий многоугольник M. Затем выберем на этих трёх сторонах точки A 1 , и отличные от вершин многоугольника (точка лежит на прямой BC и т. д.). Наконец, выберем произвольную точку O внутри многоугольника M. Отрезки, и разрезают M натри части. Рассмотрим гомотетию с центром A. Если коэффициент этой гомотетии достаточно близок кто образ многоугольника M полностью покрывает ту часть, которую отрезают OB 1 и OC 1 . Две остальные части покрываются аналогично. 22.15. Для каждого направления проведём опорные прямые к фигуре и рассмотрим пересечение всех полуплоскостей, заданных этими прямыми и содержащих Ψ. В результате получим выпуклую фигуру Φ. Она содержит, поэтому её площадь больше. Кривая, ограничивающая Φ, отличается от кривой, ограничивающей Ψ, тем, что некоторые криволинейные участки (или ломаные) заменены прямолинейными отрезками. Поэтому периметр меньше периметра Пусть P и P 0 — периметры фигур Φ и Φ 0 , S и S 0 — их площади. При гомотетии с коэффициентом P/P 0 > 1 фигура переходит в фигуру, периметр которой равен P, а площадь равна (P/P 0 ) 2 S 0 > Пусть хорда AB делит фигуру Φ на две части и Φ 2 , периметры которых равны, а площадь больше площади Φ 2 . Тогда фигура, состоящая из и фигуры, симметричной относительно AB, имеет тот же периметр, что и Φ, но большую площадь. Полученная фигура может оказаться невыпуклой. В этом случае, пользуясь результатами задачи, можно построить выпуклую фигуру того же периметра и ещё большей площади. 22.18. Рассмотрим хорду AB, делящую пополам периметр фигуры Φ. Если делит фигуру Φ на две части разной площади, то согласно задаче 22.17 существует фигура Φ 0 , которая имеет тот же периметр, что и Φ, но большую площадь. Поэтому будем считать, что хорда AB делит фигуру Φ на две части равной площади. На границе Φ есть точка P, для которой ∠APB 6= поскольку иначе Φ — круг с диаметром AB. Займёмся построением требуемой фигуры Φ 0 . Построим прямоугольный треугольник с катетами PA и P 1 B 1 = PB и приставим к его катетам сегменты, отсекаемые Глава 22. Выпуклые и невыпуклые многоугольники хордами PA ирис. Если такой сегмент будет теперь разрезан прямой A 1 B 1 , то, отразив одну из его частей относительно точки пересечения границы с прямой A 1 B 1 , получим фигуру, лежащую по одну сторону от прямой A 1 B 1 . Сегменты, прилегающие к катетами, не могут пересечься, поскольку угол между опорными прямыми в точке равен 90 ◦ + (180 ◦ − ∠APB) < 270 ◦ B P A ϕ 1 ϕ 2 B 1 P 1 A 1 ϕ 1 ϕ 2 Рис. Пусть Φ 0 — фигура, состоящая из построенной нами фигуры и фигуры, симметричной ей относительно прямой A 1 B 1 . Тогда имеет тот же периметр, что и Φ, но большую площадь, так как 2 A 1 P 1 · B 1 P 1 > 1 2 AP · BP sin APB = Замечание. Этими рассуждениями мы не доказали, что среди всех фигур данного периметра наибольшую площадь имеет круг. Мы не доказывали, что среди всех фигур данного периметра есть фигура наибольшей площади. 22.19. Для всех подобных многоугольников отношение площади к квадрату периметра постоянно. Поэтому достаточно доказать, что среди всех выпуклых многоугольников сданными углами отношение площади к квадрату периметра будет наибольшим для описанного многоугольника. а) Рассмотрим сначала случай, когда четырёхугольник ABCD — параллелограмм с заданным углом a . Если его стороны равны a и b, то отношение площади к квадрату периметра равно sin a 4(a + b) 2 6 a + b 2 2 sin a 4(a + b) 2 = 1 16 sin a , причём равенство достигается только прите. в случае, когда ABCD ромб. Ромб является описанным четырёхугольником. Решения задач 441 Будем теперь считать, что ABCD — не параллелограмм. Тогда продолжения двух его сторон пересекаются. Пусть для определённости лучи AB и пересекаются в точке E. Проведём прямую B 0 C 0 k BC, касающуюся вписанной в треугольник AED окружности (рис. 22.5; точки и лежат на сторонах O E B 0 B A D C C 0 Рис. 22.5 AE и DE). Пусть r — радиус вписанной окружности треугольника AED, O — её центр. Тогда S EB 0 O + S EOC 0 − S OB 0 C 0 = r 2 (EB 0 + EC 0 − B 0 C 0 ) = где q = (EB 0 + EC 0 − B 0 C 0 )/2. Поэтому S AED − S EBC = S AED − k 2 S EB 0 C 0 = pr − где p — полупериметр треугольника AED, k = EB/EB 0 . Вычислим теперь периметр. Сумма периметров ABCD и EBC равна сумме периметра и 2BC, поэтому периметр ABCD равен 2p − (EB + EC − BC) = 2p − Следовательно, отношение площади четырёхугольника ABCD к квадрату его периметра равно − k 2 qr 4(p − kq) 2 . Для описанного четырёхугольника такое отношение равно − qr 4(p − q) 2 , поскольку для него k = 1. Остаётся доказать неравенство, те сократить на p − q можно, потому что p > q). Неравенство (p − k 2 q)(p − q) 6 (p − верно, поскольку его можно привести к виду − k) 2 6 0. Равенство достигается только прите. в случае, когда четырёхугольник ABCD описанный. б) Доказательство проведём индукцией по n. Для n = 4 утверждение доказано в задаче а. Доказательство шага индукции начнём с доказательства того, что при n > 5 у любого угольника есть сторона, для которой сумма прилегающих к ней углов больше 180 ◦ . Действительно, сумма всех пар углов, прилегающих к сторонам, равна удвоенной сумме углов угольника, поэтому сумма углов, прилегающих к одной из сторон, не меньше − 2) · 360 ◦ /n > 360 ◦ · 3/5 > 180 ◦ Глава 22. Выпуклые и невыпуклые многоугольники Пусть для определённости сумма углов при вершинах и больше Тогда лучи и пересекаются в точке B рис. 22.6). Рассмотрим также вспомогательный описанный угольник A 0 1 . . . со сторонами, параллельными сторонам угольника A 1 . . . A n . Обозначим точку пересечения лучей и A 0 3 A 0 через B 0 . Для облегчения вычислений будем считать, что периметры угольников BA 3 A 4 . . . и B 0 A 0 3 A 0 4 . . . одинаковы и равны этого можно добиться переходом к подобным многоугольникам 2 A 0 1 A 0 5 A 0 4 A 0 Рис. Пусть r — радиус вписанной окружности многоугольника A 0 1 . . . A 0 n . Тогда площадь многоугольника B 0 A 0 3 A 0 4 . . . равна rP/2. По предположению индукции площадь (n − угольника BA 3 A 4 . . . не больше площади 3 A 0 4 . . . A 0 n−1 , те. она равна a rP/2, где a 6 1, причём a = 1 только в случае, когда многоугольник B 0 A 0 3 A 0 4 . . . A 0 n−1 описанный. Пусть площадь треугольника A 0 1 A 0 равна S, а коэффициент подобия треугольников A 1 A 2 B и A 0 1 A 0 равен k. Тогда площадь треугольника равна k 2 S. Ясно, что = 1 2 rA 0 1 B 0 + 1 2 rA 0 2 B 0 − 1 2 rA 0 1 A 0 2 = 1 где q=A 0 1 B 0 +A 0 2 B 0 −A 0 1 A 0 2 . Поэтому площади многоугольников A 1 . . . и A 0 1 . . . равны r(P − q)/2 и r( a P − k 2 q)/2, а их периметры равны P − q и P − kq. Остаётся доказать, что a P − k 2 q (P − kq) 2 6 P − q (P − q) 2 = 1 P − q , причём равенство достигается только при a = 1 и k = 1 (если a = 1, то многоугольники BA 3 A 4 . . . и B 0 A 0 3 A 0 4 . . . равны, а если при этом ещё и k = 1, тот. е. многоугольники A 1 . . . и A 0 1 . . . равны. Несложные вычисления показывают, что неравенство (P − q)( a P − k 2 q) 6 6 (P − эквивалентно неравенству 6 Pq(1 − k) 2 + (1 − a )(P − q)P. Решения задач 443 Последнее неравенство справедливо, причём равенство достигается только при a = 1 и k = Для любой невыпуклой фигуры существует выпуклая фигура того же периметра и большей площади (задачи 22.15 и 22.16 ). Поэтому можно ограничиться выпуклыми фигурами. Пусть Φ — выпуклая фигура, отличная от круга, K — круг. Нужно до- казать, что для K отношение площади к квадрату периметра больше, чем для Φ. Площадь и периметр Φ и K можно определить как предел площадей и периметров описанных вокруг Φ и K многоугольников, все внешние углы которых стремятся к нулю. Пусть некоторый многоугольник описан вокруг K. Рассмотрим другой многоугольник, соответственные стороны которого параллельны сторонам первого, а описан он вокруг Для первого многоугольника отношение площади к квадрату периметра больше, чем для второго (задача. Переходя к пределу, получаем, что отношение площади к квадрату периметра для K не меньше, чем для Если фигура Φ периметра 1 отлична от круга, то её площадь немо- жет равняться площади круга периметра 1, поскольку тогда существовала Рис. бы фигура периметра 1, площадь которой была бы больше площади Φ (задача, те. больше площади круга периметра Замечание. Другое доказательство требуемого утверждения приведено в решении задачи K — круг, в который вписан многоугольник. Построим на каждой стороне A i A i+1 многоугольника A 1 . . . внешним образом сегмент, равный сегменту, отсекаемому стороной B i B i+1 от круга K, и рассмотрим фигуру состоящую из многоугольника A 1 . . . и этих сегментов. Два таких сегмента могут пересечься только если ∠A i−1 A i A i+1 − ∠B i−1 B i B i+1 > риса этого не может быть, поскольку многоугольник A 1 . . . выпуклый. Поэтому S A 1 ...A n + S и S K = S B 1 ...B n + S, где S — сумма площадей сегментов. Ясно также, что P Φ = P K . Следовательно, согласно изо- периметрическому неравенству S K > S Φ , те, причём равенство достигается только в том случае, когда Φ — круга многоугольник A 1 . . . A n вписанный. 22.22. Добавим к данному многоугольнику многоугольник, симметричный ему относительно границы полуплоскости. Полученный многоугольник имеет площадь 2S и периметр 2L. Поэтому согласно изопериметрическому неравенству, те Рассмотрим кривую, делящую равносторонний треугольник ABC на две фигуры площади S/2. Возможны два случая либо кривая отделяет одну из вершин треугольника (для определённости вершину A) от противоположной стороны, либо кривая замкнута. Во втором случае согласно задаче 22.20 длина кривой не меньше. Рассмотрим теперь первый случай. Образы кривой при последовательных симметриях относительно прямых AC, AB 1 , Глава 22. Выпуклые и невыпуклые многоугольники A B C B 1 C 2 B 2 C 1 Рис. 22.8 AC 2 , ирис) образуют замкнутую кривую, ограничивающую фигуру площади 3S. Поэтому искомая кривая — дуга окружности радиуса с центром в точке. Её длина равна Пусть симметризация по Штейнеру выпуклого многоугольника M относительно прямой l. Нужно доказать, что если A и B — точки M 0 , то весь отрезок принадлежит M 0 . Рассмотрим два отрезка, по которым пересекают прямые, проходящие через точки A и B перпендикулярно Эти прямые пересекают M по двум отрезкам такой же длины. Выпуклая оболочка этих отрезков является трапецией, целиком лежащей в M. При симметризации этой трапеции получается трапеция, лежащая в M 0 . Отрезок AB принадлежит полученной трапеции, поэтому он принадлежит M 0 22.25. Проведём через каждую вершину многоугольника M прямую, перпендикулярную прямой l. Эти прямые разрезают многоугольник на трапеции (некоторые из трапеций могут вырождаться в треугольники. При симметризации по Штейнеру каждая такая трапеция заменяется на равнобочную трапецию с теми же основаниями и той же высотой. Ясно, что при такой замене площадь трапеции не изменяется. Остаётся проверить, что периметр не увеличивается. При этом достаточно рассмотреть случай, когда трапеция вырождается в треугольник. Действительно, если ABCD — трапеция с основаниями и CD, где AB 6 CD, то от неё можно отрезать параллелограмм Итак, пусть ABC — треугольнику которого сторона AB фиксирована, а вершина C движется по прямой m, параллельной AB. Пусть точка симметрична точке B относительно прямой m. Тогда AC + CB = AC + CB 0 > Равенство достигается тогда и только тогда, когда AC = Если – XP = l # – XA + m # – XB, то – AP = # – AX + # – XP = ( l − 1) # – XA + m # – XB = = ( l − 1 + m ) # – XA + m # – AB. Поэтому вектор – AP не зависит от выбора точки тогда и только тогда, когда l − 1 + m = 0. В этом случае – AP = m # – AB, поэтому точка P лежит на прямой Пусть и l 1 B 1 + l 2 B 2 — точки фигуры l 1 M 1 + l 2 M 2 (здесь A i и B i — точки многоугольника M i ). Тогда фигура содержит параллелограмм с вершинами Выпуклость фигуры следует из того, что она содержит диагональ этого параллелограмма. Предположим, что многоугольники и лежат по одну стороны от некоторой прямой l. Будем сдвигать эту прямую параллельно самой себе до тех пор, пока она впервые не соприкоснётся си с вообще говоря, в разные моменты времени. Пусть и a 2 — длины отрезков, по которым пересекает ив момент соприкосновения (a i = 0, если прямая l не параллельна сторонам многоугольника M i ). Тогда в момент соприкосновения с фигурой прямая l пересекаете по отрезку длины Число отлично от нуля лишь в том случае, когда одно из чисел a 1 и отлично от нуля Решения задач 445 22.28. Выберем внутри многоугольника точку и разрежем его на треугольники с вершиной O i ; многоугольник разрежем натре- угольники с вершиной O = l 1 O 1 + l 2 O 2 . Снова, как ив решении задачи 22.27 , возьмём прямую l и рассмотрим отрезки, по которым прямая l пересекает M 1 и впервые моменты соприкосновения. Пусть и a 2 — длины этих отрезков. Паре треугольников с основаниями и и высотами и соответствует треугольник с основанием и высотой l 1 h 1 + l 2 h 2 Остаётся заметить, что) = l 2 1 a 1 h 1 + l 1 l 2 (a 1 h 2 + a 2 h 1 ) + l 2 Рассмотрим сначала случай, когда и M 2 — прямоугольники с параллельными сторонами. Пусть и b 1 — длины сторон прямоугольника, и b 2 — длины сторон прямоугольника сторона параллельна стороне a 2 ). Тогда l 1 M 1 + l 2 M 2 — прямоугольник со сторонами и l 1 b 1 + l 2 b 2 . Таким образом, нужно проверить неравенство те. Это — неравенство между средним арифметическими средним геометрическим двух чисел. Рассмотрим теперь случай, когда многоугольник устроен следующим образом n − 1 горизонтальных прямых разрезают его на n прямоугольников площади S 1 /n; многоугольник устроен аналогично. Тогда площадь суммы прямоугольников с одинаковыми номерами не меньше l 1 r S 1 n + l 2 r S 2 n 2 = 1 n ( l 1 p S 1 + l 2 p S 2 ) 2 Каждая из таких сумм содержится в многоугольнике l 1 M 1 + l 2 M 2 . Ясно также, что все n таких сумм прямоугольников не перекрываются, поскольку сумма полосы, ограниченной параллельными прямыми и l 0 1 , и полосы, ограниченной параллельными прямыми и l 0 2 , является полосой, ограниченной прямыми и l 1 l 0 1 + l 2 l 0 предполагается, что прямая расположена выше прямой l 0 1 , а прямая l 2 — выше l 0 2 ). Следовательно, площадь многоугольника не меньше Многоугольники и можно с любой точностью приблизить многоугольниками рассмотренного выше вида, поэтому требуемое неравенство в случае выпуклых многоугольников общего вида доказывается предельным переходом. З а меча ни е. Неравенство называют неравенством Брун- на—Минковского в связи стем, что Минковский доказал, что это неравенство обращается в равенство тогда и только тогда, когда многоугольники и M 2 гомотетичны. 22.30. а) Фигура l 1 M + l 2 D состоит из точек, удалённых не более чем на l 2 R от многоугольника, гомотетичного M с коэффициентом l 1 . Площадь такой фигуры равна l 2 1 S + l 1 l 2 PR + l 2 2 p R 2 . (см. решение задачи 9.44 ). б) Согласно неравенству Брунна l 2 1 S + l 1 l 2 PR + l 2 2 p R 2 > ( l 1 √ S те. Поэтому S 6 P 2 /4 p Глава 22. Выпуклые и невыпуклые многоугольники 22.31. Если I 1 , . . . , I n — отрезки, расположенные на плоскости, а O 1 , . . . . . . , O n — их середины, то многоугольник l 1 I 1 + . . . симметричен относительно точки l 1 O 1 + . . . Рассмотрим теперь выпуклый многоугольник A 1 . . . с центром симметрии. Перенесём отрезки A 1 A 2 , A 2 A 3 , . . . , параллельно так, чтобы их середины попали в точку O. Увеличим эти отрезки враз, оставив их середины неподвижными. Пусть I 1 , . . . , I n — полученные отрезки. Тогда сумма+ . . . + 1 n I n — исходный многоугольника) Обозначим данные фигуры через M 1 , M 2 , и M 4 . Пусть точка пересечения всех фигур, кроме M i . Возможны два варианта расположения точек A i 1. Одна из точек, например A 4 , лежит внутри треугольника, образованного остальными точками. Так как точки A 1 , A 2 , принадлежат выпуклой фигуре M 4 , то и все точки треугольника принадлежат M 4 . Поэтому точка принадлежит M 4 , а остальным фигурам она принадлежит по своему определению. A 1 A 2 A 3 A 4 — выпуклый четырёхугольник. Пусть C — точка пересечения диагоналей и A 2 A 4 . Докажем, что точка C принадлежит всем данным фигурам. Обе точки и принадлежат фигурами, поэтому отрезок A 1 A 3 принадлежит этим фигурам. Аналогично отрезок принадлежит фигурами. Следовательно, точка пересечения отрезков и принадлежит всем данным фигурам. б) Доказательство проведём индукцией по числу фигур. Для n = 4 утверждение доказано в предыдущей задаче. Докажем, что если утверждение верно для n > 4 фигур, то оно верно и для n + 1 фигуры. Пусть даны выпуклые фигуры Φ 1 , . . . , Φ n , Φ n+1 , каждые три из которых имеют общую точку. Рассмотрим вместо них фигуры Φ 1 , . . . , Φ n−1 , Φ 0 n , где является пересечением и Φ n+1 . Ясно, что фигура тоже выпукла. Докажем, что любые три из новых фигур имеют общую точку. Сомнение в этом может возникнуть только для тройки фигур, содержащей Φ 0 n , но из предыдущей задачи следует, что фигуры Φ i , Φ j , и всегда имеют общую точку. Следовательно, по предположению индукции Φ 1 , . . . , Φ n−1 , имеют общую точку, т. е. Φ 1 , . . . , Φ n , имеют общую точку. 22.33. Круг радиуса 1 с центром O накрывает некоторые точки тогда и только тогда, когда круги радиуса 1 с центрами в этих точках содержат точку O. Поэтому наша задача допускает следующую переформулировку: «На плоскости дано n точек, причём любые три круга радиуса 1 сцен- трами в этих точках имеют общую точку. Докажите, что все эти круги имеют общую точку. Это утверждение очевидным образом следует из теоремы Хелли. 22.34. а) Для каждой стороны AB данного многоугольника рассмотрим полосу, ограниченную перпендикулярами к прямой AB, проведёнными через точки A и B. К этому набору выпуклых фигур добавим ещё и сам многоугольник. По условию любые три из этих фигур имеют общую точку. Поэтому по теореме Хелли все они имеют общую точку. б) Пусть ABCD — данный выпуклый четырёхугольник. Согласно задаче а) достаточно проверить, что требуемую точку O можно выбрать для любых трёх его сторон. Докажем, например, что её можно выбрать для сторон AB, Решения задачи. Пусть X — множество всех точек четырёхугольника, для которых основания перпендикуляров, опущенных на стороны AB и CD, лежат на самих Рис. Рис. этих сторонах. По условию это множество не пусто. Рассмотрим три случая) Углы B и C оба не тупые. Тогда нам подходит любая точка множества X. 2) Углы B и C оба тупые. Тогда нам подходит точка пересечения перпендикуляров к AB и восставленных из точек B и C. 3) Угол B не тупой, а угол C тупой. Тогда нам подходит любая точка множества X, лежащая на перпендикуляре к прямой CD, восставленном из точки Рассмотрим пятиугольники, остающиеся при выбрасывании пар соседних вершин семиугольника. Достаточно проверить, что любые три из них имеют общую точку. Для трёх пятиугольников выбрасывается не более шести различных вершин, те. одна вершина остаётся. Если вершина не выброшена, то заштрихованный на рис. 22.9 треугольник принадлежит всем трём пя- тиугольникам. 22.36. Введём систему координат с осью параллельной данным отрезкам. Для каждого отрезка рассмотрим множество всех таких точек, что прямая y = ax + b его пересекает. Достаточно проверить, что эти множества выпуклые, и применить к ним теорему Хелли. Для отрезка с концами (x 0 , y 1 ) и (x 0 , y 2 ) рассматриваемое множество является полосой, заключённой между параллельными прямыми ax 0 + b = и ax o + b = Нет, неверно. Пример приведён на рис. Требуемые многоугольники и точки изображены на рис. Рис. Пусть из точки O виден весь контур многоугольника A 1 . . . Тогда угол не содержит других сторон многоугольника, кроме A i A i+1 , Глава 22. Выпуклые и невыпуклые многоугольники Рис. Рис. и поэтому точка O лежит внутри многоугольника (рис. 22.12). Любая точка X плоскости принадлежит одному из углов A i OA i+1 , поэтому из невидна сторона Так как у выпуклого угольника все внутренние углы меньше и их сумма равна (n − 2) · 180 ◦ , то сумма внешних углов равна 360 ◦ , те. в случае выпуклого многоугольника достигается равенство. Пусть теперь — выпуклая оболочка многоугольника N. Каждый угол M содержит меньший угол N, причём угол может быть только больше угла N, т. е. внешний угол N не меньше внешнего угла рис. 22.13). Поэтому, даже ограничившись только углами N, примыкающими к уг- лам M, мы уже получим не меньше а) Если многоугольник выпуклый, то утверждение очевидно. Предположим теперь, что внутренний угол многоугольника при вершине A больше 180 ◦ . Видимая часть стороны видна из точки A под углом меньше, поэтому из точки A видны части по крайней мере двух сторон. Следовательно, существуют лучи, выходящие из точки на которых происходит смена (частей) сторон, видимых из точки A на рис. изображены все такие лучи. Каждый из этих лучей задаёт диагональ, целиком лежащую внутри многоугольника. б) Из рис. 22.15 видно, как построить угольнику которого ровно n − диагонали лежат внутри его. Остаётся доказать, что у любого угольника есть по крайней мере n − 3 диагонали. При n = 3 это утверждение очевидно. Предположим, что утверждение верно для всех угольников, где k < n, и до- Рис. Рис. 22.15 Решения задач 449 кажем его для угольника. Согласно задаче а) угольник можно разрезать диагональю на два многоугольника (k + угольники+ 1)-угольник, причём k + 1 < n и n − k + 1 < n. У них имеется соответственно по крайней мере (k + 1) − 3 и (n − k + 1) − 3 диагоналей, лежащих внутри. Поэтому у угольника имеется по крайней мере 1 + (k − 2) + (n − k − 2) = n − 3 диагоналей, лежащих внутри. 22.42. Докажем сначала, что если A и B — соседние вершины n-угольника, то из A или из B можно провести диагональ. Случай, когда внутренний угол многоугольника при вершине A больше 180 ◦ , разобран в решении задачи а. Предположим теперь, что угол при вершине A меньше Пусть B и C — вершины, соседние с A. Если внутри треугольника ABC нет других вершин многоугольника, то BC — диагональ, а если P — ближайшая к A вершина многоугольника, лежащая внутри треугольника ABC, то AP диагональ. Следовательно, число вершин, из которых нельзя провести диагональ, не превосходит [n/2] те. целой части числа n/2). С другой стороны, существуют угольники, для которых эта оценка достигается (рис. Рис. Докажем это утверждение индукцией по n. При n = 3 оно очевидно. Предположим, что утверждение доказано для всех угольников, где k < и докажем его для любого угольника. Любой угольник можно разрезать диагональю на два многоугольника (см. задачу 22.41 а), причём число вершину каждого из них строго меньше n, те. их можно разрезать на треугольники по предположению индукции. 22.44. Докажем это утверждение по индукции. При n = 3 оно очевидно. Предположим, что оно доказано для всех угольников, где k < n, и докажем его для любого угольника. Любой угольник можно разрезать диагональю на два многоугольника (см. задачу 22.41 а). Если число сторон одного из них равно k + 1, то число сторон второго равно n − k + 1, причём оба числа меньше n. Поэтому суммы углов этих многоугольников равны (k − 1) · и (n − k − 1) · соответственно. Ясно также, что сумма углов угольника равна сумме углов этих многоугольников, те. она равна − 1 + n − k − 1) · 180 ◦ = (n − 2) · Сумма всех углов полученных треугольников равна сумме углов многоугольника, те. она равна (n − 2) · см. задачу. Поэтому количество треугольников равно n − 2. Глава 22. Выпуклые и невыпуклые многоугольники 22.46. Пусть k i — количество треугольников данного разбиения, у которых ровно i сторон является сторонами многоугольника. Требуется доказать, что 2. Число сторон угольника равно n, а число треугольников разбиения равно n − 2 (см. задачу, поэтому 2k 2 + k 1 = n и k 2 + k 1 + k 0 = n − Вычитая из первого равенства второе, получаем k 2 = k 0 + 2 > Предположим, что существует тринадцатиугольник, у которого на любой прямой, содержащей сторону, есть ещё хотя бы одна сторона. Прове- дм через все стороны этого тринадцатиугольника прямые. Так как у него тринадцать сторон, тона одной из проведённых прямых лежит нечётное число сторон, те. на одной прямой лежат по крайней мере три стороны. У них есть 6 вершин и через каждую вершину проходит прямая, на которой лежат по крайней мере две стороны. Поэтому всего у этого тринадцатиугольника не менее 3 + 2 · 6 = 15 сторон, чего не может быть. Для чётного n > 10 требуемый пример — контур звезды (рис. 22.17, а); идея построения примера для нечётного n показана на рис. 22.17, б. Рис. Пусть k — число острых углов угольника. Тогда сумма его углов меньше k · 90 ◦ + (n − k) · 360 ◦ . С другой стороны, сумма углов угольника равна см. задачу, поэтому k · 90 ◦ + (n − k) · 360 ◦ > (n − 2) · те. Следовательно, k 6 [2n/3] + 1, где через [x] обозначено наибольшее целое число, не превосходящее Примеры угольников, имеющих [2n/3] + 1 острых углов, приведены на рис. Рис. 22.18 Решения задач 451 Рис. При этих операциях векторы сторон многоугольника остаются теми же самыми; изменяется только их порядок (рис. Поэтому имеется лишь конечное число многоугольников, которые могут получиться. Кроме того, после каждой операции площадь многоугольника строго возрастает. Следовательно, процесс конечен. 22.50. Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Если одно из чисел равно то шаг индукции очевиден, поэтому можно считать, что все числа отличны от p . Если n > то) = 2(n − 2) p /n > p , причём равенство достигается только для четырёхугольника. Значит, в любом случае, кроме параллелограмма, найдутся два соседних числа, сумма которых больше. Более того, найдутся такие числа и a i+1 , что p < a i + a i+1 < В самом деле, если все данные числа меньше p , то можно взять вышеука- Рис. 22.20 Глава 22. Выпуклые и невыпуклые многоугольники занную пару чисел если же a j > p , то можно взять такие числа и что a i < p и. Пусть a * i = a i + a i+1 − p . Тогда 0 < a * i < 2 p , поэтому по предположению индукции существует (n − угольник M с углами a 1 , . . . , a i−1 , a * i , a i+2 , . . . Возможны три случая 1) a * i < p , 2) a * i = p , 3) p < a * i < 2 p . В первом случае a i + a i+1 < 2 p , поэтому одно из этих чисел, например a i , меньше Если a i+1 < p , то отрежем от M треугольник с углами риса, если a i+1 > p , то приставим к M треугольник с углами рис. 22.20, б. Во втором случае отрежем от M трапецию с основанием, лежащим на стороне рис. 22.20, в. В третьем случае a i + a i+1 > p , поэтому одно из этих чисел, например a i , больше p . Если a i+1 > p , то приставим к M треугольник с углами a i − p , a i+1 − p , рис. 22.20, г, если a i+1 < p , то отрежем от M треугольник с углами ирис, д ГЛАВА ДЕЛИМОСТЬ, ИНВАРИАНТЫ, РАСКРАСКИ Основные сведения. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, связанной с состоянием системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы. Ясно, что тогда в конечном состоянии значение инварианта будет тоже самое, что ив начальном, те. система не может оказаться в состоянии с другим значением инварианта. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах. Наиболее простыми часто встречающимся инвариантом является чёт- ность числа инвариантом может быть также и остаток отделения не только на 2, но и на какое-нибудь другое число. Для построения инвариантов иногда бывают полезны вспомогательные раскраски, те. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета 1. Чти нечёт 23.1. Может ли прямая пересекать (во внутренних точках) все стороны невыпуклого: а) (2n + угольника б) 2n-угольника? 23.2. На плоскости дана замкнутая ломаная с конечным числом звеньев. Прямая l пересекаете в 1985 точках. Докажите, что существует прямая, пересекающая эту ломаную более чем в 1985 точках. 23.3. На плоскости лежат три шайбы A, B и C. Хоккеист бьёт по одной из шайб так, чтобы она прошла между двумя другими и остановилась в некоторой точке. Могут ли все шайбы вернуться на свои места после 25 ударов? 23.4. Можно ли окрасить на клетчатой бумаге 25 клеток так, чтобы у каждой из них было нечётное число окрашенных соседей (Соседними клетками считаем те, у которых есть общая сторона.) 23.5*. Окружность разбита точками на 3k дуг по k дуг длиной 1, 2 и 3. Докажите, что найдутся две диаметрально противоположные точки деления Глава 23. Делимость, инварианты, раскраски 23.6*. На плоскости дана несамопересекающаяся замкнутая ломаная, никакие три вершины которой не лежат на одной прямой. Рис. 23.1 Назовём пару несоседних звеньев ломаной особой, если продолжение одного из них пересекает другое. Докажите, что число особых пар чётно. 23.7*. Вершины треугольника помечены цифрами 0, 1 и 2. Этот треугольник разбит на несколько треугольников таким образом, что никакая вершина одного треугольника разбиения не лежит на стороне другого. Вершинам исходного треугольника оставлены старые пометки, а дополнительные вершины получают номера 0, 1, 2, причём любая вершина на стороне исходного треугольника должна быть помечена одной из пометок вершин этой стороны (рис. 23.1). Докажите, что существует треугольник разбиения, помеченный цифрами 0, 1, 2 (лемма Шпернера). 23.8*. Вершины правильного угольника A 1 . . . разбиты на пар. Докажите, что если n = 4m + 2 или n = 4m + 3, то две пары вершин являются концами равных отрезков 2. Делимость 23.9*. На рис. 23.2 изображён шестиугольник, разбитый нач рные и белые треугольники так, что любые два треугольника имеют либо Рис. общую сторону (и тогда они окрашены в разные цвета, либо общую вершину, либо не имеют общих точек, а каждая сторона шестиугольника является стороной одного из чёрных треугольников. Докажите, что десятиугольник разбить таким образом нельзя. 23.10*. Квадратный лист клетчатой бумаги разбит на меньшие квадраты отрезками, идущими по сторонам клеток. Докажите, что сумма длин этих отрезков делится на 4. (Длина стороны клетки равна 1.) |