Математика, которая мне нравится

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

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

Теорема Пика. Пусть — число целочисленных точек внутри многоугольника, — количество целочисленных точек на его границе, — его площадь. Тогда справедлива формула Пика:

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

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

Доказательство теоремы Пика. Сначала заметим, что формула Пика верна для единичного квадрата. Действительно, в этом случае мы имеем и .

Рассмотрим прямоугольник со сторонами, лежащими на линиях решетки. Пусть длины его сторон равны и . Имеем в этом случае и, по формуле Пика,

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

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

Остается сделать последний шаг: перейти от треугольников к многоугольникам. Любой многоугольник можно разбить на треугольники (например, диагоналями). Поэтому нужно просто доказать, что при добавлении любого треугольника к произвольному многоугольнику формула Пика остается верной.

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

— число внутренних целочисленных точек нового многоугольника,

— число граничных точек нового многоугольника.

Из этих равенств получаем

Так как мы предположили, что теорема верна для и для по отдельности, то

Тем самым, формула Пика доказана.

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

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

Однако некоторое обобщение получается с помощью полиномов Эрхарта.

Источники: http://en.wikipedia.org/wiki/Pick’s_theorem
http://e-maxx.ru/algo/pick_grid_theorem