首先在平面上取三点构成一个三角形,在其内部另放 $n$ 个点,且所有点两两连线均不共线,共计顶点数 $V=n+3$。玩家轮流从任意两点之间添加一条线段,要求新线段不与已有线段相交;无法继续者为输。
答案由于任何非三角形的面都可再加入对角线,游戏结束时所得图恰为关于这 $V$ 个顶点的平面三角剖分。记边数为 $E$,面数(包含外部无限区域)为 $F$,则每个面均为三角形有
$$
2E=3F
$$
又由欧拉公式
$$
V - E + F = 2
$$
联立可得
$$
E = 3V - 6 = 3(n+3) - 6 = 3n + 3.
$$
因此游戏必进行恰好 $3n+3$ 步。若 $n$ 为偶数,则 $3n+3$ 为奇数,先手走最后一子后对手无路可走,先手必胜;若 $n$ 为奇数,则 $3n+3$ 为偶数,后手必胜。 |