几何与组合中的一些问题

皮克定理

Theorem (Pick)

对于一个顶点坐标均是整数（顶点均为格点）的简单多边形，其面积满足

Copy LaTeX 内部格点个数 边界格点个数

其中边界格点包括多边形的顶点和其它在边界上的格点。

Proof

分成两个阶段进行证明，首先引入一个概念：称一个三角形为格点三角形（本原三角形），如果三角形的顶点是格点，但是边界和内部不含其它格点。我们首先证明：任意格点三角形的面积均为 $\frac12$ 。不妨设格点三角形的三个点坐标为 $O: (0,0)$ , $A: (x_1,y_1)$ , $B: (x_2,y_2)$ ，那么可以据此定义一个坐标变换

Copy LaTeX

格点三角形的性质可以保证，这个坐标变换是 $\mathbb{Z}^2$ 到自身的双射，因此这个矩阵可逆，并且逆矩阵也是一个整数矩阵，这可以保证

Copy LaTeX

因此 $S_{\Delta\,OAB} = \frac12 |x_2 y_1 - x_1 y_2| = \frac12$ .

一个顶点为格点的多边形总是可以剖分为若干个格点三角形，可以证明划分的格点三角形个数是固定的，并且满足如下关系

Copy LaTeX 划分的格点三角形个数 内部格点个数 边界格点个数

可以通过对内角和算两次进行证明：剖分后的格点三角形内角和显然为

Copy LaTeX 划分的格点三角形个数

也可以通过对格点的分类进行计算，首先边界格点分为两类

Copy LaTeX 边界格点个数 顶点个数 非顶点的边界格点个数

三类格点对内角和的贡献分别为：

顶点： $(\textnormal{顶点个数} - 2) \times \pi$ ；（即整个多边形的内角和）
非顶点的边界格点： $\textnormal{非顶点的边界格点个数} \times \pi$ ；
内部格点： $\textnormal{内部格点个数} \times 2\pi$ 。

因此

Copy LaTeX 划分的格点三角形个数 顶点个数 非顶点的边界格点个数 内部格点个数

Copy LaTeX 划分的格点三角形个数 内部格点个数 边界格点个数

这个等式的右侧与剖分无关，因此剖分得到的格点三角形个数是固定的。由于每一个格点三角形的面积必然为 $\frac12$ ，因此

Copy LaTeX 划分的格点三角形个数 内部格点个数 边界格点个数

Remark

皮克定理在高维情况并不适用。皮克定理和欧拉公式（ $V-E+F=2$ ）有密切联系。

欧拉公式

Theorem (欧拉公式)

对于任何一个凸多面体，始终满足

Copy LaTeX

其中 $V$ 是顶点数， $E$ 是棱数， $F$ 是面数。（ $2$ 其实就是欧拉示性数）

Example

例如对于立方体， $V = 8$ ， $E = 12$ ， $F = 6$ 。

凸正多面体（柏拉图立体）

Definition

称一个凸多面体是凸正多面体（柏拉图立体），如果满足：所有面都是全等的正多边形，而且每一个顶点处有相同数目的棱相交。

记凸正多面体的每一个面为正 $p$ 多边形，每一个顶点有 $q$ 条棱相交，显然 $p,q \geqslant 3$ 。

Proposition

凸正多面体（柏拉图立体）只有五种，分别是：正四面体（ $p=3,q=3$ ）；立方体（ $p=4,q=3$ ）；正八面体（ $p=3,q=4$ ）；正十二面体（ $p=5,q=3$ ）；正二十面体（ $p=3,q=5$ ）。

五种凸正多面体

五种凸正多面体（柏拉图立体）

Proof

可以基于欧拉公式给出证明。由于每条边被两个面共享，每个面有 $p$ 条边；每个顶点对应 $q$ 条棱，每个棱对应两个顶点。对边以三种方式进行计数得到

Copy LaTeX

代入欧拉公式可得

Copy LaTeX

整理得到

Copy LaTeX

并且有 $p,q \geqslant 3$ 。凸正多面体的存在性要求找到整数对 $(p,q)$ 同时满足如下要求

Copy LaTeX

注意到若 $p \geqslant 6$ ，由于

Copy LaTeX

必然无解，同理若 $q \geqslant 6$ 也无解。因此只剩下 $p,q \in \{3,4,5\}$ 的九种候选情形，而且由于所有条件关于 $p,q$ 有对称性，只需要枚举验证六种情况即可，过程略。

正方形剖分为小正方形

Problem

证明一个正方形可以拆分为 $n$ 个（大小可以不同的）小正方形，其中 $n$ 是不为 $2,3,5$ 的所有正整数。

Solution

直接构造即可，如下图所示，取 $k \geqslant 1$ ，这两种方式就可以覆盖题目要求的所有情况。

Copy LaTeX

正方形剖分示意图

满二叉树的叶子数与节点数

Proposition

对于一棵满二叉树（即每个内部节点都恰好有2个子节点），若其叶子节点数为 $d$ ，则总结点数 $N = 2d - 1$ 。

Proof

设内部节点数为 $I$ ，则 $N = I + d$ 。以下给出两种等价证明。

方法一（递归归纳法）： 当 $d=1$ 时，树仅含根节点， $N=1=2\cdot1-1$ ，结论成立。假设对于叶子数少于 $d$ 的满二叉树均成立。对于叶子数为 $d$ （ $d\ge2$ ）的满二叉树，根节点分左右两子树，设左、右子树叶子数分别为 $d_1,d_2$ ，且 $d_1+d_2=d$ 。由归纳假设，左右子树节点数分别为 $2d_1-1$ 和 $2d_2-1$ ，故整棵树

Copy LaTeX

归纳完成。

方法二（图论、算两次）： 对树的边数量 $E$ 算两次：

第一次“向上数”：除根节点外，每个节点有且仅有一条边连向父节点，故 $E = N - 1$ 。
第二次“向下数”：由于每个内部节点恰好向下发出2条边（满二叉树性质），故 $E = 2I$ 。

因此

Copy LaTeX

结合 $N=I+d$ 可以解得

Copy LaTeX