Теорема Пика

Формула площади многоугольника сетки

Солнечные лучи Фарея порядка 6 с 1 внутренней (красной) и 96 граничными (зелеными) точками, дающие площадь 1 + ⁠96/2⁠ − 1 = 48 ^[1]

В геометрии теорема Пика дает формулу для площади простого многоугольника с целочисленными координатами вершин в терминах числа целых точек внутри него и на его границе. Результат был впервые описан Георгом Александром Пиком в 1899 году. ^[2] Он был популяризирован на английском языке Хьюго Штейнхаузом в издании 1950 года его книги «Математические снимки» . ^{[3] [4]} Он имеет несколько доказательств и может быть обобщен до формул для определенных видов непростых многоугольников.

Формула

я = 7 , б = 8 , А = я + ⁠б/2⁠ − 1 = 10

Предположим, что многоугольник имеет целочисленные координаты для всех своих вершин. Пусть будет числом целых точек внутри многоугольника, а пусть будет числом целых точек на его границе (включая как вершины, так и точки вдоль сторон). Тогда площадь этого многоугольника равна: ^{[5] [6] [7] [8]} В показанном примере есть внутренние и граничные точки, поэтому его площадь составляет квадратные единицы. ${\displaystyle i}$ ${\displaystyle b}$ ${\displaystyle A}$ $${\displaystyle A=i+{\frac {b}{2}}-1.}$$ ${\displaystyle i=7}$ ${\displaystyle b=8}$ ${\displaystyle A=7+{\tfrac {8}{2}}-1=10}$

Доказательства

По формуле Эйлера

Одно доказательство этой теоремы включает в себя подразделение многоугольника на треугольники с тремя целыми вершинами и без других целых точек. Затем можно доказать, что каждый подразделенный треугольник имеет площадь ровно . Следовательно, площадь всего многоугольника равна половине числа треугольников в подразделении. После связывания площади с числом треугольников таким образом, доказательство завершается использованием многогранной формулы Эйлера для связывания числа треугольников с числом точек сетки в многоугольнике. ^[5] ${\displaystyle {\tfrac {1}{2}}}$

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

Первая часть этого доказательства показывает, что треугольник с тремя целочисленными вершинами и без других целочисленных точек имеет площадь ровно , как утверждает формула Пика. Доказательство использует тот факт, что все треугольники заполняют плоскость , при этом смежные треугольники повернуты на 180° друг относительно друга вокруг их общего ребра. ^[9] Для замощения треугольником с тремя целочисленными вершинами и без других целочисленных точек каждая точка целочисленной сетки является вершиной шести плиток. Поскольку количество треугольников на точку сетки (шесть) в два раза больше количества точек сетки на треугольник (три), треугольники в два раза плотнее на плоскости, чем точки сетки. Любая масштабированная область плоскости содержит в два раза больше треугольников (в пределе, когда масштабный коэффициент стремится к бесконечности), чем количество точек сетки, которые она содержит. Следовательно, каждый треугольник имеет площадь , что и требуется для доказательства. ^[5] Другое доказательство того, что эти треугольники имеют площадь , основано на использовании теоремы Минковского о точках решетки в симметричных выпуклых множествах. ^[10] ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle {\tfrac {1}{2}}}$

Разбиение многоугольника сетки на специальные треугольники

Это уже доказывает формулу Пика для многоугольника, который является одним из этих специальных треугольников. Любой другой многоугольник может быть подразделен на специальные треугольники: добавляйте непересекающиеся отрезки линий внутри многоугольника между парами точек сетки до тех пор, пока больше не будет отрезков линий. Единственными многоугольниками, которые не могут быть подразделены таким образом, являются рассмотренные выше специальные треугольники; следовательно, в результирующем подразделении могут появиться только специальные треугольники. Поскольку каждый специальный треугольник имеет площадь , многоугольник площадью будет подразделен на специальные треугольники. ^[5] ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle A}$ ${\displaystyle 2A}$

Подразделение многоугольника на треугольники образует планарный граф , а формула Эйлера дает уравнение, которое применяется к числу вершин, ребер и граней любого планарного графа. Вершины — это просто точки сетки многоугольника; их всего . Грани — это треугольники подразделения и единственная область плоскости вне многоугольника. Число треугольников равно , поэтому всего граней. Чтобы подсчитать число ребер, заметьте, что в подразделении есть стороны треугольников. Каждое ребро внутри многоугольника является стороной двух треугольников. Однако есть ребра треугольников, которые лежат вдоль границы многоугольника и образуют часть только одного треугольника. Следовательно, число сторон треугольников подчиняется уравнению , из которого можно найти число ребер, . Подстановка этих значений для , и в формулу Эйлера дает Формула Пика получается путем решения этого линейного уравнения для . ^[5] Альтернативный, но похожий расчет заключается в доказательстве того, что количество ребер одного и того же подразделения равно , что приводит к тому же результату. ^[11] ${\displaystyle V-E+F=2}$ ${\displaystyle V=i+b}$ ${\displaystyle 2A}$ ${\displaystyle F=2A+1}$ ${\displaystyle 6A}$ ${\displaystyle b}$ ${\displaystyle 6A=2E-b}$ ${\displaystyle E={\tfrac {6A+b}{2}}}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle V-E+F=2}$ $${\displaystyle (i+b)-{\frac {6A+b}{2}}+(2A+1)=2.}$$ ${\displaystyle A}$ ${\displaystyle E=3i+2b-3}$

Можно также пойти в другом направлении, используя теорему Пика (доказанную другим способом) как основу для доказательства формулы Эйлера. ^{[6] [12]}

Другие доказательства

Альтернативные доказательства теоремы Пика, не использующие формулу Эйлера, включают следующее.

• Можно рекурсивно разложить данный многоугольник на треугольники, позволяя некоторым треугольникам подразделения иметь площадь больше 1/2. И площадь, и количество точек, используемых в формуле Пика, складываются таким же образом, как и друг друга, поэтому истинность формулы Пика для общих многоугольников следует из ее истинности для треугольников. Любой треугольник подразделяет свой ограничивающий прямоугольник на сам треугольник и дополнительные прямоугольные треугольники , и площади как ограничивающего прямоугольника, так и прямоугольных треугольников легко вычислить. Объединение этих вычислений площади дает формулу Пика для треугольников, а объединение треугольников дает формулу Пика для произвольных многоугольников. ^{[7] [8] [13]}
• В качестве альтернативы, вместо использования квадратов сетки, центрированных на узлах сетки, можно использовать квадраты сетки, имеющие вершины в узлах сетки. Эти квадраты сетки разрезают заданный многоугольник на части, которые могут быть переставлены (путем сопоставления пар квадратов вдоль каждого края многоугольника) в полимино с той же площадью. ^[14]
• Теорема Пика может быть также доказана на основе комплексного интегрирования двоякопериодической функции, связанной с эллиптическими функциями Вейерштрасса . ^[15]
• Применение формулы суммирования Пуассона к характеристической функции многоугольника приводит к другому доказательству. ^[16]

Теорема Пика была включена в веб-список «100 лучших математических теорем» 1999 года, который позже стал использоваться Фриком Видейком в качестве эталонного набора для проверки мощности различных помощников доказательства . По состоянию на 2024 год ^{[обновлять]}теорема Пика была формализована и доказана только в двух из десяти помощников доказательства, записанных Видейком. ^[17]

Обобщения

я = 2 , б = 12 , ч = 1 , А = я + ⁠б/2⁠ + ч − 1 = 8

Обобщения теоремы Пика на непростые многоугольники более сложны и требуют больше информации, чем просто количество внутренних и граничных вершин. ^{[3] [18]} Например, многоугольник с h отверстиями , ограниченный простыми целочисленными многоугольниками, не пересекающимися друг с другом и с границей, имеет площадь ^[19] Также возможно обобщить теорему Пика на области, ограниченные более сложными планарными прямолинейными графами с целочисленными координатами вершин, используя дополнительные термины, определенные с помощью эйлеровой характеристики области и ее границы, ^[18] или на многоугольники с одним граничным многоугольником, который может пересекать себя, используя формулу, включающую число оборотов многоугольника вокруг каждой целочисленной точки, а также его общее число оборотов. ^[3] $${\displaystyle A=i+{\frac {b}{2}}+h-1.}$$

Тетраэдры Рива, показывающие, что теорема Пика неприменима в высших измерениях

Тетраэдры Рива в трех измерениях имеют четыре целые точки в качестве вершин и не содержат других целочисленных точек, но не все имеют одинаковый объем. Поэтому не существует аналога теоремы Пика в трех измерениях, который выражает объем многогранника как функцию только его числа внутренних и граничных точек. ^[20] Однако эти объемы можно вместо этого выразить с помощью полиномов Эрхарта . ^{[21] [22]}

Похожие темы

Несколько других математических тем связывают площади областей с количеством точек сетки. Теорема Блихфельдта утверждает, что любая фигура может быть преобразована так, чтобы содержать по крайней мере ее площадь в точках сетки. ^[23] Задача о круге Гаусса касается ограничения ошибки между площадями и количеством точек сетки в кругах. ^[24] Задача подсчета целых точек в выпуклых многогранниках возникает в нескольких областях математики и информатики. ^[25] В прикладных областях точечный планиметр представляет собой основанное на прозрачности устройство для оценки площади фигуры путем подсчета точек сетки, которые она содержит. ^[26] Последовательность Фарея представляет собой упорядоченную последовательность рациональных чисел с ограниченными знаменателями, анализ которой включает теорему Пика. ^[27]

Другим простым методом вычисления площади многоугольника является формула шнурка . Она дает площадь любого простого многоугольника как сумму членов, вычисленных из координат последовательных пар его вершин. В отличие от теоремы Пика, формула шнурка не требует, чтобы вершины имели целочисленные координаты. ^[28]

Ссылки

1. Кираджиев, Кристиан (октябрь 2018 г.). «Соединяя точки с теоремой Пика» (PDF) . Mathematics Today . С. 212–214.
2. Пик, Георг (1899). «Геометрические исследования Zahlenlehre». Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen "Lotos" в Праге . (Нойе Фольге). 19 : 311–319. ЖФМ  33.0216.01.CiteBank:47270
3. Грюнбаум, Бранко ; Шепард, GC (февраль 1993). «Теорема Пика». The American Mathematical Monthly . 100 (2): 150–161. doi :10.2307/2323771. JSTOR  2323771. MR  1212401.
4. Штейнхаус, Х. (1950). Математические снимки . Oxford University Press. стр. 76. MR  0036005.
5. Aigner, Martin ; Ziegler, Günter M. (2018). "Три приложения формулы Эйлера: теорема Пика". Доказательства из THE BOOK (6-е изд.). Springer. стр. 93–94. doi :10.1007/978-3-662-57265-8. ISBN 978-3-662-57265-8.
6. Wells, David (1991). «Теорема Пика». Словарь любопытной и интересной геометрии издательства Penguin . Penguin Books. С. 183–184.
7. Бек, Маттиас; Робинс, Синай (2015). "2.6 Теорема Пика". Вычисление непрерывного дискретно: перечисление целых точек в многогранниках . Бакалаврские тексты по математике (2-е изд.). Springer. стр. 40–43. doi :10.1007/978-1-4939-2969-6. ISBN 978-1-4939-2968-9. МР  3410115.
8. Ball, Keith (2003). "Глава 2: Подсчет точек". Странные кривые, подсчет кроликов и другие математические исследования . Princeton University Press, Принстон, Нью-Джерси. С. 25–40. ISBN 0-691-11321-1. МР  2015451.
9. Мартин, Джордж Эдвард (1982). Геометрия преобразований. Бакалаврские тексты по математике. Springer-Verlag. Теорема 12.1, стр. 120. doi :10.1007/978-1-4612-5680-9. ISBN 0-387-90636-3. МР  0718119.
10. Ram Murty, M.; Thain, Nithum (2007). «Теорема Пика через теорему Минковского». The American Mathematical Monthly . 114 (8): 732–736. doi :10.1080/00029890.2007.11920465. JSTOR  27642309. MR  2354443. S2CID  38855683.
11. Funkenbusch, WW (июнь–июль 1974 г.). «От формулы Эйлера к формуле Пика с использованием теоремы о ребре». Classroom Notes. The American Mathematical Monthly . 81 (6): 647–648. doi :10.2307/2319224. JSTOR  2319224. MR  1537447.
12. ДеТемпл, Дуэйн; Робертсон, Джек М. (март 1974 г.). «Эквивалентность теорем Эйлера и Пика». Учитель математики . 67 (3): 222–226. doi :10.5951/mt.67.3.0222. JSTOR  27959631. MR  0444503.
13. Варберг, Дейл Э. (1985). «Повторный взгляд на теорему Пика». The American Mathematical Monthly . 92 (8): 584–587. doi :10.2307/2323172. JSTOR  2323172. MR  0812105.
14. Trainin, J. (ноябрь 2007 г.). «Элементарное доказательство теоремы Пика». The Mathematical Gazette . 91 (522): 536–540. doi :10.1017/S0025557200182270. JSTOR  40378436. S2CID  124831432.
15. -функцию Вейерштрасса ». The American Mathematical Monthly . 102 (5): 431–437. doi :10.2307/2975035. JSTOR  2975035. MR  1327788. ${\displaystyle \wp }$
16. Брандолини, Л.; Колзани, Л.; Робинс, С.; Травальини, Г. (2021). «Теорема Пика и сходимость кратных рядов Фурье». The American Mathematical Monthly . 128 (1): 41–49. doi :10.1080/00029890.2021.1839241. MR  4200451. S2CID  231624428.
17. Видейк, Фрик. «Формализация 100 теорем». Институт компьютерных и информационных наук Университета Радбауд . Проверено 20 февраля 2024 г.
18. Rosenholtz, Ira (1979). «Вычисление площадей поверхности по чертежу». Mathematics Magazine . 52 (4): 252–256. doi :10.1080/0025570X.1979.11976797. JSTOR  2689425. MR  1572312.
19. Санкар, П. В.; Кришнамурти, Э. В. (август 1978 г.). «О компактности подмножеств цифровых изображений». Компьютерная графика и обработка изображений . 8 (1): 136–143. doi :10.1016/s0146-664x(78)80021-5.
20. Рив, Дж. Э. (1957). «Об объеме решетчатых многогранников». Труды Лондонского математического общества . Третья серия. 7 : 378–395. doi :10.1112/plms/s3-7.1.378. MR  0095452.
21. Бек и Робинс (2015), 3.6 «От дискретного к непрерывному объему многогранника», стр. 76–77
22. Диас, Рикардо; Робинс, Синай (1997). «Многочлен Эрхарта решетчатого многогранника». Annals of Mathematics . Вторая серия. 145 (3): 503–518. doi :10.2307/2951842. JSTOR  2951842. MR  1454701.
23. Олдс, CD ; Лакс, Аннели ; Давидофф, Джулиана П. (2000). «Глава 9: Новый принцип в геометрии чисел». Геометрия чисел . Новая математическая библиотека Аннели Лакс. Том 41. Математическая ассоциация Америки, Вашингтон, округ Колумбия. С. 119–127. ISBN 0-88385-643-3. МР  1817689.
24. Гай, Ричард К. (2004). "F1: проблема точек решетки Гаусса". Нерешенные проблемы теории чисел . Задачники по математике. Т. 1 (3-е изд.). Нью-Йорк: Springer-Verlag. С. 365–367. doi :10.1007/978-0-387-26677-0. ISBN 0-387-20860-7. МР  2076335.
25. Барвинок, Александр (2008). Целые точки в многогранниках . Цюрихские лекции по высшей математике. Цюрих: Европейское математическое общество. doi : 10.4171/052. ISBN 978-3-03719-052-4. МР  2455889.
26. Беллхаус, DR (1981). «Оценка площади с помощью методов подсчета точек». Биометрия . 37 (2): 303–312. doi :10.2307/2530419. JSTOR  2530419. MR  0673040.
27. Брукхаймер, Максим; Аркави, Абрахам (1995). «Ряды Фэри и теорема Пика о площадях». The Mathematical Intelligencer . 17 (4): 64–67. doi :10.1007/BF03024792. MR  1365013. S2CID  55051527.
28. Брейден, Барт (1986). «Формула площади геодезиста» (PDF) . The College Mathematics Journal . 17 (4): 326–337. doi :10.2307/2686282. JSTOR  2686282. Архивировано из оригинала (PDF) 2015-04-06 . Получено 2021-07-04 .

Внешние ссылки

• Теорема Пика Эда Пегга-младшего , проект Wolfram Demonstrations .
• Число Пи с использованием теоремы Пика Марка Даббса, GeoGebra