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

23.15. Пусть n — число вершин исходного многоугольника, n1,..., np — числа вершин полученных многоугольников (к вершинам данного многоугольника мы относим и все вершины других многоугольников, лежащие на его сторонах). Представим число r в виде r = n + r1 + r2, где r1 и r2 — количества вершин полученных многоугольников, лежащих на сторонах исходного многоугольника и внутри его. С одной стороны, сумма углов всех полученных многоугольников равна 23.16. а) С одной стороны, сумма всех углов полученных треугольников равна pp. С другой стороны, она равна (n 2)p + 2mp. Поэтому б) Воспользуемся результатом задачи 23.15. В рассматриваемой ситуации p = n + 2m 2 и r = n + m; требуется вычислить q. Согласно формуле Эйлера 23.17. Легко проверить, что длина границы всего заросшего бурьяном участка (или нескольких участков) не возрастает. В начальный момент она не превосходит 9 · 4 = 36, поэтому в конечный момент она не может быть равной 40.

23.18. Фиксируем на плоскости некоторый луч AB. Любому многоугольнику M поставим в соответствие число F(M) (зависящее от AB) следующим образом. Рассмотрим все стороны M, перпендикулярные AB, и каждой из них поставим в соответствие число ±l, где l — длина этой стороны и знак «плюс»

берётся, если мы, идя от этой стороны в направлении луча AB, попадаем внутрь M, а знак «минус» — если наружу (рис. 23.8). Сумму всех полученных чисел мы и обозначим F(M); если у M нет сторон, перпендикулярных AB, то F(M) = 0.

Легко видеть, что если многоугольник M разрезан на многоугольники M1 и M2, то F(M) = F(M1 ) + F(M2 ), а если M получен из M параллельным переносом, то F(M ) = F(M). Поэтому, если M1 и M2 можно разрезать на части, переводящиеся друг в друга параллельным переносом, то F(M1 ) = F(M2 ).

462 Глава 23. Делимость, инварианты, раскраски многоугольник M разрезан на невыпуклые четырёхугольники M1,..., Mn. Каждому многоугольнику N поставим в соответствие число f(N), равное разности между суммой его внутренних углов, меньших 180, и суммой углов, дополняющих числа A = f(M) и B = f(M1 ) +... + f(Mn ). Рассмотрим для этого все точки, являющиеся вершинами четырёхугольников M1,..., Mn. Их можно разбить на четыре типа.

1. Вершины многоугольника M. Эти точки дают одинаковые вклады в A и B.

2. Точки на сторонах многоугольника M или Mi. Вклад каждой такой точки в B на 180 больше, чем в A.

3. Внутренние точки многоугольника, в которых сходятся углы четырёхугольника, меньшие 180. Вклад каждой такой точки в B на 360 больше, чем в A.

4. Внутренние точки многоугольника M, в которых сходятся углы четырёхугольников, причём один из них больше 180. Такие точки дают нулевые вклады в A и B.

В итоге получаем A B. С другой стороны, A > 0, а B = 0. Неравенство A > 0 очевидно, а для доказательства равенства B = 0 достаточно проверить, что если N — невыпуклый четырёхугольник, то f(N) = 0. Пусть углы N равны a b g d. У любого невыпуклого четырёхугольника ровно один угол больше 180, поэтому f(N) = b + g + d (360 a) = a + b + g + d 360 = Получено противоречие, поэтому выпуклый многоугольник нельзя разрезать на конечное число невыпуклых четырёхугольников.

23.20. Пусть Sn — окружность, построенная на n-м шаге, On — её центр.

Рассмотрим величину Fn = (R2 On A2 ), где суммирование ведётся только по точкам, оказавшимся внутри окружности Sn. Будем обозначать точки, лежащие внутри окружностей Sn и Sn+1, буквами B с индексом; точки, лежащие внутри окружности Sn, но вне окружности Sn+1, буквами C, а точки, лежащие внутри окружности Sn+1, но вне окружности Sn, буквами D. Тогда Fn = (R2 On B2 ) + (R2 On C2 ) и Fn+1 = (R2 On+1 B2 ) + (R2 On+1 D2 ).

Так как точка On+1 является центром масс системы точек B и C, то On B2 + On C2 =qOn O2 + On+1 B2 + On+1 C2, где q — общее количество точек B и C. Следовательно, Fn+1 Fn = qOn O2 + (R2 On+1 D2 ) (R2 On+1 C2 ).

Все три слагаемых неотрицательны, поэтому Fn+1 Fn. В частности, Fn F1 >0, т. е. q > 0.

Центров масс различных наборов данных точек конечное число, поэтому различных положений окружностей Si конечное число. Следовательно, Fn+1 = Fn для некоторого n, а значит, qOn O2 = 0, т. е. On = On+1.

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

23.22. а) Вырезаны поля одного цвета, пусть для определённости чёрного.

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

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

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

23.23. Предположим, что доска 10 10 клеток разбита на такие фигурки. Каждая фигурка содержит либо 1, либо 3 чёрные клетки, т. е. всегда нечётное число. Самих фигурок должно быть 100/4 = 25 штук. Поэтому они содержат нечётное число чёрных клеток, а всего чёрных клеток 100/2 = 50 штук. Получено противоречие.

23.24. Разрежем плоскость на одинаковые квадраты со стороной 2R и раскрасим их в шахматном порядке. Впишем в каждый из них окружность. Тогда детали полотна можно считать расположенными на этих окружностях, причём движение поезда, идущего из начала в конец, происходит в белых клетках по часовой стрелке, а в чёрных — против (или наоборот; см. рис. 23.11). Поэтому тупик образоваться не может, так как по обоим звеньям тупика движение происходит в одну сторону.

464 Глава 23. Делимость, инварианты, раскраски на рис. 23.12, и раскрасим её в два цвета, как показано на этом рисунке (белые узлы на этом рисунке не закрашены; исходный кузнечики могут попасть только в белые узлы, т. е. при симметрии относительно белого узла белый узел переходит в белый. Для Ясно, что AA1 = 2AB = 2(me1 + ne2 ), поэтому A1 — чёрный узел. Таким образом, кузнечик не может попасть в четвёртую вершину квадрата.

23.26. Раскрасим узлы клетчатой бумаги в шахматном порядке (рис. 23.13).

Так как концы любого единичного отрезка разноцветны, то ломаная с одноцветными концами содержит нечётное число узлов, всех узлов границы (кроме вершин квадрата) выходят ломаные. Докажем, что тогда все ломаные вместе содержат чётное число узлов. Для этого достаточно доказать, что число ломаных с одноцветными концами чётно. Пусть на границе квадрата расположено 4m белых и 4n чёрных узлов (вершины квадрата не учитываются). Обозначим число ломаных, у которых оба конца белые, через k. Тогда Остаётся заметить, что квадратный лист бумаги размером 100 100 клеток содержит нечётное число узлов.

с последовательными номерами разноцветные. Поэтому быть только на 1 больше, чем белых. Следовательно, общее число занумерованных треугольников не превосходит n(n 1) + 1.

23.28. Раскрасим дно коробки в два цвета, как показано на рис. 23.15.

Тогда каждая плитка 2 2 покрывает ровно одну чёрную клетку, а плитка 1 4 покрывает 2 или 0. Поэтому чётность числа чёрных клеток дна коробки совпадает с чётностью числа плиток 2 2. Так как при замене плитки 2 2 на плитку 1 4 чётность числа плиток 2 2 изменится, выложить дно коробки плитками не удастся.

23.29. Заштрихуем на данном квадратном листе бумаги квадратики так, как показано на рис. 23.16. При этом получится 100 заштрихованных квадратиков. Каждый вырезанный квадратик задевает ровно один заштрихованный квадратик, поэтому хотя бы один заштрихованный квадратик остаётся целым, и его можно вырезать.

23.30. Если многоугольник разбит на части несколькими диагоналями, то эти части можно окрасить в два цвета так, чтобы части, имеющие общую сторону, были разного цвета. Это можно сделать следующим образом. Будем последовательно проводить диагонали. Каждая диагональ разбивает многоугольник на две части. В одной из них сохраняем раскраску, а другую перекрашиваем, заменяя везде белый цвет на чёрный, а чёрный — на белый.

Проделав эту операцию для всех нужных диагоналей, получим требуемую раскраску. Так как в нашем случае в каждой вершине сходится нечётное число треугольников, то при такой раскраске все стороны многоугольника будут принадлежать треугольникам одного цвета, например чёрного (рис. 23.17).

Обозначим число сторон белых треугольников через m. Ясно, что m делится на 3. Так как каждая сторона белого треугольника является также и стороной чёрного треугольника, а все стороны многоугольника являются сторонами чёрных треугольников, то число сторон чёрных треугольников равно n + m.

Поэтому n + m делится на 3, а поскольку m делится на 3, то и n делится на 3.

466 Глава 23. Делимость, инварианты, раскраски 23.31. Раскрасим доску в четыре цвета, как показано на рис. 23.18. Легко сосчитать, что клеток второго цвета 26, а четвёртого 24. Каждая плитка накрывает по одной клетке каждого цвета. Поэтому плитками 1 4 нельзя замостить доску 10 10, так как иначе клеток каждого цвета было бы поровну.

23.32. Раскрасим клетчатую бумагу в четыре цвета, как показано на рис. 23.19. Среди данных n клеток найдётся не менее n/4 одноцветных клеток, а одноцветные клетки не имеют общих точек.

23.33. Раскрасим узлы клетчатой бумаги в четыре цвета в том же порядке, в каком раскрашены клетки на рис. 23.19. Если n 5, то найдутся две одноцветные вершины n-угольника. Середина отрезка с концами в одноцветных узлах является узлом. Так как n-угольник выпуклый, то середина отрезка с концами в его вершинах лежит либо внутри его, либо на стороне.

23.34. Разобьём полученный квадрат на клетки размером 1 1 и раскрасим их в три цвета, как показано на рис. 23.20. Легко проверить, что плитки 1 3 можно разбить на два типа: плитка 1-го типа накрывает одну клетку 1-го цвета и две клетки 2-го цвета, а плитка 2-го типа накрывает одну клетку 2-го цвета и две клетки 3-го цвета. Предположим, что все клетки 1-го цвета накрыты плитками 1 3. Тогда плиток 1-го типа 9, а плиток 2-го типа 7.

Следовательно, они накрывают 9 · 2 + 7 = 25 клеток 2-го цвета и 7 · 2 = клеток 3-го цвета. Получено противоречие, поэтому одна из клеток 1-го цвета накрыта плиткой 1 1.

23.35. Разрежем данный n-угольник непересекающимися диагоналями на треугольники (см. задачу 22.43). Вершины n-угольника можно раскрасить в три цвета так, что все вершины каждого из полученных треугольников будут разного цвета (см. задачу 23.41). Вершин какого-нибудь цвета будет не более [n/3]; сторожей достаточно поставить в этих вершинах.

23.36. Рассмотрим правильный треугольник со стороной 1. Все три его вершины не могут быть разного цвета, поэтому две вершины имеют один цвет; расстояние между ними равно 1.

23.37. Предположим, что любые две точки, лежащие на расстоянии 1, окрашены в разные цвета. Рассмотрим правильный треугольник ABC со стороной 1; все его вершины разного цвета. Пусть точка A1 симметрична A относительно прямой BC. Так как A1 B = A1 C = 1, то цвет точки A1 отличен от цветов точек B и C, т. е. она окрашена тот же цвет, что и точка A. Эти рассуждения показывают, что если AA1 = 3, то точки A и A1 одного цвета.

Поэтому все точки окружности радиуса 3 с центром A одного цвета. Ясно, что на этой окружности найдутся две точки, расстояние между которыми равно 1. Получено противоречие.

23.38. Приведём пример раскраски плоскости в семь цветов, для которой расстояние между любыми двумя одноцветными точками не равно 1. Разобьём плоскость на равные шестиугольники со стороной a и окрасим их, как покаРис. 23. 468 Глава 23. Делимость, инварианты, раскраски зано на рис. 23.21 (точки, принадлежащие двум или трём шестиугольникам, можно красить в любой из цветов этих шестиугольников). Наибольшее расстояние между точками одного цвета, лежащими в одном шестиугольнике, не превосходит 2a, а наименьшее расстояние между точками одного цвета, лежащими в разных шестиугольниках, не меньше длины отрезка AB (см. рис. 23.21). Ясно, что 2 = AC2 + BC2 = 4a2 + 3a2 = 7a2 > (2a)2. Поэтому, если 2a < 1 < 7a, т. е. 1/ 7 < a < 1/2, то расстояние между точками одного цвета не может быть равно 1.

23.39. Предположим, что нет прямоугольного треугольника с вершинами одного цвета. Разделим каждую сторону правильного треугольника двумя точками на три равные части. Эти точки образуют правильный шестиугольник. Если две его противоположные вершины одного цвета, то все остальные вершины будут второго цвета, а значит, есть прямоугольный треугольник с вершинами второго цвета. Следовательно, противоположные вершины шестиугольника разноцветные. Поэтому найдутся две соседние разноцветные вершины; противоположные им вершины тоже разноцветные. Одна из этих пар разноцветных вершин лежит на стороне треугольника. Точки этой стороны, отличные от вершин шестиугольника, не могут быть ни первого, ни второго цвета. Получено противоречие.

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

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

23.42. Доказательство проведём индукцией по числу кругов n. При n = утверждение очевидно. Пусть M — любая точка, O — наиболее удалённый от неё центр круга. Тогда круг с центром O касается не более трёх других данных кругов. Выбросим его и раскрасим остальные круги согласно предположению индукции. Этот круг можно окрасить цветом, отличным от цветов касающихся его кругов.

ЦЕЛОЧИСЛЕННЫЕ РЕШЁТКИ

Рассмотрим на плоскости систему прямых, заданных уравнениями x = m и y = n, где m и n — целые числа. Эти прямые образуют решётку квадратов или целочисленную решётку. Вершины этих квадратов, т. е. точки с целочисленными координатами, называют узлами целочисленной решётки.

§ 1. Многоугольники с вершинами в узлах решётки 24.1*. Существует ли правильный треугольник с вершинами в узлах целочисленной решётки?

24.2*. Докажите, что при n = 4 правильный n-угольник нельзя расположить так, чтобы его вершины оказались в узлах целочисленной решётки.

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

24.4*. Существует ли замкнутая ломаная с нечётным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решётки?

24.5*. На клетчатой бумаге выбраны три точки A, B, C, находящиеся в вершинах клеток. Докажите, что если треугольник ABC остроугольный, то внутри его или на сторонах есть по крайней мере ещё одна вершина клетки.

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

См. также задачи 21.13, 23.33.

24.7*. Вершины многоугольника (не обязательно выпуклого) расположены в узлах целочисленной решётки. Внутри его лежит n узлов решётки, а на границе m узлов. Докажите, что его площадь равна n + m/2 1 (формула Пика).

470 Глава 24. Целочисленные решётки 24.8*. Последовательностью Фарея Fn называют возрастающую последовательность несократимых дробей a/b, где 0 < a < b n. Пусть a/b и c/d — соседние члены последовательности Фарея. Докажите, что |ad bc| = 1.

24.9*. Вершины треугольника ABC расположены в узлах целочисленной решётки, причём на его сторонах других узлов нет, а внутри его есть ровно один узел O. Докажите, что O — точка пересечения медиан треугольника ABC.

24.10*. Докажите, что квадрат со стороной n не может накрыть более (n + 1)2 точек целочисленной решётки.

24.11*. На бесконечном листе клетчатой бумаги N клеток окрашено в чёрный цвет. Докажите, что из этого листа можно вырезать конечное число квадратов так, что будут выполняться два условия:

1) все чёрные клетки лежат в вырезанных квадратах; 2) в любом вырезанном квадрате K площадь чёрных клеток составит не менее 0, и не более 0,8 площади K.

24.12*. Докажите, что для любого n существует окружность, внутри которой лежит ровно n целочисленных точек.

24.13*. Докажите, что для любого n существует окружность, на которой лежит ровно n целочисленных точек.

См. также задачи 21.1, 21.23, 23.4.

24.14*. Начало координат является центром симметрии выпуклой фигуры площадью более 4. Докажите, что эта фигура содержит хотя бы одну точку с целыми координатами, отличную от начала координат (Минковский).

24.15*. а) Во всех узлах целочисленной решётки, кроме одного, в котором находится охотник, растут деревья, стволы которых имеют радиус r. Докажите, что охотник не сможет увидеть зайца, находящегося от него на расстоянии больше 1/r.

б) Пусть n — натуральное число. Во всех точках целочисленной решётки, расположенных строго внутри окружности радиуса n2 + с центром в начале координат и отличных от начала координат, растут деревья радиуса r. Докажите, что если r <, то на указанной окружности есть точка, которую можно увидеть из начала координат.

24.16*. Внутри выпуклой фигуры с площадью S и полупериметром p нет точек целочисленной решётки. Докажите, что S p.

24.17*. Выпуклая фигура имеет площадь S и полупериметр p.

Докажите, что если S > np для некоторого натурального n, то содержит по крайней мере n целочисленных точек.

24.18*. Внутри выпуклой фигуры с площадью S и полупериметром p лежит n узлов решётки. Докажите, что n > S p.

24.1. Предположим, что вершины правильного треугольника ABC расположены в узлах целочисленной решётки. Тогда тангенсы всех углов, образованных сторонами AB и AC с линиями решётки, рациональны. При любом положении треугольника ABC сумма или разность некоторых двух = (tg a ± tg b)/(1 tg a tg b) — рациональное число. Получено противоречие.

24.2. Для n = 3 и n = 6 утверждение вытекает из предыдущей задачи, поэтому будем в дальнейшем считать, что n = 3, 4, 6. Предположим, что существуют правильные n-угольники с вершинами в узлах целочисленной решётки (n = 3, 4, 6). Среди всех таких n-угольников можно выбрать тот, у которого длина стороны наименьшая. (Для доказательства достаточно заметить, что если a — длина отрезка с концами в узлах решётки, то a = n2 + m2, где n и m — целые числа, поэтому длина отрезка с концами в узлах решётки может принимать лишь конечное число различных значений, меньших данного.) Пусть Ai Bi = Ai+1 Ai+2. Тогда B1... Bn — правильный n-угольник, вершины которого лежат в узлах целочисленной решётки, а его сторона меньше стороны правильного n-угольника A1... An. Для n = 5 это видно из рис. 24.1, а для n 7 — из рис. 24.2. Получено противоречие с выбором n-угольника A1... An.

24.3. Легко проверить, что треугольник с вершинами в точках с координатами (0, 0), (12, 16) и (12, 9) обладает требуемыми свойствами.

24.4. Предположим, что существует замкнутая ломаная A1... An с нечётным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решётки. Пусть ai и bi — координаты проекций вектора Ai Ai+1 на горизонтальную и вертикальную оси. Обозначим длину звена ломаной через c.

Тогда c2 = a2 + b2, поэтому c2 при делении на 4 даёт остаток 0, 1 или 2.

Если c2 делится на 4, то ai и bi делятся на 2 (это доказывается простым перебором всех возможных остатков, которые ai и bi дают при делении на 2).

Поэтому при гомотетии с центром A1 и коэффициентом 0,5 наша ломаная перейдёт в ломаную с меньшей длиной звена, вершины которой по-прежнему лежат в узлах решётки. После нескольких таких операций придём к ломаной, у которой c2 не делится на 4, т. е. даёт остаток 1 или 2. Разберём эти варианты, предварительно заметив, что a1 +... + am = b1 +... + bm = 0.

1. c2 при делении на 4 даёт остаток 2. Тогда числа ai и bi оба нечётны, поэтому число a1 +... + am нечётно и не может равняться нулю.

2. c2 при делении на 4 даёт остаток 1. Тогда одно из чисел ai и bi нечётно, а другое чётно, поэтому число a1 +... + am + b1 +... + bm нечётно и не может равняться нулю.

24.5. Построим прямоугольник со сторонами, идущими по линиям клетчатой бумаги, так, чтобы вершины A, B, C лежали на его сторонах. Ни одна из вершин A, B, C не может оказаться внутри этого прямоугольника, поскольку иначе угол при этой вершине был бы тупым. По крайней мере одна из точек A, B, C лежит на стороне прямоугольника, а не в его вершине, поскольку иначе треугольник ABC был бы прямоугольным. Пусть для определённости вершина A лежит на стороне прямоугольника. Введём на плоскости координаты, выбрав точку A в качестве начала координат, а эту сторону прямоугольника — в качестве оси Ox. Ось Oy направим так, чтобы прямоугольник лежал в полуплоскости y 0. Ни одна из вершин B и C не лежит на оси Ox, поскольку иначе угол при вершине A был бы тупым. Таким образом, если точки B и C имеют координаты (x1, y1 ) и (x2, y2 ), то y1, y2 1, а числа x1 и x2 имеют разные знаки. Поэтому точка с координатами (0, 1) лежит внутри треугольника ABC или на его стороне BC.

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

Горизонтальные линии решётки разрезают многоугольник на два треугольника с основаниями a1 и an и n 1 трапеций с основаниями a1 и a2, a2 и a3,..., an1 и an. Высоты этих треугольников и трапеций равны 1, поэтому сумма их площадей равна Для вертикальных линий доказательство аналогично.

24.7. Каждому многоугольнику M с вершинами в узлах целочисленной решётки поставим в соответствие число f(M) = ведётся по всем узлам решётки, принадлежащим M, а угол fi определяется следующим образом: fi = 2p для внутренней точки многоугольника, fi = p для граничной точки, отличной от вершины, и fi — угол при вершине, если данный узел — вершина. Легко видеть, что f(M) = n + =n+ Остаётся проверить, что число f(M) равно площади многоугольника M.

Пусть многоугольник M разрезан на многоугольники M1 и M2 с вершинами в узлах решётки. Тогда f(M) = f(M1 ) + f(M2 ), поскольку для каждого узла углы складываются. Поэтому если формула Пика верна для двух из многоугольников M, M1 и M2, то она верна и для третьего.

Если M — прямоугольник со сторонами p и q, направленными по линиям решётки, то В этом случае формула Пика справедлива. Разрезав прямоугольник M диагональю на треугольники M1 и M2 и воспользовавшись тем, что f(M) = f(M1 ) + + f(M2 ) и f(M1 ) = f(M2 ), легко доказать справедливость формулы Пика для любого прямоугольного треугольника с катетами, направленными по линиям решётки. Отрезав несколько таких треугольников от прямоугольника, можно получить любой треугольник (рис. 24.3).

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

24.8. Сопоставим каждой несократимой дроби a/b точку с координатами (a, b). Если a/b и c/d — соседние члены последовательности Фарея, то треугольник с вершинами (0, 0), (a, b) и (c, d) не содержит целочисленных точек, отличных от вершин. Действительно, если бы целочисленная точка (p, q) принадлежала этому треугольнику, то числа p и q не превосходили бы n и дробь p/q была бы заключена между a/b и c/d. Поэтому согласно формуле Пика площадь этого треугольника равна 1/2. С другой стороны, согласно задаче 12.78 его площадь равна |ad bc|.

24.9. Согласно формуле Пика SAOB = SBOC = SCOA = 1/2, а значит, O — точка пересечения медиан треугольника ABC (см. задачу 4.2).

24.10. Пусть M — выпуклая оболочка точек целочисленной решётки, покрытых квадратом со стороной n. Согласно формуле Пика её площадь равна p + 1, где p — количество целочисленных точек внутри M, q — количество целочисленных точек на границе M. Поэтому p + 1 n2.

Периметр M не превосходит периметра данного квадрата (задача 9.29 б).

Кроме того, расстояние между соседними целочисленными точками на границе M не меньше 1. Поэтому q 4n.

Сложив неравенства p + 1 n2 и 2n, получаем требуемое неравенство p + q (n + 1)2.

24.11. Возьмём какой-нибудь достаточно большой квадрат со стороной 2n так, чтобы все чёрные клетки лежали внутри его и составляли менее 0,2 его площади. Разрежем этот квадрат на четыре одинаковых квадрата. Каждый из них окрашен менее чем на 0,8. Те из них, которые окрашены более чем на 0,2, оставляем, а остальные режем дальше таким же образом. Полученные квадраты 2 2 будут окрашены на 1/4, 1/2, 3/4 или не будут окрашены вовсе. Из листа бумаги нужно вырезать те полученные квадраты, в которых 24.12. Докажем сначала, что на окружности с центром A = ( 2, 1/3) не может лежать более одной целочисленной точки. Если m и n — целые числа, то (m 2)2 + (n (1/3))2 = q 2m 2, где q — рациональное число. Поэтому из равенства следует, что m1 = m2. По теореме Виета сумма корней уравнения (n (1/3))2 = = d равна 2/3, поэтому лишь один корень может быть целочисленным.

Расположим теперь радиусы окружностей с центром A, проходящих через целочисленные точки, в порядке возрастания: R1 < R2 < R3 <... Если Rn < R < Rn+1, то внутри окружности радиуса R с центром A лежит ровно n целочисленных точек.

24.13. Докажем сначала, что уравнение x2 + y2 = 5k имеет ровно 4(k + 1) целочисленных решений. При k = 0 и k = 1 это утверждение очевидно. Докажем, что уравнение x2 + y2 = 5k имеет ровно восемь таких решений (x, y), что x и y не делятся на 5; вместе с 4(k 1) решениями вида (5a, 5b), где a и b — решение уравнения a2 + b2 = 5k2, они дают нужное количество решений. Эти решения получаются друг из друга перестановками x и y и изменениями знаков; мы будем называть их нетривиальными решениями.

Пусть x2 + y2 делится на 5. Тогда (x + 2y)(x 2y) = x2 + y2 5y2 тоже делится на 5. Поэтому одно из чисел x + 2y и x 2y делится на 5. Легко проверить также, что если x + 2y и x 2y делятся на 5, то x и y делятся на 5.

Если (x, y) — нетривиальное решение уравнения x2 +y2 =5k, то (x+2y, 2xy) и (x 2y, 2x + y) — решения уравнения x2 + h2 = 5k+1, причём ровно одно из них нетривиально. Докажем, что нетривиальное решение единственно с точностью до перестановки x и y и изменения знаков. Пусть (x, y) — нетриx y x + 2y являются решениями уравнения x + h = 5, но целочисленными будут пары ровно одного из этих видов, так как ровно одно из чисел x + 2y и x 2y делится на 5. При этом мы получим нетривиальное решение, потому что (x + 2y)(x 2y) = (x2 + y2 ) 5y2 при k 2 делится на 5, но не делится на 25. Таким образом, каждое из восьми нетривиальных решений уравнения x2 + y2 = 5k даёт восемь нетривиальных решений уравнения x2 + h2 = 5k1, причём для одной половины решений нужно воспользоваться формулами первого вида, а для другой половины решений — формулами второго вида.

Перейдём теперь непосредственно к решению задачи. Пусть n = 2k + 1.

Докажем, что на окружности радиуса 5k /3 с центром (1/3, 0) лежит ровно n целочисленных точек. Уравнение x2 + y2 = 52k имеет 4(2k + 1) целочисленных решений. Кроме того, 52k при делении на 3 даёт остаток 1, поэтому одно из чисел x и y делится на 3, а другое при делении на 3 даёт остаток ±1.

Следовательно, ровно в одной из пар (x, y), (x, y), (y, x) и (y, x) первое и второе числа дают при делении на 3 остатки 1 и 0 соответственно.

Поэтому уравнение (3z 1)2 + (3t)2 = 52k имеет ровно 2k + 1 целочисленных решений.

Пусть n = 2k. Докажем, что на окружности радиуса 5(k1)/2 /2 с центром (1/2, 0) лежит ровно n целочисленных точек. Уравнение x2 + y2 = 5k1 имеет ровно 4k целочисленных решений, причём одно из чисел x и y чётно, а другое нечётно. Поэтому уравнение (2z 1)2 + (2t)2 = 5k1 имеет ровно 2k целочисленных решений.

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

Если бы они не пересекались, то при любом n выполнялось бы неравенство (n + 1)2 S < 4(n + R)2, где S — площадь данной фигуры. Но так как S > 4, то n можно выбрать так, чтобы выполнялось неравенство (n + R)/(n + 1) < S/4.

Пусть теперь фигуры с центрами O1 и O2 имеют общую точку A (рис. 24.4). Докажем, что тогда середина M отрезка O1 O2 принадлежит обеим фигурам (ясно, что точка M имеет целые координаты).

Пусть O1 B = O2 A. Так как данная фигура центрально симметрична, точка B принадлежит фигуре с центром O1. Эта фигура выпукла, и точки A и B принадлежат ей, поэтому ей принадлежит также середина отрезка AB. Ясно, что середина отрезка AB совпадает с серединой отрезка O1 O2.

24.15. а) Пусть охотник находится в точке O, а заяц — в точке A; A1 — точка, симметричная A относительно O. Рассмотрим фигуру, содержащую все точки, расстояние от которых до отрезка AA1 не превосходит r (рис. 24.5). Достаточно доказать, что содержит хотя бы один узел решётки (если узел попадает в заштрихованную часть, то точка A принадлежит стволу дерева). Рис. 24. Площадь равна 4rh + pr2, где h — расстояние от охотника до зайца. Если h > 1/r, то 4rh + pr2 > 4. По теореме Минковского содержит целочисленную точку.

б) Рассмотрим прямоугольник с вершинами (0, 0), (0, 1), (n, 1) и (n, 0).

Покажем, что из начала координат можно увидеть точку (n, 1). Действительно, расстояния от точек (1, 0) и (n 1, 1) до прямой, проходящей через точки (0, 0) и (n, 1), равно. Поэтому деревья, растущие в этих точках, не пеn2 + ресекают указанную прямую. Остальные деревья её тем более не пересекают.

24.16. Прежде всего докажем, что если внутри выпуклой фигуры с площадью S и полупериметром p нет точек целочисленной решётки, то существует выпуклая фигура с площадью S = S и полупериметром p p, внутри которой нет точек целочисленной решётки и которая симметрична относительно прямых x = 1/2 и y = 1/2. Затем для фигуры мы докажем, Фигура строится по фигуре следующим образом. Сначала мы берём симметризацию по Штейнеру фигуры относительно прямой x = 1/2, а затем для полученной фигуры рассматриваем симметризацию по Штейнеру относительно прямой y = 1/2. При симметризации по Штейнеру снова получается выпуклая фигура (задача 22.24), её площадь не изменяется, а периметр не увеличивается (задача 22.25). Предположим, что промежуточная фигура содержит целочисленную точку (m, n). Эта фигура симметрична относительно прямой x = 1/2, поэтому она содержит точку (m + 1, n). Следовательно, прямая y = n пересекает фигуру по отрезку, длина которого не меньше |2m 1| 1. Но тогда фигура должна содержать целочисленную точку. Приходим к противоречию. Аналогично доказывается, что фигура не содержит целочисленных точек.

Докажем теперь, что S p. Для этого рассмотрим два случая.

1. Фигура не содержит точек (x, y), для которых x > 3/2 или y > 3/2.

Тогда фигура целиком содержится в фигуре, заштрихованной на рис. 24.6.

Нужно лишь объяснить, почему от квадрата со стороной 2 отрезаны угловые квадратики со стороной 1/2. Это связано с тем, что если для любой точки углового квадратика рассмотреть ещё точки, симметричные ей относительно прямых x = 1/2 и y = 1/2 и относительно точки (1/2, 1/2), то выпуклая оболочка этих четырёх точек будет содержать целочисленные точки (например, начало координат). Таким образом, S 3. Поэтому согласно изопериметрическому неравенству S /p 3/p < 1.

2. Фигура содержит точку (x, y), для которой x > 3/2 или y > 3/2.

Пусть для определённости наибольшая координата x точек фигуры равна но, что b < 1, поскольку иначе прямоугольник с вершинами (a, b), (a + 1, b), (a + 1, b + 1), (a, b + 1) содержал бы целочисленные точки. Часть фигуры, состоящая из точек (x, y), для которых x 1/2 и y 1/2, принадлежит трапеции, заштрихованной на рис. 24.7, поэтому площадь этой части 24.17. Согласно задаче 24.16 достаточно доказать, что если S > np, то можно разрезать на n выпуклых фигур, у каждой из которых площадь больше полупериметра. Применим индукцию по n. Для n = 1 утверждение очевидно. Предположим, что оно доказано для n; докажем его для n + 1.

Пусть S > (n + 1)p для некоторой фигуры. Разрежем эту фигуру прямой Пусть p1 и p2 — полупериметры этих фигур. Ясно, что p1 < p и p2 < p. Поэтому S1 > p > p1 и S2 > np > np2. Применив предположение индукции к фигуре 2, получаем требуемое.

24.18. Рассмотрим решётку, заданную уравнениями x = k + 1/2 и y = l + 1/2, где k и l — целые числа. Докажем, что каждый квадрат этой решётки даёт неотрицательный вклад в величину n S + p. Рассмотрим два случая.

1. Фигура содержит центр квадрата. Тогда n = 1 и S 1, поэтому 2. Фигура пересекает квадрат, но не содержит его центр. Докажем, что в этом случае S p. Если фигура целиком лежит в этом квадрате, то согласно изопериметрическому неравенству S /p 1/p < 1. Если рассматриваемая часть фигуры ограничена стороной квадрата и некоторой кривой, то согласно задаче 22.22 S /p 2S /p 2/p < 1. Поэтому остаётся рассмотреть случаи, когда рассматриваемая часть фигуры ограничена сторонами квадрата и кривой, соединяющей либо противоположные, либо смежные стороны квадрата. При этом можно считать, что центр O квадрата лежит на границе фигуры (рис. 24.8). Действительно, для кривой, соединяющей противоположные стороны, можно применить параллельный перенос, а для кривой, соединяющей смежные стороны, — гомотетию с центром в их общей вершине. В обоих случаях отношение S /p увеличится.

Так как расстояния от центра квадрата до его сторон равны 1/2, то 1/2. Проведя через точку O опорную прямую к данной фигуре, получим, что S 1/2.

Ясно также, что все вклады квадратов не могут быть одновременно нулевыми.

РАЗРЕЗАНИЯ, РАЗБИЕНИЯ, ПОКРЫТИЯ

1. Во всех задачах этой главы рассматриваются лишь прямолинейные разрезы.

2. Две фигуры называют равносоставленными, если одну из них можно разрезать на части и сложить из них вторую фигуру (нетрудно убедиться, что тогда и вторую фигуру можно разрезать на части, из которых можно сложить первую фигуру). Ясно, что равносоставленные фигуры имеют равные площади. Оказывается, что для многоугольников верно и обратное, т. е. любые два равновеликих многоугольника равносоставлены (см. задачу 25.8 б).

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

25.1. Разрежьте произвольный треугольник на 3 части и сложите из них прямоугольник.

25.2. Разрежьте произвольный треугольник на части, из которых можно составить треугольник, симметричный исходному относительно некоторой прямой (части переворачивать нельзя).

25.3. Разрежьте правильный треугольник шестью прямыми на части и сложите из них 7 одинаковых правильных треугольников.

25.4*. Разрежьте правильный шестиугольник на 5 частей и сложите из них квадрат.

25.5*. Разрежьте квадрат на 6 частей и сложите из них три одинаковых квадрата.

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

25.7*. Докажите, что любой прямоугольник можно разрезать на части и сложить из них прямоугольник со стороной 1.

25.8*. а) Докажите, что любой многоугольник можно разрезать на части и сложить из них прямоугольник со стороной 1.

480 Глава 25. Разрезания, разбиения, покрытия б) Даны два многоугольника равной площади. Докажите, что первый многоугольник можно разрезать на части и сложить из них второй.

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

§ 2. Разрезания на части, обладающие 25.9. Разрежьте фигуру, изображённую на рис. 25.1, на 4 равные части.

25.10. Существует ли треугольник, который можно разрезать:

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

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

Рис. 25. 5-угольник разрезать на два равных 5-угольника?

25.14*. Разрежьте произвольный тупоугольный треугольник на 7 остроугольных.

25.15*. Разрежьте разносторонний треугольник на 7 равнобедренных, три из которых равны.

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

§ 3. Свойства частей, полученных при разрезаниях 25.16. а) В выпуклом n-угольнике проведены все диагонали. Они разбивают его на несколько многоугольников. Докажите, что у каждого из них не более n сторон.

б)* Докажите, что если n чётно, то у каждого из полученных многоугольников не более n 1 сторон.

25.17. Докажите, что если n-угольник разрезан произвольным образом на k треугольников, то k n 2.

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

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

25.20*. В квадрате со стороной 1 проведено конечное число отрезков, параллельных его сторонам, причём эти отрезки могут пересекать друг друга. Сумма длин отрезков равна 18. Докажите, что площадь одной из частей, на которые разбит квадрат, не меньше 0,01.

25.21*. Треугольник, все углы которого не превосходят 120, разрезан на несколько треугольников. Докажите, что хотя бы у одного из полученных треугольников все углы не превосходят 120.

См. также задачи 4.54, 22.45, 22.46, 23.15, 23.30, 23.40, 23.41.

§ 4. Разрезания на параллелограммы 25.22*. Докажите, что следующие свойства выпуклого многоугольника F эквивалентны: 1) F имеет центр симметрии; 2) F можно разрезать на параллелограммы.

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

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

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

§ 5. Плоскость, разрезанная прямыми 25.26. 99 прямых разбивают плоскость на n частей. Найдите все возможные значения n, меньшие 199.

Пусть на плоскости проведено n попарно непараллельных прямых, никакие три из которых не пересекаются в одной точке. В задачах 25.27—25.31 рассматриваются свойства фигур, на которые эти прямые разбивают плоскость.

При этом фигуру называют p-звенной, если она ограничена p звеньями (т. е. отрезками или лучами).

25.27. Докажите, что при n = 4 среди полученных частей есть четырёхугольник.

25.28. а) Найдите число всех полученных фигур.

б) Найдите число ограниченных фигур, т. е. многоугольников.

25.29. а) Докажите, что при n = 2k среди полученных фигур не более 2k 1 углов.

б) Может ли при n = 100 среди полученных фигур быть только три угла?

482 Глава 25. Разрезания, разбиения, покрытия 25.30*. Докажите, что если среди полученных фигур есть p-звенная и q-звенная, то p + q n + 4.

25.31*. Докажите, что при n 3 среди полученных частей не менее (2n 2)/3 треугольников.

Откажемся теперь от предположения, что никакие три из рассматриваемых прямых не пересекаются в одной точке. Если P — точка пересечения двух или нескольких прямых, то количество прямых данной системы, проходящих через точку P, будем обозначать l(P).

25.32*. Докажите, что количество отрезков, на которые данные прямые разбиты точками их пересечения, равно n + l(P).

25.33*. Докажите, что количество частей, на которые данные прямые разбивают плоскость, равно 1 + n + (l(P) 1), причём среди этих частей 2n неограниченных.

25.34*. Части, на которые плоскость разрезана прямыми, раскрашены в красный и синий цвет так, что соседние части разного цвета (см. задачу 27.1). Пусть a — количество красных частей, b — количество синих частей. Докажите, что причём равенство достигается тогда и только тогда, когда красные области — треугольники и углы.

25.35*. Можно ли невыпуклый четырёхугольник разрезать двумя прямыми на 6 частей?

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

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

25.38*. Докажите, что для любого натурального n, где n 6, квадрат можно разрезать на n квадратов.

25.39*. Докажите, что выпуклый 22-угольник нельзя разрезать диагоналями на 7 пятиугольников.

25.40*. Можно ли разрезать правильный треугольник на выпуклых многоугольников так, чтобы любая прямая имела общие точки не более чем с 40 из них?

25.41*. Квадратный лист бумаги разрезают прямой на две части.

Одну из полученных частей разрезают на две части, и так делают несколько раз. Какое наименьшее число разрезаний нужно сделать, чтобы среди полученных частей оказалось 100 двадцатиугольников?

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

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

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

См. также задачи 23.18 и 23.19.

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

25.45*. Докажите, что треугольник можно разбить на отрезки.

25.46*. Докажите, что круг можно разбить на отрезки.

25.47*. Докажите, что плоскость можно разбить на отрезки.

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

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

25.50*. Дан выпуклый пятиугольник, все углы которого тупые.

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

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

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

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

25.53*. Длина проекции фигуры на любую прямую не превосходит 1. Верно ли, что можно накрыть кругом диаметра: а) 1;

б) 1,5?

25.54*. Докажите, что любые n точек на плоскости всегда можно накрыть несколькими непересекающимися кругами так, что сумма 484 Глава 25. Разрезания, разбиения, покрытия их диаметров меньше n и расстояние между любыми двумя из них больше 1.

25.55*. На круглом столе радиуса R расположено без наложений n круглых монет радиуса r, причём больше нельзя положить ни одной монеты. Докажите, что R/r 2 n + 1.

См. также задачи 20.13, 20.17, 20.28, 20.34, 22.5, 22.10, 22.33, 22.35.

§ 9. Замощения костями домино и плитками оставшуюся часть доски можно замостить плитками, изображёнными на рис. 25.3.

Рис. 25.2 25.58*. Вырежьте из обычной шахматной доски было замостить плитками размером 1 3.

25.59*. Прямоугольник размером 2n 2m замостили костями домино 1 2. Докажите, что на этот слой костей можно положить второй слой так, что ни одна кость второго слоя не совпадёт с костью первого слоя.

25.60*. Прямоугольник покрыт в два слоя карточками 1 2 (над каждой клеткой лежат ровно две карРис. 25. точки). Докажите, что карточки можно разбить на два непересекающихся множества, каждое из которых покрывает весь прямоугольник.

25.61*. а) Можно ли квадрат 6 6 замостить костями домино так, чтобы не было «шва», т. е. прямой, не разрезающей костей?

б) Докажите, что любой прямоугольник m n, где m и n больше и mn чётно, можно замостить костями домино так, чтобы не было «шва».

в) Докажите, что прямоугольник 6 8 можно замостить костями домино так, чтобы не было «шва».

25.62*. Имеется неограниченное количество плиток в форме многоугольника M. Будем говорить, что из этих плиток можно сложить паркет, если ими можно покрыть круг сколь угодно большого радиуса так, чтобы не было ни просветов, ни перекрытий.

а) Докажите, что если M — выпуклый n-угольник, где n 7, то паркет сложить нельзя.

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

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

§ 10. Расположение фигур на плоскости 25.63*. Докажите, что к квадрату нельзя приложить более 8 не налегающих друг на друга квадратов такого же размера.

25.1. Пусть A — наибольший угол треугольника ABC. Тогда углы B и C острые. Проведя разрезы через середины сторон AB и AC перпендикулярно BC, переставим полученные части, как показано на рис. 25.4.

25.2. Пусть A — наибольший угол треугольника. Разрежем треугольник ABC на равнобедренные треугольники и переставим их, как показано на рис. 25.5.

25.3. Сложим 7 одинаковых правильных треугольников, как показано на рис. 25.6.

Тогда ABC — правильный треугольник. Ясно, что заштрихованные треугольники равны.

Теперь легко понять, что на рис. 25. фактически изображено, как разрезать 486 Глава 25. Разрезания, разбиения, покрытия 25.4. Требуемые разрезы изображены на рис. 25.7. Отрезок AB равен стороне квадрата, площадь которого равна площади шестиугольника. Остальные разрезы проводятся очевидным образом.

25.5. Мы будем решать обратную задачу: разрежем три квадрата со стороной a и сложим из них квадрат со стороной 3a. Требуемые разрезы изображены на рис. 25.8.

25.6. На рис. 25.9 показано, как это сделать.

25.7. Нужно доказать, что если есть два прямоугольника со сторонами a, b и c, d, причём ab = cd = S, то первый прямоугольник можно разрезать на части и сложить из них второй. Пусть для определённости a b и c d. Тогда S b и a d. Отрежем от обоих прямоугольников по два прямоугольных треугольника с катетами a и c, как показано на рис. 25.10.Заштрихованные параллелограммы равновелики и имеют сторону длиной один параллелограмм можно разрезать на части и сложить из них второй (см. задачу 25.6).

25.8. а) Для решения этой задачи нужно воспользоваться результатами задач 22.43, 25.1 и 25.7. Сначала разрезаем многоугольник непересекающимися диагоналями на треугольники. Каждый из этих треугольников разрезаем на части и складываем из них прямоугольник. Полученные прямоугольники разрезаем на части и складываем из них прямоугольники со стороной 1.

Ясно, что из нескольких прямоугольников со стороной 1 можно сложить один прямоугольник со стороной 1.

б) Разрежем первый многоугольник на части и сложим из них прямоугольник со стороной 1. Так как второй многоугольник можно разрезать на части и сложить из них этот прямоугольник, то и прямоугольник можно разрезать на части и сложить из них второй многоугольник (при этом части, на которые был разрезан первый многоугольник, будут разрезаны на более мелкие части).

25.9. Требуемые разрезы изображены на рис. 25.11.

25.10. а) Существует. Из трёх одинаковых прямоугольных треугольников с углом 60 можно сложить один прямоугольный треугольник с углом 60 , как показано на рис. 25.12.

б) Требуемым образом можно разрезать любой прямоугольный треугольник (рис. 25.13).

488 Глава 25. Разрезания, разбиения, покрытия 25.11. а) Можно считать, что BC/AC = k > 1. Приложим к треугольнику ABC треугольники 1, 2, 3, 4 и 5 (см. рис. 25.14). Может оказаться,что треугольники 4 и 5 равны, т. е. k + k3 = k4. В этом случае дополним конструкцию треугольниками 6 и 7, а треугольник 5 заменим треугольником 8. Тогда треугольники 7 и 8 не равны, т. е. k6 = k + k3 + k5. В самом деле, так как б) Предположим, что правильный треугольник разрезан на неравные правильные треугольники. Стороны двух треугольников разбиения не могут совпадать. Будем рассматривать только стороны треугольников разбиения, лежащие внутри (не на границе) исходного треугольника; пусть N — число таких сторон. Возникает три типа вершин треугольников разбиения (см. рис. 25.15).

Из каждой вершины 1-го, 2-го и 3-го типа выходит соответственно 4, 12 и 6 сторон. Пусть n1, n2 и n3 — количества точек 1-го, 2-го и 3-го типа.

Тогда N = (4n1 + 12n2 + 6n3 )/2 = 2n1 + 6n2 + 3n3.

Каждой точке 3-го типа можно сопоставить 3 стороны (на рис. 25.15 это стороны AB, OP и OQ). Легко проверить, что каждая сторона будет соответствовать хотя бы одной точке 3-го типа. Следовательно, N 3n3, а значит, 2n1 + 6n2 0. В частности, n1 = 0, т. е. разбиение состоит лишь из исходного треугольника.

25.12. Требуемые разрезы изображены на рис. 25.16; пунктирные полуокружности показывают, что все полученные треугольники остроугольные.

25.13. Да, можно. См. рис. 25.17, а или рис. 25.17, б.

25.14. Пусть ACB > 90 и O — центр вписанной окружности S треугольника ABC. Проведём к S касательные через точки пересечения S с отрезками OA и OB и обозначим получившиеся углы, как показано на рис. 25.18. Последовательно вычисляя углы, получаем, что f1 =(pa)/2 10002. Ясно, что можно отсекать не все треугольники, чтобы получить ровно 1000000 многоугольников.

25.41. Ясно, что после n разрезаний получится n + 1 кусок. Так как после каждого разрезания общее число вершин полученных фигур увеличивается на 2, 3 или 4, то после n разрезаний общее число вершин не превосходит 4n + 4.

Если после n разрезаний получилось сто 20-угольников, то кроме 20-угольников есть ещё n + 1 100 кусков, так как общее число кусков равно n + 1.

Поскольку у каждого куска не менее трёх вершин, общее число вершин не меньше 100 · 20 + (n 99) · 3 = 1703 + 3n. Следовательно, 1703 + 3n 4n + 4, т. е. n 1699.

Остаётся доказать, что за 1699 разрезаний можно разрезать квадрат требуемым образом. Чтобы разрезать квадрат на 100 прямоугольников, достаточно 99 разрезов, а чтобы отрезать от каждого из этих прямоугольников по 16 треугольников и превратить их в 20-угольники, достаточно 1600 разрезов.

25.42. а) Предположим, что из нескольких попарно различных по величине квадратов сложен прямоугольник. Рассмотрим самый маленький квадрат Q.

С одной из его сторон имеет общую часть сторона некоторого большего квадрата A. Сторона квадрата A выходит за пределы стороны квадрата Q.

Образовавшийся угол должен быть заполнен некоторым квадратом B, сторона которого снова больше стороны квадрата Q. Получаем ещё один угол, который должен быть заполнен квадратом C, а затем ещё один угол, который должен быть заполнен квадратом D. При этом между квадратами A и D не может быть «колодца» (т. е. квадраты A и D должны иметь общую границу), поскольку иначе для заполнения «колодца» потребовался бы квадрат, который меньше самого маленького квадрата Q.

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

Пусть q, a, b, c, d — длины сторон квадратов. Тогда a = b + q, b = c + q, c = d + q, d = a + q. Сложив эти равенства, получим 5q = 0. Этого не может быть.

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

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

Но тогда у квадратов D и E есть общая стороны, поэтому они равны. А по условию все квадраты попарно различны.

25.43. Введём систему координат с началом в одной из вершин исходного прямоугольника и осями, направленными по его сторонам. Разрежем координатную плоскость прямыми x = n/2 и y = m/2, где m и n — целые числа, и раскрасим полученные части в шахматном порядке. Если стороны прямоугольника параллельны осям координат, а длина одной из его сторон равна 1, то суммы площадей его белых и чёрных частей равны. В самом деле, для каждого отрезка длины 1, параллельного одной из сторон прямоугольника, длина его белой части равна длине чёрной части. Для прямоугольника с целочисленной стороной справедливо аналогичное утверждение, потому что его можно разрезать на прямоугольники со стороной 1. Остаётся доказать, что если суммы площадей белых и чёрных частей равны, то одна из сторон прямоугольника целочисленная. Предположим, что обе стороны исходного прямоугольника не целые. Прямые x = m и y = n разрезают его на три прямоугольника, одна из сторон каждого из которых имеет целую длину, и прямоугольник, обе стороны которого меньше 1. Легко проверить, что в последнем прямоугольнике суммы площадей белых и чёрных частей не могут быть равны.

25.44. Возьмём на сторонах AB и DC точки Mt и Nt так, что AMt : Mt B = = DNt : Nt C = t : (1 t), где 0 < t < 1. Тогда семейство отрезков Mt Nt, а также отрезки AD и BC образуют искомое разбиение (рис. 25.28).

25.45. Возьмём на стороне AC треугольника ABC точку D. «Вырожденный четырёхугольник» ABCD можно разбить на отрезки, как это делалось в предыдущей задаче (рис. 25.29).

25.46. Разделим диаметр AB точками C, D, E и F на 5 равных частей.

Пусть точки Mt и Pt лежат на отрезках CD и EF, причём CMt : Mt D = = FPt : Pt E = t : (1 t), где 0 < t < 1, а точки Qt и Nt лежат на разных дугах окружности, заданных точками A и B, и делят эти дуги в отношении t : (1 t) (рис. 25.30). Отрезки Mt Nt и Pt Qt вместе с отрезками AC, DE и FB дают требуемое разбиение.

25.47. Разбиение плоскости на отрезки изображено на рис. 25.31. Выделенные ломаные состоят из концов отрезков разбиения; их звенья, естественно, не являются отрезками разбиения.

25.48. Выберем среди всех отрезков, покрывающих левый конец исходного отрезка, тот, у которого правый конец самый правый, и обозначим этот отрезок I1. После того как выбран отрезок Ik, выбираем среди всех отрезков, покрывающих его правый конец, тот, у которого правый конец самый правый. Таким образом выберем несколько отрезков, полностью покрывающих исходный отрезок. Остаётся доказать, что сумма их длин не превосходит 2.

Отрезок Ik+2 не имеет общих точек с Ik, так как иначе вместо Ik+1 мы должны были бы выбрать Ik+2. Поэтому каждая точка исходного отрезка длиной покрыта не более чем двумя отрезками Ik, т. е. сумма длин этих отрезков не превосходит 2.

25.49. Будем последовательно выбрасывать отрезки, покрытые одним или несколькими оставшимися отрезками, до тех пор, пока это возможно. Направим ось координат по данному отрезку и обозначим координаты концов оставшихся отрезков через ak и bk (ak < bk ). Один из двух отрезков с общим левым концом всегда будет выброшен, поэтому можно считать, что a1 < a2 < a3 <... < an. Докажем, что тогда bk < ak+2, т. е. чётные отрезки не пересекаются и нечётные тоже. Предположим, что bk ak+2. Возможны два случая.

1. bk+1 bk+2, тогда отрезок с номером k + 1 покрыт отрезками с номерами k и k + 2. Получено противоречие.

500 Глава 25. Разрезания, разбиения, покрытия 2. bk+1 bk+2, тогда отрезок с номером k + 2 покрыт отрезком с номером k + 1. Получено противоречие.

Остаётся заметить, что сумма длин либо чётных, либо нечётных отрезков не меньше 0,5.

25.50. Пусть AB — наибольшая сторона пятиугольника. Рассмотрим полосу, заданную перпендикулярами к стороне AB, проведёнными через A и B. Так покрытия и выбросим все квадраты, пересекающиеся с ним. Они лежат внутри квадрата, поэтому площадь, занимаемая их частями, расположенными вне K, не больше 8s, где s — площадь K. Квадрат K относим к выбранным и в дальнейшем его уже не рассматриваем. Для остальных квадратов проделываем то же самое до тех пор, пока все квадраты будут либо выбраны, либо выброшены. Если сумма площадей выбранных квадратов равна S, то общая площадь частей выброшенных квадратов, расположенных вне выбранных квадратов, не превосходит 8S. Поэтому 1 S + 8S, т. е. S 1/9.

б) Выберем круг наибольшего радиуса, раздуем его в три раза и выбросим все круги, целиком лежащие в этом раздутии. Оставшиеся круги не пересекаются с первым. Для них проделаем то же самое и т. д. Раздутия всех выбранных кругов содержат все данные круги, а площадь раздутия в 9 раз больше площади исходного круга, поэтому 9S 1, где S — общая площадь всех выбранных кругов. Следовательно, S 1/9.

25.52. Проведём прямую l так, что две данные точки лежат по одну сторону от неё и две — по другую. Пусть точки A и B лежат по одну сторону от l, C и D — по другую. Пусть A1 и B1 — проекции точек A и B на прямую l. Поставим в точке A прожектор так, чтобы он освещал угол, заданный лучом AA и лучом, параллельным l и пересекающим прямую BB1. Прожектор в точке B поставим аналогичным образом (рис. 25.33, а). Эти два прожектора освещают полуплоскость, содержащую точки C и D. Аналогично в точках C и D ставим прожекторы, освещающие другую полуплоскость. (Если AB l, то прожекторы нужно направить так, как показано на рис. 25.33, б.) 25.53. а) Не верно. Пусть — правильный треугольник со стороной 1. Легко проверить, что длина проекции на любую прямую не больше 1. С другой стороны, так как треугольник остроугольный, его нельзя накрыть кругом, радиус которого меньше радиуса описанной окружности (см. задачу 9.97).

Диаметр описанной окружности треугольника равен 2/ 3 > 1.

б) Верно. Если проекции фигуры на две взаимно перпендикулярные прямые равны a и b, то её можно заключить в прямоугольник со сторонами a и Диаметр описанной окружности этого прямоугольника равен a2 + b2.

25.54. Построим круги с центрами в данных точках радиуса a = 1/2 + 1/2n.

Ясно, что пересекающиеся круги радиусов R1 и R2 можно заключить в круг радиуса не более R1 + R2. Будем так делать до тех пор, пока не получатся непересекающиеся круги. Все данные точки расположены на расстоянии не меньше a от границ этих кругов, поэтому их радиусы можно уменьшить на b < a, и при этом они по-прежнему будут покрывать все данные точки. Если кругов k штук, то сумма их диаметров не больше n · 2a k · 2b 2na 2b. Нам нужно, чтобы выполнялись следующие условия: 2na 2b < n и b < a. Они выполняются, если a = 1/2 + 1/2n и b = 1/2 + 1/4n.

25.55. Раздуем все монеты в 2 раза, т. е. для каждой из них рассмотрим круг радиуса 2r с тем же центром. Если центр одной монеты не принадлежит раздутию второй монеты, то расстояние между их центрами больше 2r, а значит, эти монеты не пересекаются. Кроме того, если центр монеты удалён от края стола меньше чем на r, то она лежит внутри стола. Поэтому раздутия монет полностью покрывают круг радиуса R r, Рис. 25. так как иначе можно было бы положить монету с центром в непокрытой точке. Следовательно, 4pr2 n p(R r)2, т. е. 2 n (R r)/r.

25.56. Требуемое замощение изображено на рис. 25.34.

25.57. а) Докажем это утверждение по индукции. Для квадрата со стороной 2 оно очевидно.

Предположим теперь, что можно замостить любой квадрат со стороной 2n без одной клетки, и покажем, как тогда замостить квадрат со стороной 2n+1 без одной клетки. Разобьём этот квадрат на 4 квадрата со стороной 2n. Выброшенная клетка попадает в один из них, а по одной клетке в трёх остальных квадратах можно покрыть одной фигуркой (рис. 25.35). Теперь в каждом из этих Рис. 25. 502 Глава 25. Разрезания, разбиения, покрытия четырёх квадратов со стороной 2n выброшено по одной клетке, поэтому их можно замостить данными фигурками.

б) Докажем сначала требуемое утверждение для n = 1, т. е. для квадрата со стороной 7. Можно считать, что выброшенная клетка лежит в одном из заштрихованных на рис. 25.36 квадратиков; требуемые замощения изображены на этом же рисунке.

Покажем теперь, как с помощью замощения квадрата со стороной 6n + построить замощение квадрата со стороной 6n + 7. Четыре квадрата со стороной 6n + 1, Прилегающие к вершинам квадрата со стороной 6n + 7, полностью покрывают этот квадрат. Поэтому выброшенная клетка лежит в одном из этих квадратов; замостим его. Оставшуюся часть можно разрезать на квадраты со стороной 6 и прямоугольники размером 6 7. Эти квадраты и прямоугольники можно разрезать на прямоугольники размером 2 3, каждый из которых состоит из двух плиток.

25.58. Требуемое покрытие изображено на рис. 25.37.

25.59. Разрежем прямоугольник со сторонами 2n и 2m на квадратики со стороной 2 и вторым слоем будем мостить каждый квадратик по отдельности.

Квадратик можно замостить либо двумя горизонтальными костями домино, либо двумя вертикальными. Ясно, что нам подойдёт одно из этих покрытий, так как в квадратике со стороной 2 не фигуры, а не только для прямоугольника. Возьмём произвольную карточку A0. Одна из её клеток покрыта клеткой другой карточки A1, вторая Цепочка карточек A0, A1, A2,... замкнётся, причём именно на карточке A0, так как иначе какая-либо клетка будет покрыта трижды (не исРис. 25. состоит из чётного числа карточек (для доказательства можно рассмотреть ломаную, каждое звено которой соединяет центры клеток одной карточки;

эта ломаная имеет чётное число и горизонтальных и вертикальных звеньев).

Поэтому для карточек, входящих в замкнутую цепочку, искомым разбиением является разбиение на карточки с чётными и нечётными номерами. Все эти карточки выбрасываем и для оставшихся карточек проделываем такую же операцию и т. д.

25.61. а) Нельзя. Предположим, что квадрат 6 6 замощён костями домино 1 2 так, что нет «шва». Рассмотрим 10 отрезков, которые делят квадрат на 36 клеток (стороны самого квадрата мы не рассматриваем). Каждый из этих отрезков разрезает не менее двух костей. В самом деле, если бы такой отрезок разрезал одну кость, то по обе стороны от него лежало бы целое число костей и ещё половина кости, т. е. нечётное число клеток. Этого не может быть, так как площадь каждой из частей, на которые отрезок разрезает квадрат, чётна. Ясно также, что одну кость не могут разрезать разные отрезки.

Поэтому должно быть по крайней мере 20 костей, а их всего 18.

б) На рис. 25.38 показано, как замостить прямоугольники 5 6 и (при замощении прямоугольника 8 8 использовано замощение прямоугольника 5 6).

Теперь достаточно доказать, что если можно замостить прямоугольник m n, то можно замостить и прямоугольник m (n + 2). Для этого нужно разрезать замощённый прямоугольник m n на две части, не разрезая костей.

Затем нужно правую часть сдвинуть вправо на расстояние 2 и промежуток заполнить горизонтальными костями (рис. 25.39).

в) Требуемое замощение изображено на рис. 25.40.

25.62. а) Предположим, что круг K радиуса R покрыт паркетом, состоящим из одинаковых выпуклых n-угольников. Рассмотрим все точки, лежащие 504 Глава 25. Разрезания, разбиения, покрытия внутри круга K и являющиеся вершинами n-угольников. Эти точки бывают двух типов: точки 1-го типа лежат на сторонах других n-угольников и сумма углов, сходящихся в них, равна 180 ; в точках 2-го типа сходятся углы, сумма которых равна 360. Пусть p и q — количества точек 1-го и 2-го типа соответственно. В каждой точке 1-го типа сходится не менее двух углов n-угольников, а в каждой точке 2-го типа — не менее трёх углов. Поэтому 2p + 3q 2nL1, где L1 — количество n-угольников, пересекающихся с K. Суммы углов, сходящихся в точках 1-го и 2-го типа равны 180 и 360 соответственно.

Поэтому p + 2q (n 2)L2, где L2 — количество n-угольников, лежащих внутри K. Сложив неравенства 4p + 6q 4nL1 и 3p 6q 6L2 3nL2, получим p 6L2 n(4L1 3L2 ), т. е. p/L2 6 n(4L1 /L2 3). Так как limR L1 /L2 = 1, то limR p/L2 = 6 n. Значит, если из данных выпуклых n-угольников можно сложить паркет, то 6 n 0, т. е. n 6.

б) См. рис. 25.41.

25.63. Пусть ABCD — исходный квадрат, A1 B1 C1 D1 — квадрат с тем же центром, стороны которого параллельны сторонам исходного квадрата и имеют вдвое большую длину. Для определённости будем считать, что сторона исходного квадрата равна 2. Тогда периметр квадрата A1 B1 C1 D1 равен 16.

Поэтому достаточно доказать, что длина части периметра квадрата A1 B1 C1 D1, высекаемой приложенным квадратом, не может быть меньше 2. Рассмотрим два возможных варианта расположения квадрата A1 B1 C1 D1 и приложенного квадрата.

1) Ни одна вершина квадрата A1 B1 C1 D1 не попадает внутрь приложенного квадрата. В этом случае рассматриваемая часть периметра является отрезком PQ. Если внутри квадрата A1 B1 C1 D1 лежит только одна вершина приложенного квадрата (та, которая примыкает к исходному квадрату), то ходного квадрата и стороной приложенного квадрата. Если внутри квадрата A1 B1 C1 D1 лежат две вершины приложенного квадрата, то отрезок PQ является гипотенузой прямоугольного треугольника с катетом 2.

2) Одна вершина квадрата A1 B1 C1 D1 попадает внутрь приложенного квадрата. Тогда длина рассматриваемой части периметра равна a + tg a + 1 a tg a (рис. 25.42). Требуется доказать, что a + tg a + 1 a tg a 2, т. е. (a 1) tg a

СИСТЕМЫ ТОЧЕК И ОТРЕЗКОВ.

ПРИМЕРЫ И КОНТРПРИМЕРЫ

26.1. а) Архитектор хочет расположить четыре высотных здания так, что, гуляя по городу, можно увидеть их шпили в произвольном порядке (т. е. для любого набора номеров зданий i, j, k, l можно, стоя в некоторой точке и поворачиваясь в направлении «по» или «против» часовой стрелки, увидеть сначала шпиль здания i, затем j, k, l). Удастся ли ему это сделать?

б) Тот же вопрос для пяти зданий.

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

26.3*. На плоскости дано 400 точек. Докажите, что различных расстояний между ними не менее 15.

26.4*. На плоскости дано n 3 точек. Пусть d — наибольшее расстояние между парами этих точек. Докажите, что имеется не более n пар точек, расстояние между которыми равно d.

26.5*. На плоскости дано 4000 точек, никакие три из которых не лежат на одной прямой. Докажите, что существует 1000 непересекающихся четырёхугольников (возможно, невыпуклых) с вершинами в этих точках.

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

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

См. также задачи 9.20, 9.50, 9.63, 20.3, 20.4, 20.8, 20.9, 20.14, 20.16, 20.17, 20.22, 20.23, 20.25, 20.27, 20.28, 21.2, 21.3, 21.5, 21.6, 21.8, 21.10, 21.25, 21.26, 22.1, 22.8, 22.33, 23.20, 26.16, 26.20, 27.11, 28.35, 31.75.

§ 2. Системы отрезков, прямых и окружностей 26.8. Постройте замкнутую шестизвенную ломаную, пересекающую каждое своё звено ровно один раз.

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

26.10*. Точка O, лежащая внутри выпуклого многоугольника A1... An, обладает тем свойством, что любая прямая OAi содержит ещё одну вершину Aj. Докажите, что кроме точки O никакая другая точка не обладает этим свойством.

26.11*. На окружности отметили 4n точек и окрасили их через одну в красный и синий цвета. Точки каждого цвета разбили на пары, а точки каждой пары соединили отрезками того же цвета.

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

26.12*. На плоскости расположено n 5 окружностей так, что любые три из них имеют общую точку. Докажите, что тогда и все окружности имеют общую точку.

См. также задачи 20.5, 20.15, 20.30, 21.14, 21.15, 21.17—21.19, 23.42, 25.5—25.12, 28.37—28.42.

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

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

26.13. Существует ли треугольник, у которого все высоты меньше 1 см, а площадь больше 1 м2 ?

26.14. В выпуклом четырёхугольнике ABCD равны стороны AB и CD и углы A и C. Обязательно ли этот четырёхугольник параллелограмм?

26.15*. Список упорядоченных в порядке возрастания длин сторон и диагоналей одного выпуклого четырёхугольника совпадает с таким же списком для другого четырёхугольника. Обязательно ли эти четырёхугольники равны?

26.16*. Пусть n 3. Существуют ли n точек, не лежащих на одной прямой, попарные расстояния между которыми иррациональны, а площади всех треугольников с вершинами в них рациональны?

26.17*. Существуют ли на плоскости три такие точки A, B и C, что для любой точки X длина хотя бы одного из отрезков XA, XB и XC иррациональна?

26.18*. В остроугольном треугольнике ABC проведены медиана AM, биссектриса BK и высота CH. Может ли площадь треугольника, образованного точками пересечения этих отрезков, быть больше 0,499SABC ?

508 Глава 26. Системы точек. Примеры и контрпримеры 26.19*. На бесконечном листе клетчатой бумаги (размер клетки 1 1) укладываются кости домино размером 1 2 так, что они накрывают все клетки. Можно ли при этом добиться того, чтобы любая прямая, идущая по линиям сетки, разрезала лишь конечное число костей?

26.20*. Может ли конечный набор точек содержать для каждой своей точки ровно 100 точек, удалённых от неё на расстояние 1?

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

26.22*. Обязательно ли треугольник равнобедренный, если центр его вписанной окружности одинаково удалён от середин двух сторон?

26.23*. Арена цирка освещается n различными прожекторами.

Каждый прожектор освещает выпуклую фигуру. Известно, что если выключить любой прожектор, то арена будет по-прежнему полностью освещена, а если выключить любые два прожектора, то арена будет освещена не полностью. При каких n это возможно?

См. также задачи 6.81, 6.92—6.95, 22.37—22.39, 22.47, 22.48, 22.50, 23.38, 24.12, 24.13.

26.1. а) Легко проверить, что, построив четвёртое здание внутри треугольника, образованного тремя другими зданиями, получим требуемое расположение.

б) Расположить требуемым образом пять зданий нельзя. В самом деле, если мы видим последовательно здания A1, A2,..., An, то A1 A2... An — несамопересекающаяся ломаная. Поэтому если ABCD — выпуклый четырёхугольник, то его вершины нельзя увидеть в следующем порядке: A, C, D, B. Остаётся заметить, что из пяти точек, никакие три из которых не лежат на одной прямой, всегда можно выбрать четыре точки, являющиеся вершинами выпуклого четырёхугольника (задача 22.2).

26.2. Можно считать, что n 4 и не все точки лежат на одной прямой.

Тогда можно выбрать четыре точки A, B, C и D, не лежащие на одной прямой. По условию три из них лежат на одной прямой. Пусть для определённости точки A, B и C лежат на прямой l, а D не лежит на l. Нужно доказать, что все точки, кроме D, лежат на прямой l. Предположим, что точка E не принадлежит l. Рассмотрим четвёрку точек A, B, D, E. Тройки точек A, B, D и A, B, E не лежат на одной прямой. Поэтому на одной прямой лежит либо тройка точек A, D, E, либо тройка точек B, D, E.

Пусть для определённости на одной прямой лежат точки A, D и E. Тогда никакие три из точек B, C, D, E не лежат на одной прямой. Получено противоречие.

26.3. Пусть количество различных расстояний между точками равно k.

Фиксируем две точки. Тогда все остальные точки являются точками пеРешения задач ресечения двух семейств концентрических окружностей, содержащих по k окружностей. Следовательно, общее количество точек не превосходит 2k2 + 2.

Остаётся заметить, что 2 · 142 + 2 = 394 < 400.

26.4. Назовём диаметром отрезок длиной d, соединяющий пару данных точек. Концы всех диаметров, выходящих из точки A, лежат на окружности с центром A и радиусом d. Так как расстояние между любыми двумя точками не превосходит d, концы всех диаметров, выходящих из A, лежат на дуге, угловая величина которой не превосходит 60. Следовательно, если из точки A выходят три диаметра AB, AC и AD, то один из концов этих диаметров лежит внутри угла, образованного двумя другими. Пусть для определённости точка C лежит внутри угла BAD. Докажем, что тогда из точки C выходит не более одного диаметра. Предположим, что есть ещё диаметр CP и точки B и P лежат по разные стороны от прямой AC (рис. 26.1). Тогда ABCP — выпуклый четырёхугольник, поэтому AB + CP < AC + BP (см. задачу 9.15), т. е. d + d < d + BP, а значит, BP > d, чего не может быть.

В итоге получаем, что либо из каждой точки выходит не более двух диаметров, либо существует точка, из которой выходит не более одного диаметра. Теперь требуемое утверждение можно доказать индукцией по числу точек. Для n = 3 оно очевидно. Предположим, что утверждение доказано для любой сиРис. 26. стемы из n точек, и докажем его для системы из n + 1 точки. В этой системе либо есть точка, из которой выходит не более одного диаметра, либо из каждой точки выходит не более двух диаметров. В первом случае отбрасываем эту точку и, воспользовавшись тем, что в оставшейся системе не более n диаметров, получаем требуемое.

Второй случай очевиден.

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

26.6. Разобьём данные точки произвольным образом на шесть групп: четыре группы по четыре точки, группа из пяти точек и группа из одной точки. Рассмотрим группу из пяти точек. Из них можно выбрать четыре точки, являющиеся вершинами некоторого выпуклого четырёхугольника ABCD (см. задачу 22.2). Объединим в пары точки A, C и B, D. Тогда отрезки Рис. 26. AC и BD, заданные парами, пересекаются. Одна из пяти точек осталась свободной. Присоединим её к четвёрке точек и с полученной пятёркой точек проделаем то же самое и т. д. После пяти таких операций останутся две точки, и мы объединим их в пару.

510 Глава 26. Системы точек. Примеры и контрпримеры щий тем свойством, что sin f = 2n/(n + 1) и cos f = (n 1)/(n + 1), причём 0 < 2Nf < p/2 при достаточно большом n. Рассмотрим окружность радиуса R с центром O и возьмём на ней точки A0, A1,..., AN1 так, что A0 OAk = 2kf.

Тогда Ai Aj = 2Rsin(|i j|f). Воспользовавшись формулами sin(m + 1)f = = sin mf cos f + sin f cos mf и cos(m + 1)f = cos mf cos f sin mf sin f, легко доказать, что числа sin mf и cos mf рациональны для всех натуральных m.

Возьмём в качестве R наибольший общий делитель всех знаменателей рациональных чисел sin f,..., sin(N 1)f. Тогда A0,..., AN1 — требуемая система точек.

26.8. Требуемый пример изображён на рис. 26.3.

26.9. Можно. Пример изображён на рис. 26.4.

26.10. Из условия следует, что все вершины многоугольника разбиваются на пары, задающие диагонали Ai Aj, которые проходят через точку O. Поэтому число вершин чётно и по обе стороны от каждой такой диагонали Ai Aj лежит равное число вершин. Следовательно, j = i + m, где m — половина числа вершин. Таким образом, точка O является точкой пересечения диагоналей, соединяющих противоположные вершины. Ясно, что точка пересечения этих диагоналей единственна.

26.11. Если AC и BD — пересекающиеся красные отрезки, то число точек пересечения любой прямой с отрезками AB и CD не превосходит числа точек пересечения этой прямой с отрезками AC и BD. Поэтому, заменив красные отрезки AC и BD на отрезки AB и CD, мы не увеличим число точек пересечения красных отрезков с синими, а число точек пересечения красных отрезков с красными уменьшим, так как исчезнет точка пересечения AC и BD. После нескольких таких операций все красные отрезки станут непересекающимися, и нам остаётся доказать, что в этом случае число точек пересечения красных отрезков с синими не меньше n. Рассмотрим произвольный красный отрезок.

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

Следовательно, найдётся синий отрезок, пересекающий данный красный отрезок. Поэтому числе точек пересечения красных отрезков с синими не меньше числа красных отрезков, т. е. не меньше n.

26.12. Пусть A — общая точка первых трёх окружностей S1, S2 и S3.

Обозначим точки пересечения окружностей S1 и S2, S2 и S3, S3 и S1 через B, C, D соответственно. Предположим, что существует окружность S, не проходящая через точку A. Тогда окружность S проходит через точки B, C и D. Пусть S — пятая окружность. Каждая пара точек из набора A, B, C, D является парой точек пересечения двух из окружностей S1, S2, S3, S. Поэтому окружность S проходит через одну точку из каждой пары точек A, B, C, D. С другой стороны, окружность S не может проходить через три точки из A, B, C, D, поскольку каждая тройка этих точек задаёт одну из окружностей S1, S2, S3, S. Поэтому окружность S не проходит через какие-то две из этих точек. Получено противоречие.

26.13. Рассмотрим прямоугольник ABCD со сторонами AB = 1 см и BC = 500 м. Пусть O — точка пересечения его диагоналей. Легко проверить, что площадь треугольника AOD больше 1 м2, а все его высоты меньше 1 см.

26.14. Нет, не обязательно. На рис. 26.5 показано, как получить нужный четырёхугольник ABCD.

26.15. Не обязательно. Легко проверить, что список длин сторон и диагоналей для равнобедрен- Рис. 26. ной трапеции с высотой 1 и основаниями 2 и совпадает с таким же списком для четырёхугольника с перпендикулярными диагоналями длиной 2 и 4, делящимися точкой пересечения на отрезки длиной 1 и 1, 1 и 3 (рис. 26.6).

26.16. Да, существуют. Рассмотрим точки Pi = (i, i2 ), где i = 1,..., n.

Площади всех треугольников с вершинами в узлах целочисленной решётки рациональны (см. задачу 24.7), а числа Pi Pj = |i j| 1 + (i + j)2 иррациональны.

26.17. Да, существуют. Пусть C — середина отрезка AB. Тогда XC2 = = (2XA2 + 2XB2 AB2 )/2. Если число AB2 иррационально, то числа XA, XB и XC не могут одновременно быть рациональными.

26.18. Может. Рассмотрим прямоугольный треугольник ABC1 с катетами AB = 1 и BC1 = 2n. Проведём в нём медиану AM1, биссектрису BK1 и высоту C1 H1. Площадь треугольника, образованного этими отрезками, больше SABM1 SABK1. Ясно, что SABK1 < 1/2 и SABM1 = n/2, т. е. SABM1 SABK1 > > (S/2) (S/2n), где S = SABC1. Поэтому при достаточно большом n площадь треугольника, образованного отрезками AM1, BK1 и C1 H1, будет больше 0,499S.

Точку C1 можно слегка сдвинуть так, чтобы прямоугольный треугольник ABC1 превратился в остроугольный треугольник ABC, а площадь треугольГлава 26. Системы точек. Примеры и контрпримеры ника, образованного точками пересечения отрезков, осталась больше 0,499 площади треугольника ABC.

A1,..., Ak при параллельном переносе на единичный вектор a. Для доказательства шага индукции i = j. Каждое из этих ограничений исключает из единичной окружности не более одной точки.

26.21. Не всегда. Рассмотрим отрезки, изображённые на рис. 26.8. Концы каждого короткого отрезка можно соединить только с концами ближайшего к нему длинного отрезка. Ясно, что при этом не может получиться замкнутая несамопересекающаяся ломаная.

26.22. Не обязательно. Докажем, что центр O вписанной окружности треугольника ABC со сторонами AB = 6, BC = 4 и CA = 8 одинаково удалён от середин сторон AC и BC. Обозначим середины сторон AC и BC через B1 и A1, а основания перпендикуляров, опущенных из точки O на AC и BC, — через B2 и A2 (рис. 26.9). Так как A1 A2 = 1 = B1 B2 (см. задачу 3.2) и OA2 = OB2, то OA1 A2 = OB1 B2 т. е. OA1 = OB1.

26.23. Это возможно при любом n 3. Впишем в арену правильный k-угольник, где k — число различных пар, которые можно составить из n прожекторов, т. е. k = n(n 1)/2. Тогда можно установить взаимно однозначное соответствие между сегментами, отсекаемыми сторонами k-угольника, и парами прожекторов. Пусть каждый прожектор освещает весь k-угольник и сегменты, соответствующие парам прожекторов, в которые он входит. Легко проверить, что это освещение обладает требуемыми свойствами.

ИНДУКЦИЯ И КОМБИНАТОРИКА

При решении геометрических задач иногда используется метод математической индукции. Он заключается в следующем. Пусть имеется некоторое утверждение A(n), где n — натуральное число. Чтобы доказать истинность этого утверждения для всех n k, достаточно доказать его истинность для n = k и доказать, что из истинности утверждения для n = m, где m — любое натуральное число, не меньшее k, следует его истинность для n = m + 1.

Доказательство истинности утверждения A(n) при n = k называют базой индукции, а доказательство того, что из истинности утверждения для n = m следует его истинность для n = m + 1, называют шагом индукции.

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

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

27.3*. Пусть E — точка пересечения боковых сторон AD и BC трапеции ABCD, Bn+1 — точка пересечения прямых An C и BD (A0 = A), An+1 — точка пересечения прямых EBn+1 и AB. Докажите, что An B = = AB/(n + 1).

27.4*. На прямой даны точки A1,..., An и B1,..., Bn1. Докажите, что 27.5*. Докажите, что если n точек не лежат на одной прямой, то среди прямых, их соединяющих, не менее n различных.

См. также задачи 2.13, 5.119, 13.26, 22.8, 22.9, 22.11—22.13, 22.32, 22.41 б), 22.43, 22.44, 22.50, 23.40—23.42, 24.17, 25.24, 25.26, 25.33, 25.36, 25.39, 25.57, 26.4, 26.20 28.37, 28.38.

514 Глава 27. Индукция и комбинаторика 27.6. На окружности отмечено несколько точек, A — одна из них.

Каких выпуклых многоугольников с вершинами в этих точках больше: содержащих точку A или не содержащих её?

27.7. На окружности отмечено десять точек. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в этих точках?

27.8*. В выпуклом n-угольнике (n 4) проведены все диагонали, причём никакие три из них не пересекаются в одной точке. Найдите число точек пересечения диагоналей.

27.9*. В выпуклом n-угольнике (n 4) проведены все диагонали.

На сколько частей они делят n-угольник, если никакие три из них не пересекаются в одной точке?

27.10*. На плоскости дано n точек, никакие три из которых не лежат на одной прямой. Докажите, что существует не менее C5 /(n 4) различных выпуклых четырёхугольников с вершинами в этих точках (определение числа Ck см. на с. 428).

27.11*. Докажите, что число неравных треугольников с вершинами в вершинах правильного n-угольника равно ближайшему к n2 / целому числу.

См. также задачи 21.27—21.29, 25.6.

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

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

Если из каждой вершины (n + 1)-угольника выходит не более двух выбранных сторон или диагоналей, то их всего выбрано не более n + 1. Поэтому будем считать, что из некоторой вершины A выходят три выбранные стороны или диагонали AB1, AB2 и AB3, причём AB2 лежит между AB1 и AB3. Так как диагональ или сторона, выходящая из точки B2 и отличная от AB2 не может одновременно пересекать AB1 и AB3, то из B2 выходит только одна выбранная диагональ. Поэтому можно выбросить точку B2 вместе с диагональю AB и применить предположение индукции.

27.3. Ясно, что A0 B = AB. Пусть Cn — точка пересечения прямых EAn и DC, DC : AB = k, AB = a, An B = an и An+1 B = x. Так как CCn+1 : An An+1 = DCn+1 : BAn+1, то kx : (an x) = (ka kx) : x, т. е. x = aan /(a + an ). Если an = a/(n + 1), то x = a/(n + 2).

27.4. Докажем сначала требуемое утверждение при n = 2. Так как A1 B1 + + B1 A2 + A2 A1 = 0, то (A1 B1 /A1 A2 ) + (A2 B1 /A2 A1 ) = 1. Для доказательства шага индукции поступим следующим образом. Фиксируем точки A1,..., An и B1,..., Bn2, а точку Bn1 будем считать переменной. Рассмотрим функцию Эта функция линейная, причём по предположению индукции f(Bn1 ) = 1, если Bn1 совпадает с одной из точек A1,..., An. Следовательно, эта функция тождественно равна 1.

27.5. Доказательство проведём индукцией по n. При n = 3 утверждение очевидно. Предположим, что мы доказали его для n 1 точки и докажем его для n точек. Если на каждой прямой, проходящей через две данные точки, лежит ещё одна данная точка, то все данные точки лежат на одной прямой (см. задачу 20.14). Поэтому существует прямая, на которой лежат ровно две данные точки A и B. Выбросим точку A. Возможны два случая.

1. Все оставшиеся точки лежат на одной прямой l. Тогда будет ровно n различных прямых: n 1 прямая, проходящая через A, и прямая l.

2. Оставшиеся точки не лежат на одной прямой. Тогда среди прямых, их соединяющих, по предположению индукции есть не менее n 1 различных, причём все они отличны от прямой l. Вместе с прямой AB они составляют не менее n прямых.

27.6. Любому многоугольнику, не содержащему точки A, можно поставить в соответствие многоугольник, содержащий точку A, добавив её к его вершинам. А вот обратную операцию, т. е. отбрасывание вершины A, можно производить только для n-угольников с n 4. Поэтому многоугольников, содержащих точку A, больше, чем многоугольников, не содержащих точки A, причём больше на число треугольников с вершиной A, т. е. на (n 1)(n 2)/2.

27.7. Первую точку можно выбрать десятью способами. Каждую из следующих восьми точек можно выбрать двумя способами, так как она должна быть соседней с одной из ранее выбранных точек (иначе получится самопересекающаяся ломаная). Поскольку начало и конец при таком подсчёте не различаются, результат нужно разделить на 2. Следовательно, всего имеется 10 · 28 /2 = 1280 ломаных.

27.8. Любая точка пересечения диагоналей определяет две диагонали, пересечением которых она является, а концы этих диагоналей определяют выпуклый четырёхугольник. Обратно, любые четыре вершины многоугольника определяют одну точку пересечения диагоналей. Поэтому число точек пересечения диагоналей равно числу способов выбора четырёх точек из n, т. е. равно n(n 1)(n 2)(n 3) 27.9. Будем поочерёдно проводить диагонали. Когда мы проводим очередную диагональ, число частей, на которые проведённые ранее диагонали делят многоугольник, увеличивается на m + 1, где m — число точек пересечения новой диагонали с ранее проведёнными, т. е. каждая новая диагональ и каждая новая точка пересечения диагоналей увеличивают число частей на 1. Поэтому общее число частей, на которые диагонали делят n-угольник, равно D + P + 1, где D — число диагоналей, P — число точек пересечения диагоналей. Ясно, что D = n(n 3)/2. Согласно предыдущей задаче P = n(n 1)(n 2)(n 3)/24.

27.10. Если выбрать любые пять точек, то существует выпуклый четырёхугольник с вершинами в них (задача 22.2). Остаётся заметить, что четвёрку точек можно дополнить до пятёрки n 4 различными способами.

27.11. Пусть всего имеется N неравных треугольников с вершинами в вершинах правильного n-угольника, причём из них N1 правильных, N2 неправильных равнобедренных и N3 разносторонних. Каждый правильный треугольник равен одному треугольнику с фиксированной вершиной A, неправильный равнобедренный — трём треугольникам с вершиной A, а разносторонний — шести. Так как всего имеется (n 1)(n 2)/2 треугольников с вершиной A, то (n 1)(n 2)/2 = N1 + 3N2 + 6N3.

Ясно, что число неравных правильных треугольников равно 0 или 1, а число неравных равнобедренных равно (n 1)/2 или (n/2) 1, т. е. N1 = 1 c, N1 + + N2 = (n 2 + d)/2, где c и d равны 0 или 1. Поэтому 12N = 12(N1 + N2 + N3 ) = = n2 + 3d 4c. Так как |3d 4c| < 6, то N совпадает с ближайшим к n2 / целым числом.

ИНВЕРСИЯ

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