Формула. В. В. Прасолов задачи по планиметрии
 Скачать 6.7 Mb.
|
|
§ 1. Многоугольники с вершинами в узлах решётки 24.1*. Существует ли правильный треугольник с вершинами вуз- лах целочисленной решётки? 24.2*. Докажите, что при n 6= 4 правильный угольник нельзя расположить так, чтобы его вершины оказались в узлах целочисленной решётки. 24.3*. Можно ли прямоугольный треугольник с целыми сторонами расположить так, чтобы его вершины лежали в узлах целочисленной решётки, но ни одна из его сторон не проходила по линиям решётки? 24.4*. Существует ли замкнутая ломаная с нечётным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решётки? 24.5*. На клетчатой бумаге выбраны три точки A, B, C, находящиеся в вершинах клеток. Докажите, что если треугольник остроугольный, то внутри его или на сторонах есть по крайней мере ещё одна вершина клетки. 24.6*. Вершины выпуклого многоугольника расположены в узлах целочисленной решётки, причём ни одна из его сторон не проходит по линиям решётки. Докажите, что сумма длин горизонтальных отрезков линий решётки, заключённых внутри многоугольника, равна сумме длин вертикальных отрезков. См. также задачи 2. Формула Пика 24.7*. Вершины многоугольника (необязательно выпуклого) расположены в узлах целочисленной решётки. Внутри его лежит n узлов решётки, а на границе m узлов. Докажите, что его площадь равна + m/2 − 1 (формула Пика Глава 24. Целочисленные решётки 24.8*. Последовательностью Фарея называют возрастающую последовательность несократимых дробей a/b, где 0 < a < b 6 n. Пусть и c/d — соседние члены последовательности Фарея. Докажите, что − bc| = Вершины треугольника ABC расположены в узлах целочисленной решётки, причём на его сторонах других узлов нет, а внутри его есть ровно один узел O. Докажите, что O — точка пересечения медиан треугольника Докажите, что квадрат со стороной n не может накрыть более (n + точек целочисленной решётки. § 3. Разные задачи 24.11*. На бесконечном листе клетчатой бумаги N клеток окрашено в чёрный цвет. Докажите, что из этого листа можно вырезать конечное число квадратов так, что будут выполняться два условия) все чёрные клетки лежат в вырезанных квадратах 2) в любом вырезанном квадрате K площадь чёрных клеток составит не менее и не более 0,8 площади Докажите, что для любого n существует окружность, внутри которой лежит ровно n целочисленных точек. 24.13*. Докажите, что для любого n существует окружность, на которой лежит ровно n целочисленных точек. См. также задачи 4. Вокруг теоремы Минковского 24.14*. Начало координат является центром симметрии выпуклой фигуры площадью более 4. Докажите, что эта фигура содержит хотя бы одну точку с целыми координатами, отличную от начала координат (Минковский). 24.15*. а) Во всех узлах целочисленной решётки, кроме одного, в котором находится охотник, растут деревья, стволы которых имеют радиус r. Докажите, что охотник не сможет увидеть зайца, находящегося от него на расстоянии больше б) Пусть n — натуральное число. Во всех точках целочисленной решётки, расположенных строго внутри окружности радиуса+ с центром вначале координат и отличных от начала координат, растут деревья радиуса r. Докажите, что если r < 1 p n 2 + 1 , тона указанной окружности есть точка, которую можно увидеть изначала координат. 24.16*. Внутри выпуклой фигуры с площадью S и полуперимет- ром p нет точек целочисленной решётки. Докажите, что S 6 p. Решения задач 471 24.17*. Выпуклая фигура Φ имеет площадь S и полупериметр Докажите, что если S > np для некоторого натурального n, то Φ содержит по крайней мере n целочисленных точек. 24.18*. Внутри выпуклой фигуры с площадью S и полуперимет- ром p лежит n узлов решётки. Докажите, что n > S − p. Решения 24.1. Предположим, что вершины правильного треугольника ABC расположены в узлах целочисленной решётки. Тогда тангенсы всех углов, образованных сторонами AB и AC с линиями решётки, рациональны. При любом положении треугольника ABC сумма или разность некоторых двух таких углов и равна 60 ◦ . Следовательно = tg 60 ◦ = tg( a ± b ) = = (tg a ± tg b )/(1 ∓ tg a tg b ) — рациональное число. Получено противоречие. 24.2. Для n = 3 и n = 6 утверждение вытекает из предыдущей задачи, поэтому будем в дальнейшем считать, что n 6= 3, 4, 6. Предположим, что существуют правильные угольники с вершинами в узлах целочисленной решётки (n 6= 3, 4, 6). Среди всех таких угольников можно выбрать тот, у которого длина стороны наименьшая. (Для доказательства достаточно заметить, что если a — длина отрезка с концами в узлах решётки, то a = √ n 2 + m 2 , где и m — целые числа, поэтому длина отрезка с концами в узлах решётки может принимать лишь конечное число различных значений, меньших данного.) Пусть # – A i B i = # – A i+1 A i+2 . Тогда B 1 . . . B n — правильный угольник, вершины которого лежат в узлах целочисленной решётки, а его сторона меньше стороны правильного угольника A 1 . . . A n . Для n = 5 это видно из риса для 7 — из рис. 24.2. Получено противоречие с выбором угольника A 1 . . . Рис. Рис. Легко проверить, что треугольник с вершинами в точках с координатами) и (−12, 9) обладает требуемыми свойствами. 24.4. Предположим, что существует замкнутая ломаная A 1 . . . с нечётным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решётки. Пусть и b i — координаты проекций вектора # на Глава 24. Целочисленные решётки горизонтальную и вертикальную оси. Обозначим длину звена ломаной через Тогда c 2 = a 2 i + b 2 i , поэтому при делении на 4 даёт остаток 0, 1 или Если делится на 4, то и делятся на 2 (это доказывается простым перебором всех возможных остатков, которые и дают при делении на Поэтому при гомотетии с центром и коэффициентом 0,5 наша ломаная перейдёт в ломаную с меньшей длиной звена, вершины которой по-прежнему лежат в узлах решётки. После нескольких таких операций придём к ломаной, у которой не делится нате. даёт остаток 1 или 2. Разберём эти варианты, предварительно заметив, что a 1 + . . . + a m = b 1 + . . . + b m = 0. 1. при делении на 4 даёт остаток 2. Тогда числа и оба нечётны, поэтому число a 1 + . . . + a m нечётно и не может равняться нулю. при делении на 4 даёт остаток 1. Тогда одно из чисел и b i нечётно, а другое чётно, поэтому число a 1 + . . . + a m + b 1 + . . . + b m нечётно и не может равняться нулю. 24.5. Построим прямоугольник со сторонами, идущими по линиям клетчатой бумаги, так, чтобы вершины A, B, C лежали на его сторонах. Ни одна из вершин A, B, C не может оказаться внутри этого прямоугольника, поскольку иначе угол при этой вершине был бы тупым. По крайней мере одна из точек A, B, C лежит на стороне прямоугольника, а не в его вершине, поскольку иначе треугольник ABC был бы прямоугольным. Пусть для определённости вершина A лежит на стороне прямоугольника. Введём на плоскости координаты, выбрав точку A в качестве начала координата эту сторону прямоугольника — в качестве оси Ox. Ось Oy направим так, чтобы прямоугольник лежал в полуплоскости y > 0. Ни одна из вершин B и C не лежит на оси Ox, поскольку иначе угол при вершине A был бы тупым. Таким образом, если точки B и C имеют координаты (x 1 , y 1 ) и (x 2 , y 2 ), то y 1 , y 2 > а числа и имеют разные знаки. Поэтому точка с координатами (0, лежит внутри треугольника ABC или на его стороне Докажем, что каждая из этих сумм равна площади многоугольника. Горизонтальные линии решётки разрезают многоугольник на два треугольника с основаниями и и n − 1 трапеций с основаниями и и a 3 , ..., и a n . Высоты этих треугольников и трапеций равны поэтому сумма их площадей равна 2 + a 1 + a 2 2 + a 2 + a 3 2 + . . . + a n−1 + a n 2 + a n 2 = a 1 + a 2 + . . . + Для вертикальных линий доказательство аналогично. 24.7. Каждому многоугольнику M с вершинами в узлах целочисленной решётки поставим в соответствие число f(M) = P i f i /2 p , где суммирование ведётся по всем узлам решётки, принадлежащим M, а угол определяется следующим образом 2 p для внутренней точки многоугольника для граничной точки, отличной от вершины, и f i — угол при вершине, если данный узел — вершина. Легко видеть, что f(M) = n + (m − 2) p 2 p = n + m 2 − 1. Остаётся проверить, что число f(M) равно площади многоугольника Пусть многоугольник M разрезан на многоугольники и сверши- нами в узлах решётки. Тогда f(M) = f(M 1 ) + f(M 2 ), поскольку для каждого узла углы складываются. Поэтому если формула Пика верна для двух из многоугольников M, и M 2 , то она верна и для третьего Решения задач 473 Если M — прямоугольник со сторонами p и q, направленными по линиям решётки, то) = (p − 1)(q − 1) + 2(p − 1) 2 + 2(q − 1) 2 + 4 4 = В этом случае формула Пика справедлива. Разрезав прямоугольник M диагональю на треугольники и и воспользовавшись тем, что f(M) = f(M 1 ) + + f(M 2 ) и f(M 1 ) = f(M 2 ), легко доказать справедливость формулы Пика для любого прямоугольного треугольника с катетами, направленными по линиям решётки. Отрезав несколько таких треугольников от прямоугольника, можно получить любой треугольник (рис. Рис. Для завершения доказательства формулы Пика остаётся заметить, что любой многоугольник можно разрезать на треугольники непересекающимися диагоналями (задача 22.43 ). 24.8. Сопоставим каждой несократимой дроби a/b точку с координатами, b). Если a/b и c/d — соседние члены последовательности Фарея, то треугольник с вершинами (0, 0), (a, b) и (c, d) не содержит целочисленных точек, отличных от вершин. Действительно, если бы целочисленная точка, q) принадлежала этому треугольнику, то числа p и q не превосходили бы n и дробь p/q была бы заключена между a/b и c/d. Поэтому согласно формуле Пика площадь этого треугольника равна 1/2. С другой стороны, согласно задаче 12.78 его площадь равна 2 |ad − Согласно формуле Пика S AOB = S BOC = S COA = 1/2, а значит, O — точка пересечения медиан треугольника ABC см. задачу 4.2 ). 24.10. Пусть M — выпуклая оболочка точек целочисленной решётки, покрытых квадратом со стороной n. Согласно формуле Пика её площадь равна + q 2 − 1, где p — количество целочисленных точек внутри M, q — количество целочисленных точек на границе M. Поэтому p + q 2 − 1 6 Периметр M не превосходит периметра данного квадрата (задача 9.29 б). Кроме того, расстояние между соседними целочисленными точками на границе не меньше 1. Поэтому q 6 Сложив неравенства p + q 2 − 1 6 и 6 2n, получаем требуемое неравенство+ 1) 2 24.11. Возьмём какой-нибудь достаточно большой квадрат со стороной так, чтобы все чёрные клетки лежали внутри его и составляли менее 0,2 его площади. Разрежем этот квадрат на четыре одинаковых квадрата. Каждый из Глава 24. Целочисленные решётки них окрашен менее чем на 0,8. Те из них, которые окрашены более чем на, оставляем, а остальные режем дальше таким же образом. Полученные квадраты 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 — рациональное число. Поэтому из равенства+ (n 1 − 1/3) 2 = (m 2 − √ 2) 2 + (n 2 − следует, что m 1 = m 2 . По теореме Виета сумма корней уравнения (n − (1/3)) 2 = = d равна 2/3, поэтому лишь один корень может быть целочисленным. Расположим теперь радиусы окружностей с центром A, проходящих через целочисленные точки, в порядке возрастания R 1 < R 2 < R 3 < . . . Если R < R n+1 , то внутри окружности радиуса R с центром A лежит ровно целочисленных точек. 24.13. Докажем сначала, что уравнение x 2 + y 2 = имеет ровно 4(k + целочисленных решений. При k = 0 и k = 1 это утверждение очевидно. Докажем, что уравнение x 2 + y 2 = имеет ровно восемь таких решений (x, что x и y не делятся на 5; вместе с 4(k − 1) решениями вида (5a, где a и b — решение уравнения a 2 + b 2 = 5 k−2 , они дают нужное количество решений. Эти решения получаются друг из друга перестановками x и y и изменениями знаков мы будем называть их нетривиальными решениями. Пусть x 2 + делится на 5. Тогда (x + 2y)(x − 2y) = x 2 + y 2 − тоже делится на 5. Поэтому одно из чисел x + 2y и x − 2y делится на 5. Легко проверить также, что если x + 2y и x − 2y делятся на 5, то x и y делятся на Если (x, y) — нетривиальное решение уравнения x 2 +y 2 =5 k , то (x+2y, и (x − 2y, 2x + y) — решения уравнения x 2 + h 2 = 5 k+1 , причём ровно одно из них нетривиально. Докажем, что нетривиальное решение единственно с точностью до перестановки x и y и изменения знаков. Пусть (x, y) — нетривиальное решение уравнения x 2 + y 2 = 5 k . Тогда как пары − y 5 , ± x + итак и пары + y 5 , ± x − и − 2y 5 , ± 2x + являются решениями уравнения x 2 + h 2 = 5 k−1 , но целочисленными будут пары ровно одного из этих видов, так как ровно одно из чисел x + и x − 2y делится на 5. При этом мы получим нетривиальное решение, потому что (x + 2y)(x − 2y) = (x 2 + y 2 ) − при k > 2 делится на 5, ноне делится на 25. Таким образом, каждое из восьми нетривиальных решений уравнения+ y 2 = дат восемь нетривиальных решений уравнения x 2 + h 2 = 5 k−1 , причём для одной половины решений нужно воспользоваться формулами первого вида, а для другой половины решений — формулами второго вида. Перейдём теперь непосредственно к решению задачи. Пусть n = 2k + Докажем, что на окружности радиуса 5 k /3 с центром (1/3, 0) лежит ровно целочисленных точек. Уравнение x 2 + y 2 = 5 имеет 4(2k + 1) целочисленных решений. Кроме того, 5 при делении на 3 даёт остаток 1, поэтому одно из чисел x и y делится на 3, а другое при делении на 3 даёт остаток ±1. Решения задач 475 Следовательно, ровно водной из пари) первое и второе числа дают при делении на 3 остатки и 0 соответственно. Поэтому уравнение (3z − 1) 2 + (3t) 2 = 5 имеет ровно 2k + 1 целочисленных решений. Пусть n = 2k. Докажем, что на окружности радиуса 5 (k−1)/2 /2 с центром, 0) лежит ровно n целочисленных точек. Уравнение x 2 + y 2 = имеет ровно 4k целочисленных решений, причём одно из чисел x и y чётно, а другое нечётно. Поэтому уравнение (2z − 1) 2 + (2t) 2 = имеет ровно 2k целочисленных решений. 24.14. Рассмотрим все выпуклые фигуры, получающиеся изданной переносами на векторы, обе координаты которых чётны. Докажем, что хотя бы две из этих фигур пересекаются. Исходную фигуру можно заключить вкруг радиуса R с центром вначале координат, причём R можно выбрать целым числом. Возьмём те из рассматриваемых фигур, координаты центров которых Рис. являются неотрицательными числами, не превосходящими. Этих фигур ровно (n + штуки все они лежат внутри квадрата со стороной 2(n + Если бы они не пересекались, то при любом выполнялось бы неравенство (n + 1) 2 S < 4(n + где S — площадь данной фигуры. Но так как S > то n можно выбрать так, чтобы выполнялось неравенство) Пусть теперь фигуры с центрами и имеют общую точку A рис. 24.4). Докажем, что тогда середина M отрезка принадлежит обеим фигурам (ясно, что точка M имеет целые координаты). Пусть # – O 1 B = − # – O 2 A. Так как данная фигура центрально симметрична, точка принадлежит фигуре с центром O 1 . Эта фигура выпукла, и точки A и принадлежат ей, поэтому ей принадлежит также середина отрезка AB. Ясно, что середина отрезка AB совпадает с серединой отрезка а) Пусть охотник находится в точке O, а заяц — в точке A; A 1 — точка, симметричная A относительно O. Рассмотрим фигуру Φ, содержащую все Рис. точки, расстояние от которых до отрезка не превосходит r рис. 24.5). Достаточно доказать, что Φ содержит хотя бы один узел решётки (если узел попадает в заштрихованную часть, то точка принадлежит стволу дерева). Площадь Φ равна 4rh + p r 2 , где h — расстояние от охотника до зайца. Если h > 1/r, то 4rh + p r 2 > 4. По теореме Минковско- го Φ содержит целочисленную точку. б) Рассмотрим прямоугольник с вершинами (0, 0), (0, 1), (n, 1) и (n, Покажем, что изначала координат можно увидеть точку (n, 1). Действительно, расстояния от точек (1, 0) и (n − 1, 1) до прямой, проходящей через точки, 0) и (n, 1), равно. Поэтому деревья, растущие в этих точках, не пересекают указанную прямую. Остальные деревья её тем более не пересекают. 24.16. Прежде всего докажем, что если внутри выпуклой фигуры с площадью S и полупериметром p нет точек целочисленной решётки, то существует выпуклая фигура с площадью S 0 = S и полупериметром p 0 6 p, Глава 24. Целочисленные решётки внутри которой нет точек целочисленной решётки и которая симметрична относительно прямых x = 1/2 и y = 1/2. Затем для фигуры мы докажем, что S 0 6 Фигура строится по фигуре Φ следующим образом. Сначала мы берём симметризацию по Штейнеру фигуры Φ относительно прямой x = 1/2, а затем для полученной фигуры рассматриваем симметризацию по Штейнеру относительно прямой y = 1/2. При симметризации по Штейнеру снова получается выпуклая фигура (задача, её площадь не изменяется, а периметр не увеличивается (задача. Предположим, что промежуточная фигура содержит целочисленную точку (m, n). Эта фигура симметрична относительно прямой x = 1/2, поэтому она содержит точку (−m + 1, n). Следовательно, прямая y = n пересекает фигуру Φ по отрезку, длина которого не меньше − 1| > 1. Но тогда фигура Φ должна содержать целочисленную точку. Приходим к противоречию. Аналогично доказывается, что фигура не содержит целочисленных точек. Докажем теперь, что S 0 6 p 0 . Для этого рассмотрим два случая. Фигура не содержит точек (x, y), для которых x > 3/2 или y > Тогда фигура целиком содержится в фигуре, заштрихованной на рис. 24.6. x y 0 −1/2 −1/2 1 3/2 Рис. Нужно лишь объяснить, почему от квадрата со стороной 2 отрезаны угловые квадратики со стороной 1/2. Это связано стем, что если для любой точки углового квадратика рассмотреть ещё точки, симметричные ей относительно прямых x = 1/2 и y = 1/2 и относительно точки (1/2, 1/2), то выпуклая оболочка этих четырёх точек будет содержать целочисленные точки (например, начало координат. Таким образом, S 0 6 3. Поэтому согласно изопериметриче- скому неравенству S 0 /p 0 6 √ S 0 / p 6 √ 3/ p < 1. 2. Фигура содержит точку (x, y), для которой x > 3/2 или y > Пусть для определённости наибольшая координата x точек фигуры равна > 3/2. Рассмотрим точку (a, b) фигуры с наибольшей координатой y. Яс- Решения задач 477 но, что b < 1, поскольку иначе прямоугольник с вершинами (a, b), (−a + 1, b), (−a + 1, −b + 1), (a, −b + 1) содержал бы целочисленные точки. Часть фигуры, состоящая из точек (x, y), для которых x > 1/2 и y > 1/2, принадлежит трапеции, заштрихованной на рис. 24.7, поэтому площадь этой части 1/2 3/2 1/2 (1, 1) (a, b) x = Рис. не превосходит 2 a − 1 2 . Следовательно, S 0 6 2 a − 1 2 . Ясно также, что 2 a − 1 Согласно задаче 24.16 достаточно доказать, что если S > np, то можно разрезать на n выпуклых фигуру каждой из которых площадь больше полупериметра. Применим индукцию по n. Для n = 1 утверждение очевидно. Предположим, что оно доказано для n; докажем его для n + Пусть S > (n + 1)p для некоторой фигуры Φ. Разрежем эту фигуру прямой на две фигуры и Φ 2 , площади которых равны S 1 = 1 n + 1 S и S 2 = n n + Пусть и p 2 — полупериметры этих фигур. Ясно, что p 1 < p и p 2 < p. Поэтому p > и S 2 > np > np 2 . Применив предположение индукции к фигуре получаем требуемое. 24.18. Рассмотрим решётку, заданную уравнениями x = k + 1/2 и y = l + где k и l — целые числа. Докажем, что каждый квадрат этой решётки даёт неотрицательный вклад в величину n − S + p. Рассмотрим два случая. Фигура содержит центр квадрата. Тогда n 0 = 1 и S 0 6 1, поэтому S 0 + p 0 > 0. 2. Фигура пересекает квадратно не содержит его центр. Докажем, что в этом случае S 0 6 p 0 . Если фигура целиком лежит в этом квадрате, то согласно изопериметрическому неравенству S 0 /p 0 6 √ S 0 / p 6 √ 1/ p < 1. Если рассматриваемая часть фигуры ограничена стороной квадрата и некоторой кривой, то согласно задаче 6 √ 2S 0 / p 6 √ 2/ p < 1. Поэтому остаётся рассмотреть случаи, когда рассматриваемая часть фигуры ограничена сторонами квадрата и кривой, соединяющей либо противоположные, либо смежные стороны квадрата. При этом можно считать, что центр O квадрата лежит Глава 24. Целочисленные решётки Рис. на границе фигуры (рис. 24.8). Действительно, для кривой, соединяющей противоположные стороны, можно применить параллельный переноса для кривой, соединяющей смежные стороны, — гомотетию с центром в их общей вершине. В обоих случаях отношение S 0 /p 0 увеличится. Так как расстояния от центра квадрата до его сторон равны 1/2, то 1/2. Проведя через точку O опорную прямую к данной фигуре, получим, что S 0 6 Ясно также, что все вклады квадратов не могут быть одновременно нулевыми ГЛАВА РАЗРЕЗАНИЯ, РАЗБИЕНИЯ, ПОКРЫТИЯ Основные сведения. Во всех задачах этой главы рассматриваются лишь прямолинейные разрезы. Две фигуры называют равносоставленными, если одну из них можно разрезать на части и сложить из них вторую фигуру (нетрудно убедиться, что тогда и вторую фигуру можно разрезать на части, из которых можно сложить первую фигуру. Ясно, что равносоставленные фигуры имеют равные площади. Оказывается, что для многоугольников верно и обратное, те. любые два равновеликих многоугольника равносоставлены (см. задачу 25.8 б). 3. Будем говорить, что фигура Φ покрыта фигурами Φ 1 , . . . , Φ n , если Φ содержится в объединении этих фигур, те. любая точка фигуры Φ принадлежит хотя бы одной из фигур Φ 1 , . . . , Φ n . Если же фигуры Φ 1 , . . . , не пересекаются (точнее говоря, не имеют общих внутренних точек) и их объединение совпадает сто будем говорить, что Φ замощена фигурами Φ 1 , . . . , Φ n |