Глава 22. § -1  |	Оглавление |	Глава 23.

22.1.

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

Рис. 22.1

22.2. Рассмотрим выпуклую оболочку данных точек. Если она является четырех- или пятиугольником, то все ясно. Допустим теперь, что выпуклая оболочка является треугольником ABC, а точки D и E лежат внутри его. Точка E лежит внутри одного из треугольников ABD, BCD, CAD; пусть для определенности она лежит внутри треугольника ABD. Обозначим точку пересечения прямых CD и AB через H. Точка E лежит внутри одного из треугольников ADH и BDH. Если, например, E лежит внутри треугольника ADH, то AEDC - выпуклый четырехугольник (рис. 22.1).

22.3. Пусть выпуклая оболочка вершин данных n-угольников является m-угольником и j₁, ј, j_m - его углы. Так как к каждому углу выпуклой оболочки прилегает угол правильного n-угольника, то j_i і (1 – (2/n))p (справа стоит величина угла правильного n-угольника). Поэтому j₁ + ј + j_m і m(1 – (2/n))p  =  (m – (2m/n))p. С другой стороны, j₁ + ј + j_m  =  (m – 2)p. Следовательно, (m – 2)p і (m-(2m/n))p, т. е. m і n.

22.4.

Заметим сначала, что 50 треугольников достаточно. В самом деле, пусть D_k - треугольник, стороны которого лежат на лучах A_kA_k – 1 и A_kA_k + 1 и который содержит выпуклый многоугольник A₁јA₁₀₀. Тогда этот многоугольник является пересечением треугольников D₂, D₄, ј, D₁₀₀. С другой стороны,

Рис. 22.2

100-угольник, изображенный на рис. 22.2, нельзя представить в виде пересечения менее чем 50 треугольников. В самом деле, если три его стороны лежат на сторонах одного треугольника, то одна из этих сторон - сторона A₁A₂. Все стороны этого многоугольника лежат на сторонах n треугольников, поэтому 2n + 1 і 100, т. е. n і 50.

Рис. 22.3

22.6. Докажем сначала, что H - выпуклая фигура. Пусть точки A и B принадлежат H, т. е. A и B - середины отрезков C₁D₁ и C₂D₂, где C₁ и C₂ принадлежат F, a D₁ и D₂ принадлежат G. Нужно доказать, что весь отрезок AB принадлежит H. Ясно, что отрезки C₁C₂ и D₁D₂ принадлежат F и G соответственно. Геометрическим местом середин отрезков с концами на отрезках C₁C₂ и D₁D₂ является параллелограмм с диагональю AB (рис. 22.3); это следует из того, что геометрическим местом середин отрезков CD, где точка C фиксирована, а точка D перемещается по отрезку D₁D₂, является средняя линия треугольника CD₁D₂.

Возьмем на плоскости произвольную ось координат Ox. Опорным множеством многоугольника, соответствующим оси Ox, назовем множество его точек, проекции которых на эту ось имеют наибольшее значение (рис. 22.4). Выпуклый многоугольник задается своими опорными множествами для всех возможных осей Ox. Если опорными множествами F и G относительно некоторой оси являются отрезки длиной a и b, то опорным множеством H относительно той же оси будет отрезок длиной (a + b)/2 (здесь считается, что точка - отрезок с нулевой длиной). Поэтому пери-

Рис. 22.4 метр H равен (P₁ + P₂)/2, а число сторон H может принимать любое значение от наибольшего из чисел n₁ и n₂ до n₁ + n₂ в зависимости от того, для скольких осей оба опорных множества F и G одновременно являются сторонами, а не вершинами.

22.7. Мы докажем более общее утверждение. Пусть 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(p₁, q₁, r – 1) + 1, где p₁ = N(p – 1, q, r) и q₁ = N(p, q – 1, r). В самом деле, выбросим из N(p, q, r)¯элементного множества S один элемент и разобьем (r – 1)¯элементные подмножества оставшегося множества Sў на два семейства: семейство aў (соответственно bў) состоит из тех подмножеств, объединения которых с выброшенным элементом входят в семейство a (соответственно b). Тогда либо существует p₁-элементное подмножество множества Sў, все (r – 1)-элементные подмножества которого содержатся в  семействе aў, либо существует q₁-элементное подмножество, все (r – 1)-элементные подмножества которого содержатся в  семействе bў. Рассмотрим первый случай. Так как p₁ = N(p – 1, q, r), то либо существует q-элементное подмножество множества Sў, все r-элементные подмножества которого лежат в b (тогда эти q элементов искомые), либо существует (p – 1)-элементное подмножество множества Sў, все r-элементные подмножества которого содержатся в a (тогда эти p – 1 элементов вместе с выброшенным элементом искомые). Второй случай рассматривается аналогично.

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

22.8.

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

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

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

в) Два разбиения содержат 2(n – 3) диагоналей, поэтому в среднем из каждой вершины выходит

4(n – 3) n

= 4 –

12 n

диагоналей двух данных разбиений. При n і 13 это число больше 3, поэтому найдется вершины, из которой выходят по крайней мере 4 диагонали данных разбиений. Выбрав ее, можно сэкономить не одно, а четыре преобразования.

Рис. 22.5

22.9. Если многоугольник не треугольник и не параллелограмм, то у него найдутся две непараллельные несоседние стороны. Продолжив их до пересечения, получим новый многоугольник, содержащий исходный и имеющий меньшее число сторон. После нескольких таких операций получим треугольник или параллелограмм. Если получится треугольник, то все доказано; поэтому будем считать, что получился параллелограмм ABCD. На каждой его стороне лежит сторона исходного многоугольника, и одна из его вершин, например A, не принадлежит исходному многоугольнику (рис. 22.5). Пусть K - ближайшая к A вершина многоугольника, лежащая на AD, a KL - сторона, не лежащая на AD. Тогда многоугольник заключен внутри треугольника, образованного прямыми KL, BC и CD.

22.10.

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

22.11.

Доказательство проведем индукцией по n. При n = 3 доказательство очевидно. Рассмотрим теперь n-угольник A₁јA_n, где n і 4. Точка O лежит внутри некоторого треугольника A_pA_qA_r. Пусть A_k - вершина данного n-угольника, отличная от точек A_p, A_q и A_r. Выбросив вершину A_k, из n-угольника A₁јA_n получим (n – 1)-угольник, к которому можно применить предположение индукции. Кроме того, углы A_kOA_p, A_kOA_q и A_kOA_r не могут быть все острыми, так как сумма некоторых двух из этих углов больше 180°.

22.12.

Доказательство проведем индукцией по n. При n = 3 утверждение очевидно. Пусть n і 4. Фиксируем один остроугольный треугольник A_pA_qA_r и выбросим вершину A_k, отличную от вершин этого треугольника. К полученному (n – 1)-угольнику можно применить предположение индукции. Кроме того, если, например, точка A_k лежит на дуге A_pA_q и РA_kA_pA_r Ј РA_kA_qA_r, то треугольник A_kA_pA_r остроугольный. В самом деле, РA_pA_kA_r = РA_pA_qA_r, РA_pA_rA_k < РA_pA_rA_q и РA_kA_pA_r Ј 90°, а значит, РA_kA_pA_r < 90°.

22.13.

а) Обозначим данные фигуры через M₁, M₂, M₃ и M₄. Пусть A_i - точка пересечения всех фигур, кроме M_i. Возможны два варианта расположения точек A_i.

2. A₁A₂A₃A₄ - выпуклый четырехугольник. Пусть C - точка пересечения диагоналей A₁A₃ и A₂A₄. Докажем, что точка C принадлежит всем данным фигурам. Обе точки A₁ и A₃ принадлежат фигурам M₂ и M₄, поэтому отрезок A₁A₃ принадлежит этим фигурам. Аналогично отрезок A₂A₄ принадлежит фигурам M₁ и M₃. Следовательно, точка пересечения отрезков A₁A₃ и A₂A₄ принадлежит всем данным фигурам.

б) Доказательство проведем индукцией по числу фигур. Для n = 4 утверждение доказано в предыдущей задаче. Докажем, что если утверждение верно для n і 4 фигур, то оно верно и для n + 1 фигуры. Пусть даны выпуклые фигуры F₁,…, F_n, F_n + 1, каждые три из которых имеют общую точку. Рассмотрим вместо них фигуры F₁, …, F_n – 1, F_nў, где F_nў является пересечением F_n и F_n + 1. Ясно, что фигура F_nў тоже выпукла. Докажем, что любые три из новых фигур имеют общую точку. Сомнение в этом может возникнуть только для тройки фигур, содержащей F_nў, но из предыдущей задачи следует, что фигуры F_i, F_j, F_n и F_n + 1 всегда имеют общую точку. Следовательно, по предположению индукции F₁, ј, F_n – 1, F_nў имеют общую точку, т. е. F₁, ј, F_n, F_n + 1 имеют общую точку.

22.14.

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

22.15.

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

Рис. 22.6 Рис. 22.7

22.16.

Введем систему координат с осью Oy, параллельной данным отрезкам. Для каждого отрезка рассмотрим множество всех таких точек (a, b), что прямая y = ax + b его пересекает. Достаточно проверить, что эти множества выпуклые, и применить к ним теорему Хелли. Для отрезка с концами (x₀, y₁) и (x₀, y₂) рассматриваемое множество является полосой, заключенной между параллельными прямыми ax₀ + b = y₁ и ax_o + b = y₂.

22.17.

Не верно. Пример приведен на рис. 22.7.

22.18.

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

22.19.

Пусть из точки O виден весь контур многоугольника A₁јA_n. Тогда угол A_iOA_i + 1 не содержит других сторон многоугольника, кроме A_iA_i + 1, и поэтому точка O лежит внутри многоугольника (рис. 22.9). Любая точка X плоскости принадлежит одному из углов A_iOA_i + 1, поэтому из нее видна сторона A_iA_i + 1.

Рис. 22.8

22.20.

Так как у выпуклого n-угольника все внутренние углы меньше 180° и их сумма равна (n – 2) · 180°, то сумма внешних углов равна 360°, т. е. в случае выпуклого многоугольника достигается равенство.

Рис. 22.9 Рис. 22.10

22.21.

а) Если многоугольник выпуклый, то утверждение очевидно. Предположим теперь, что внутренний угол многоугольника при вершине A больше 180°. Видимая часть стороны видна из точки A под углом меньше 180°, поэтому из точки A видны части по крайней мере двух сторон. Следовательно, существуют лучи, выходящие из точки A, на которых происходит смена (частей) сторон, видимых из точки A (на рис. 22.11 изображены все такие лучи). Каждый из этих лучей задает диагональ, целиком лежащую внутри многоугольника.

Рис. 22.11 Рис. 22.12

мере n – 3 диагонали. При n = 3 это утверждение очевидно. Предположим, что утверждение верно для всех k-угольников, где k < n, и докажем его для 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.22.

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

Рис. 22.13

22.23.

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

22.24.

Докажем это утверждение по индукции. При n = 3 оно очевидно. Предположим, что оно доказано для всех k-угольников, где k < n, и докажем его для любого n-угольника. Любой n-угольник можно разрезать диагональю на два многоугольника (см. задачу 22.21, а)). Если число сторон одного из них равно k + 1, то число сторон второго равно n – k + 1, причем оба числа меньше n. Поэтому суммы углов этих многоугольников равны (k – 1) · 180° и (n – k – 1) · 180° соответственно. Ясно также, что сумма углов n-угольника равна сумме углов этих многоугольников, т. е. она равна (k – 1 + n – k – 1) · 180°  =  (n – 2) · 180°.

22.25.

Сумма всех углов полученных треугольников равна сумме углов многоугольника, т. е. она равна (n – 2) · 180° (см. задачу 22.24). Поэтому количество треугольников равно n – 2.

22.26.

Пусть k_i - количество треугольников данного разбиения, у которых ровно i сторон является сторонами многоугольника. Требуется доказать, что k₂ і 2. Число сторон n-угольника равно n, а число треугольников разбиения равно n – 2 (см. задачу 22.25), поэтому 2k₂ + k₁ = n и k₂ + k₁ + k₀ = n – 2. Вычитая из первого равенства второе, получаем k₂ = k₀ + 2 і 2.

22.27.

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

Рис. 22.14

22.28.

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

Рис. 22.15

Рис. 22.16

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

22.30. Доказательство проведем индукцией по n. При n = 3 утверждение очевидно. Если одно из чисел a_i, равно p, то шаг индукции очевиден, поэтому можно считать, что все числа a_i отличны от p. Если n і 4, то

1 n

n е i = 1

(ai + ai + 1) = 2(n – 2) p/n і p

, причем равенство достигается только для четырехугольника. Значит, в любом случае, кроме параллелограмма (a₁ = p – a₂ = a₃ = p – a₄), найдутся два соседних числа, сумма которых больше p. Более того, найдутся такие числа a_i и a_i + 1, что p < a_i + a_i + 1 < 3p. В самом деле, если все данные числа меньше p, то можно взять вышеуказанную пару чисел; если же a_j > p, то можно взять такие числа a_i и a_i + 1, что a_i < p и a_i + 1 > p. Пусть a_i^* = a_i + a_i + 1 – p. Тогда 0 < a_i^* < 2p, поэтому по предположению индукции существует (n – 1)-угольник M с  углами a₁, ј, a_i – 1, a_i^*, a_i + 2, ј, a_n.

Возможны три случая: 1) a_i^* < p, 2) a_i^* = p, 3) p < a_i^* < 2p. В первом случае a_i + a_i + 1 < 2p, поэтому одно из этих чисел, например a_i, меньше p. Если a_i + 1 < p, то отрежем от M треугольник с углами p – a_i, p – a_i + 1, a_i^* (рис. 22.17, а ), если a_i + 1 > p, то приставим к M треугольник с углами a_i, a_i + 1 – p, p – a_i^* (рис. 22.17, б ). Во втором случае отрежем от M трапецию с основанием, лежащим на стороне A_i – 1A_i^* A_i + 2 (рис. 22.17, в ). В третьем случае a_i + a_i + 1 > p, поэтому одно из этих чисел, например a_i, больше p. Если a_i + 1 > p, то приставим к M треугольник с углами a_i – p, a_i + 1 – p, 2p – a_i^* (рис. 22.17, г ), если a_i + 1 < p, то отрежем от M треугольник с углами 2p – a_i, p – a_i + 1 и a_i^* – p (рис. 22.17, д ).

Рис. 22.17

Глава 22. § -1  |	Оглавление |	Глава 23.

Copyright © 2002 МЦНМО

Внимание! Данное издание содержит опечатки! Исправленные исходные файлы книги и файлы нового издания доступны со страницы автора. Заказ книги: biblio@mccme.ru.