Теперь мы можем доказать теорему Пика. Сначала построим триангуляцию многоугольника — разобьем его на T примитивных треугольников (как показано на рис. 13.12). Если считать неограниченную область гранью, то F = T + 1. Поскольку площадь каждой треугольной грани равна 1/2, то полная площадь многоугольника A = (1/2)T.
Рис. 13.12. Многоугольник разбит на примитивные треугольники
У каждой ограниченной грани три стороны, поэтому в величине 3T каждое ребро учтено дважды, за исключением граничных ребер, которые учитываются один раз. Поскольку число граничных ребер равно числу расположенных на границе вершин, имеем
3T = 2E — B,
или
Количество вершин V = I + B. Применяя формулу Эйлера, получаем
2 = V — Е + F;
Поэтому число треугольных граней равно
T = 2I + B — 2,
а полная площадь равна
что и требовалось доказать.
И в заключение опишем две игры с карандашом и бумагой. Несмотря на сходство, одна является интеллектуальным вызовом, а другая — насмешкой над игроками, поскольку исход известен еще до того, как сделан первый ход.
По словам Мартина Гарднера (1914–2010), который долгое время вел математическую колонку в журнале «Scientific American», игру «Рассада» придумали за чашкой чая одним февральским утром 1967 года Джон Хортон Конвей (1937–2020) и Майкл Патерсон из Кембриджского университета. Она стала сенсацией. Конвей писал Гарднеру, что «на следующий день после того, как рассада проросла, в нее, казалось, играли все. Во время перерыва на чай или кофе собирались группки людей, склонившихся над фантастически нелепыми позициями рассады»107.
В начале игры на чистом листе бумаги рисуется несколько точек. Затем игроки по очереди ходят. Ход заключается в том, что игрок соединяет линией (прямой или кривой) две точки либо рисует петлю, начинающуюся и заканчивающуюся в какой-то точке, а потом ставит на этой линии новую точку. Правила очень простые: линии не должны пересекаться, линия не должна проходить через ранее поставленные точки, из каждой точки не должно исходить более трех точек. Победителем считается игрок, сделавший последний возможный ход. На рис. 13.13 показана игра с двумя начальными точками, в которой игрок 2 выигрывает на четвертом ходу.
Рис. 13.13. Игрок 2 выигрывает в «Рассаду»
Чем больше точек нарисовано в начале, тем дольше длится игра, но бесконечно продолжаться она не может. В начале игры с n точками существует 3n мест для присоединения ребра. После проведения каждого нового ребра количество свободных мест уменьшается на единицу (два места использованы, одно добавилось). Поэтому самая длинная игра не может продолжаться более 3п — 1 ходов.
Оказывается, что при небольших n преимущество есть у первого или второго игрока, в зависимости от числа точек. Если в начале игры всего две точки, то второй игрок всегда может делать ходы, гарантированно приводящие к выигрышу. Это верно также для n = 1, 6, 7, 8. С другой стороны, первый игрок имеет преимущество при n = 3, 4, 5, 9, 10, 11. Большая часть этих случаев (n > 6) была проверена на компьютере108. Для следующих значений n неизвестно, имеет ли какой-то игрок преимущество. Хотя теоретически эта игра несправедлива, конкретная выигрышная стратегия известна только для самых малых n. В любом случае на практике для выигрыша нужно приложить интеллектуальные усилия.
Впоследствии Конвей придумал вариант «Рассады», который назвал «Брюссельская капуста». Вначале рисуется не n точек, а n плюсиков. Игроки по очереди соединяют свободные концы плюсиков линией и ставят на ней новый плюсик (с двумя свободными концами) (см. рис. 13.14). В отличие от «Рассады», правила «Брюссельской капусты» позволяют сходиться в одной вершине четырем ребрам. Как и раньше, победителем считается игрок, сделавший последний ход. Как выяснилось, забавное название «Брюссельская капуста» было намеком на то, что и сама игра шуточная.