慕慕的玩具(4)：疯狂对对碰背后的数学模型 Steiner System和Finite Projective Plane(上)

Posted on by
Contents hide
1 对对碰问题的数学描述
2 BIBD问题
3 BIBD问题的计数性质
4 Steiner System and Steiner Triple Systems
5 益智对对碰具体玩具分析
6 Finite Projective Plane简单介绍
7 Finite Projective Plane和Steiner System
8 Projective Planes of Small Order
9 参考资料

慕慕的玩具和游戏背后有很多有趣的算法话题。之前已经写三篇（如下）：

第四篇的游戏是一组卡牌，称为疯狂对对碰，网上很容易买到，如下图：

这个游戏是由一组卡牌，每个卡牌上有一些图标（这里是不同国家的国旗），任何两张卡牌的国旗组合里，有且只有一个共同点（这是我们的游戏经验）。家人陪慕慕玩这个游戏的办法是，洗牌，然后每个人分同样多的牌，每次各出一张，最快发现唯一相同国旗的人，赢走两张牌。最后计赢取的牌的数目决定胜负。

我曾经花过一些时间研究这个问题，想思考如何构造这个牌组，以及这个模型背后的组合结构。可惜不得其法，自己思考没有得出什么有用的东西。最近我把这个问题丢给了DeepSeek，DeepSeek告诉我这是Steiner System，属于组合构造问题（Design Theory）。有了关键字后，我搜索了一些资料，对这个话题有了初步理解。

对对碰问题的数学描述

集合\mathcal{V}表示所有国旗，每张卡牌上有k个不同的国旗，任一张卡牌用B表示，B就是集合\mathcal{V}的某个尺寸是k的非空子集。一组卡牌\mathcal{B}就是B构成的集合。要求\forall B_1, B_2 \in \mathcal{B}, B_1 \ne B_2 \implies | B_1 \cap B_2 | = 1 .

BIBD问题

Balanced Incomplete Block Designs问题我们先给出Design的定义，然后再给出BIBD问题的定义。

Design的定义:

  • 一个二元元组(\mathcal{V}, \mathcal{B}), 其中
  • \mathcal{V}是基本元素的集合，每个元素也可以称为一个point
  • \mathcal{B}是由一系列\mathcal{V}的非空子集构成的multiset，称之为blocks

BIBD的定义：

  • 有三个参数v,k,\lambda，都是正数，且v > k \ge 2
  • 一个(v,k,\lambda)\text{-BIBD}是一个Design (\mathcal{V}, \mathcal{B})且满足如下条件：
    • |\mathcal{V}| = v ,
    • \forall B \in \mathcal{B}, |B| = k,
    • \forall v_1, v_2 \in \mathcal{V}, v_1 \ne v_2 \implies \text{there is one and only one satisfying } B \in \mathcal{B} \ \ v_1 \in B \land v_2 \in B.

维基百科里 Kirkman’s schoolgirl problem 的任何一组解答都是一个15,3,1\text{-BIBD}。我们把第一个解，列在下面：

  • \mathcal{V} = \{A, B, C, D, E, F, G, H, I, J, K, L, M, N, O\}, |\mathcal{V}|=15
  • |\mathcal{B}|=35, 全部列在下面：
    • B_1=\{A,B,C\}, B_2=\{D,E,F\}, B_3=\{G,H,I\}, B_4=\{J,K,L\}, B_5=\{M,N,O\}
    • B_6=\{A,D,G\}, B_7=\{B,E,H\}, B_8=\{C,J,M\}, B_9=\{F,K,N\}, B_{10}=\{I,L,O\}
    • B_{11}=\{A,E,O\},B_{12}=\{B,I,J\}, B_{13}=\{C,D,N\}, B_{14}=\{F,H,L\}, B_{15}=\{G,K,M\}
    • B_{16}=\{A,I,M\}, B_{17}=\{B,D,L\},B_{18}=\{C,E,K\},B_{19}=\{F,G,O\},B_{20}=\{H,J,N\}
    • B_{21}=\{A,F,J\},B_{22}=\{B,K,O\},B_{23}=\{C,G,L\},B_{24}=\{D,H,M\},B_{25}=\{E,I,N\}
    • B_{26}=\{A,H,K\},B_{27}=\{B,G,N\}, B_{28}=\{C,F,I\},B_{29}=\{D,J,O\},B_{30}=\{E,L,M\}
    • B_{31}=\{A,L,N\},B_{32}=\{B,F,M\},B_{33}=\{C,H,O\},B_{34}=\{D,I,K\},B_{35}=\{E,G,J\}

用Greenplum做验证如下：

gpadmin=# create table Bs(c1 text, c2 text, c3 text) distributed randomly;
CREATE TABLE
gpadmin=# copy Bs from stdin with DELIMITER ',';
A,B,C
D,E,F
G,H,I
J,K,L
M,N,O
A,D,G
B,E,H
C,J,M
F,K,N
I,L,O
A,E,O
B,I,J
C,D,N
F,H,L
G,K,M
A,I,M
B,D,L
C,E,K
F,G,O
H,J,N
A,F,J
B,K,O
C,G,L
D,H,M
E,I,N
A,H,K
B,G,N
C,F,I
D,J,O
E,L,M
A,L,N
B,F,M
C,H,O
D,I,K
E,G,J
\.
COPY 35
gpadmin=# create table V (v text) distributed by (v);
CREATE TABLE
gpadmin=# copy V from stdin;
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
\.
COPY 15

gpadmin=# with
  all_pairs(a) as (select array[x.v, y.v] from V x, V y where x.v < y.v)
select all_pairs.a, count(1)
from all_pairs, Bs
where all_pairs.a <@ array[Bs.c1,Bs.c2,Bs.c3]
group by 1 having count(1) <> 1;
 a | count
---+-------
(0 rows)

gpadmin=# with
  all_pairs(a) as (select array[x.v, y.v] from V x, V y where x.v < y.v)
select count(1) from all_pairs;
 count
-------
   105
(1 row)

gpadmin=# select count(1) from (with
  all_pairs(a) as (select array[x.v, y.v] from V x, V y where x.v < y.v)
select all_pairs.a, count(1)
from all_pairs, Bs
where all_pairs.a <@ array[Bs.c1,Bs.c2,Bs.c3]
group by 1 having count(1) = 1)s;
 count
-------
   105
(1 row)

BIBD问题的计数性质

还是先用Greenplum来分析一下，每个point出现在几个Block里。

gpadmin=# select point, sum(c) from 
(select V.v, (array[V.v] <@ array[c1, c2, c3])::int 
 from V, bs) s(point, c) group by 1 order by 1;
 point | sum
-------+-----
 A     |   7
 B     |   7
 C     |   7
 D     |   7
 E     |   7
 F     |   7
 G     |   7
 H     |   7
 I     |   7
 J     |   7
 K     |   7
 L     |   7
 M     |   7
 N     |   7
 O     |   7
(15 rows)

我们发现上面的例子中，任何一个point都存在于7个Blocks里。关于每个point存在于多少Blocks里，我们有如下定理：

Constant replication number: \text{A } (v,k,\lambda)\text{-BIBD}, \{\mathcal{V}, \mathcal{B}\}; \forall v \in \mathcal{V}, \text{ let } B_v = \{B \in \mathcal{B} | v \in B \}, \text{ then } |B_v| = r = \frac{\lambda (v-1)}{k-1}。

Proof:

任意考虑某个点x \in \mathcal{V}，定义B_x=\{B \in \mathcal{B} | x \in B\}, 且 r_x = |B_x|。我们构造一个集合如下：

I_x = \{ \{y, B\} | y\in \mathcal{V}, y \ne x, B \in \mathcal{B}, x \in B \land y \in B \}.

如果我们任何同属于某个block的元素是友邻，那么上面的集合实际上就是给定某个x后，它所有的友邻和对应的block。接下来我们尝试求|I_x|。

第一步选择y，还有v-1种选择。然后，有了\{x,y\}后，根据定义，存在\lambda个blocks包含这一对元素。从而|I_x| = (v-1) \lambda 。

另一方面，我们可以换一个算法计算。先选择block，则有r_x种选择，然后再选择y，有k-1种选择方案，从而|I_x| = r_x(k-1)。

两种算法的结果必须一致，故而： (v-1) \lambda = r_x (k-1) \implies r_x = \frac{\lambda (v-1)}{k-1}。

QED.

用上面的例子的参数代入，则有 1 * (15-1) / (3-1) = 7 ，和我们用程序计算结果一致。

接下来我们研究集合 \mathcal{B} 的大小。

Number of blocks：\text{A } (v,k,\lambda)\text{-BIBD}, \{\mathcal{V}, \mathcal{B}\}; b = |\mathcal{B}| = \frac{\lambda (v^2 - v)}{k^2 - k} 。

Proof:

还是用老办法，定义一个新的集合，如下：

J = \{ (x, B) | B \in \mathcal{B} \land x \in B \}

我们用两种办法（顺序）求|J|。

第一种先选择x，共有]v中选择，然后再选择B，根据之前已经证明的定义有r种，故而 |J| = vr 。

第二种先选择B，共有b=\mathcal{B}种，然后再选择x，有k种，故而|J| = bk 。

综上两种办法必须一致，则 b = \frac{vr}{k} = \frac{\lambda (v(v-1))}{k(k-1)}

QED.

继续代入上面的例子 1*(15^2-15) / (3^2-3) = 35 ，是吻合的。

Steiner System and Steiner Triple Systems

一个Steiner System有三个参数t,k,n，记为S(t,k,n)，一个点集\mathcal{V}, |\mathcal{V}| = n，一个block集合\mathcal{B}, \forall B \in \mathcal{B}, |B| = k，以及约束条件: \forall V \subset \mathcal{V}, |V| = t \implies \exists \text{ a unique } B \in \mathcal{B}, V \subset B (t < k < n)。

Steiner System也有一些BIBD问题的性质。

S(t,k,n) \text{ exists } \implies S(t-1,k-1,n-1) \text{ exists. }

上面的定理容易证明，就是在一个已经存在的Steiner System彻底删除某个point即可。

S(t,k,n) \text{ exists } \implies {k \choose t} \text{ divides } {n \choose t}.

给定参数v, 一个Steiner Triple Systems记为\text{STS}(v)，它是一个 \{v,3,1\}\text{-BIBD}。故而上面的例子的是一个\text{STS}(15)问题的例子。利用上面的计数相关的定理，我们给出\text{STS}(v)存在的必要条件：

\text{STS}(v) \text{ exists} \implies v \equiv 1,3 (\bmod 6)

Proof:

r=\frac{v-1}{2} \implies v \text{ is odd } \implies v \equiv 1,3,5 (\bmod 6)。

b=\frac{v(v-1)}{6} \text{ be an integer }, then only 1,3 is possible.

QED.

益智对对碰具体玩具分析

家里国旗卡已经不全了，我就直接从京东买了一个新的。共有54张卡牌，每张卡上面有8个不同的图标。

两张卡牌示意图

一个一个输入后，所以卡如下:

     1	章鱼,橘子,鹦鹉,白菜,裙子,长颈鹿,篮球,向日葵
     2	梨子,警车,鹦鹉,西瓜,电瓶车,青蛙,芒果,恐龙
     3	橘子,骆驼,鲸鱼,镜子,青蛙,梳子,西兰花,轮船
     4	梨子,猪,老虎,羽毛球,枫叶,糖果,裙子,轮船
     5	斑马,企鹅,羽毛球,书包,大象,青蛙,剪刀,长颈鹿
     6	手提包,闹钟,鸽子,茶壶,鹦鹉,梳子,糖果,大象
     7	蝴蝶,桃子,大象,胡萝卜,西瓜,轮船,太阳,向日葵
     8	闹钟,骆驼,向日葵,枫叶,斑马,树,电瓶车,瓢虫
     9	斑马,茄子,汽车,白菜,茶壶,裤子,轮船,芒果
    10	手提包,企鹅,鲸鱼,棒棒糖,裙子,芒果,蝴蝶,树
    11	斑马,鹦鹉,猫,棒棒糖,老虎,鼓,太阳,西兰花
    12	章鱼,猫,枫叶,恐龙,裤子,蝴蝶,书包,梳子
    13	手提包,茄子,枫叶,草莓,西兰花,篮球,剪刀,西瓜
    14	猪,橘子,鸽子,斑马,松鼠,蝴蝶,警车,草莓
    15	梨子,企鹅,瓢虫,梳子,白菜,草莓,太阳,乌龟
    16	闹钟,猪,书包,玉米,太阳,镜子,芒果,篮球
    17	茶壶,橘子,桃子,梨子,树,猫,剪刀,玉米
    18	裤子,企鹅,警车,风车,向日葵,玉米,糖果,西兰花
    19	向日葵,青蛙,乌龟,猫,汽车,奶瓶,手提包,猪
    20	苹果,闹钟,桃子,鼓,裤子,青蛙,裙子,草莓
    21	斑马,恐龙,桃子,飞机,糖果,乌龟,鲸鱼,篮球
    22	警车,羽毛球,汽车,梳子,篮球,树,胡萝卜,鼓
    23	梨子,骆驼,松鼠,棒棒糖,裤子,大象,篮球,奶瓶
    24	苹果,糖果,瓢虫,西瓜,橘子,棒棒糖,书包,汽车
    25	白菜,枫叶,鸽子,胡萝卜,飞机,玉米,青蛙,棒棒糖
    26	章鱼,茄子,松鼠,小黄鸭,树,青蛙,太阳,糖果
    27	章鱼,鸽子,芒果,羽毛球,桃子,奶瓶,瓢虫,西兰花
    28	奶瓶,鼓,白菜,镜子,蝴蝶,糖果,电瓶车,剪刀
    29	茄子,飞机,猫,瓢虫,大象,裙子,警车,镜子
    30	斑马,西瓜,毛巾,奶瓶,小黄鸭,玉米,裙子,梳子
    31	风车,飞机,鹦鹉,轮船,书包,奶瓶,树,草莓
    32	章鱼,老虎,汽车,玉米,大象,鲸鱼,电瓶车,草莓
    33	苹果,茄子,鹦鹉,羽毛球,蝴蝶,玉米,乌龟,骆驼
    34	骆驼,汽车,剪刀,恐龙,太阳,风车,裙子,鸽子
    35	风车,橘子,枫叶,鼓,小黄鸭,乌龟,大象,芒果
    36	老虎,西瓜,裤子,长颈鹿,树,镜子,乌龟,鸽子
    37	胡萝卜,毛巾,骆驼,草莓,猫,长颈鹿,糖果,芒果
    38	西兰花,猪,毛巾,苹果,树,大象,恐龙,白菜
    39	风车,茄子,电瓶车,桃子,梳子,猪,长颈鹿,棒棒糖
    40	手提包,骆驼,桃子,警车,老虎,小黄鸭,白菜,书包
    41	茄子,鼓,毛巾,梨子,鸽子,向日葵,书包,鲸鱼
    42	胡萝卜,鹦鹉,剪刀,鲸鱼,猪,小黄鸭,裤子,瓢虫
    43	章鱼,闹钟,毛巾,乌龟,剪刀,棒棒糖,警车,轮船
    44	老虎,芒果,松鼠,梳子,苹果,向日葵,飞机,剪刀
    45	企鹅,毛巾,枫叶,汽车,松鼠,桃子,鹦鹉,镜子
    46	风车,羽毛球,松鼠,闹钟,西瓜,白菜,猫,鲸鱼
    47	西兰花,松鼠,茶壶,裙子,书包,胡萝卜,电瓶车,乌龟
    48	手提包,玉米,松鼠,恐龙,轮船,长颈鹿,瓢虫,鼓
    49	风车,老虎,毛巾,茶壶,瓢虫,青蛙,蝴蝶,篮球
    50	手提包,橘子,飞机,毛巾,裤子,羽毛球,电瓶车,太阳
    51	苹果,电瓶车,猫,企鹅,小黄鸭,篮球,轮船,鸽子
    52	章鱼,骆驼,飞机,猪,企鹅,茶壶,鼓,西瓜
    53	胡萝卜,茄子,恐龙,企鹅,闹钟,奶瓶,老虎,橘子
    54	斑马,梨子,章鱼,胡萝卜,风车,镜子,苹果,手提包

导入到Greenplum里分析一下：

gpadmin=# create table Bs(c1 text, c2 text, c3 text, c4 text,
                c5 text, c6 text, c7 text, c8 text);

copy Bs from '/home/gpadmin/cards' with DELIMITER ',';

create table V as
select distinct v from
(
select unnest(a) as v
from (select array[c1, c2, c3, c4, c5, c6, c7, c8]
      from Bs) s(a)
)q(v);

select count(*) from V;

SELECT 57
 count
-------
    57
(1 row)

结果显示共有57个不同的point。接下来我们看看每个point的分布情况：

(
  select V.v,
         (array[v] &lt;@ array[c1, c2, c3, c4, c5, c6, c7, c8])::int
  from Bs, V
)s(v, flag) group by v;
   v    | cnt
--------+-----
 乌龟   |   8
 书包   |   8
 企鹅   |   8
 剪刀   |   8
 向日葵 |   7
 大象   |   8
 太阳   |   7
 奶瓶   |   7
 小黄鸭 |   6
 恐龙   |   7
 手提包 |   8
 斑马   |   8
 松鼠   |   8
 枫叶   |   7
 树     |   8
 桃子   |   8
 梨子   |   7
 梳子   |   8
 棒棒糖 |   7
 橘子   |   8
 毛巾   |   8
 汽车   |   7
 猪     |   8
 猫     |   8
 玉米   |   8
 瓢虫   |   8
 电瓶车 |   8
 白菜   |   8
 章鱼   |   8
 篮球   |   8
 糖果   |   8
 羽毛球 |   7
 老虎   |   8
 胡萝卜 |   8
 芒果   |   8
 苹果   |   7
 茄子   |   8
 茶壶   |   6
 草莓   |   7
 蝴蝶   |   7
 裙子   |   8
 裤子   |   8
 西兰花 |   7
 西瓜   |   8
 警车   |   7
 轮船   |   8
 镜子   |   7
 长颈鹿 |   6
 闹钟   |   7
 青蛙   |   8
 风车   |   8
 飞机   |   7
 骆驼   |   8
 鲸鱼   |   7
 鸽子   |   8
 鹦鹉   |   8
 鼓     |   8
(57 rows)

我们发现，并不均匀。因此这不是一个严格的BIBD问题。这是因为这个玩具不允许无解的案例存在。我们继续检测是否确保任何两张card都有唯一解：

gpadmin=# create language plpython3u;
create function array_intersection(a text[], b text[]) returns int as
$$
return len(set(a).intersection(set(b)))
$$
language plpython3u;

select * from
(
  select
    x, y,
    array_intersection(array[x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8],
                       array[y.c1, y.c2, y.c3, y.c4, y.c5, y.c6, y.c7, y.c8])
  from Bs x, Bs y
  where x is distinct from y
)s(x,y,i)
where array_length(i, 1) &lt;> 1;

gpadmin=#
select * from
(
  select
    x, y,
    array_intersection(array[x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8],
                       array[y.c1, y.c2, y.c3, y.c4, y.c5, y.c6, y.c7, y.c8])
  from Bs x, Bs y
  where x is distinct from y
)s(x,y,i)
where i &lt;> 1;
 x | y | i
---+---+---
(0 rows)

从上面的结果我们发现了，任何两张卡的交集都全部都是有且只有一个point。我们再研究下，任何两个不一样的point的是否都存在某个卡牌。

gpadmin=# with pairs(x, y) as (select a.v, b. v from V a, V b where a.v &lt; b.v)
select count(distinct pairs)
from pairs left join Bs on
   array[x,y] &lt;@ array[c1, c2, c3, c4, c5, c6, c7, c8]
;
 count
-------
  1596
(1 row)

gpadmin=# with pairs(x, y) as (select a.v, b. v from V a, V b where a.v &lt; b.v)
select count(distinct pairs)
from pairs left join Bs on
   array[x,y] &lt;@ array[c1, c2, c3, c4, c5, c6, c7, c8]
where Bs is null;
 count
-------
    84
(1 row)

gpadmin=# with pairs(x, y) as (select a.v, b. v from V a, V b where a.v &lt; b.v)
select  pairs, count(1)
from pairs left join Bs on
   array[x,y] &lt;@ array[c1, c2, c3, c4, c5, c6, c7, c8]
where Bs is not null group by 1 having count(1) &lt;> 1;
 pairs | count
-------+-------
(0 rows)

我们发现，所有可能的二元对，有84个不存在于任何一张卡里。一个二元对，只要存在卡牌中的，那么只存在于唯一的某个卡牌中。

因此，这套疯狂对对碰，并不是一个标准的steiner system。

接下来我们研究如何构造。这里转入一个接近的话题研究——Finite Projective Plane.

Finite Projective Plane简单介绍

Projective Geometry是一个非欧几何系统。其中的Finite Projective Plane系统和我们今天的话题有重要联系。这里研究的对象Point和Line与我们构造问题里的Point和Block是对应的。Projective Geometry的几条公理，限定Finite Projective Plane的时候，就是下面的几条了(point集合\mathcal{P}, line线集合\mathcal{L})：

  • \mathbf{A_1}: \forall p_1,p_2 \in \mathcal{P}, p_1 \ne p_2 \implies 存在且仅存在唯一一个l \in \mathcal{L} 使得 p1 \in l \land p2 \in l。
  • \mathbf{A_2}: \forall l_1, l_2 \in \mathcal{L}, l_1 \ne l_2 \implies 存在且仅存在唯一一个p \in \mathcal{P} 使得 p \in l_1 \land p \in l_2。
  • \mathbf{A_3}:\exists P', |P'|=4 \land P' \subset \mathcal{P} 且满足 (\forall p_1,p_2,p_3 \in P', p_1 \ne p_2, p_1 \ne p_2, \ne p_2 \ne p_3 则 \nexists l \in \mathcal{L}, p_1 \in l \land p_2 \in l \land p_3 \in l)。

其中上面的\mathbf{A_1},\mathbf{A_2}是对偶的，本质都是某个集合里任何两个不同的元素，都存在且唯一的决定了另一个集合里的一个元素。\mathbf{A_3}也存在它的对偶\mathbf{A_3}^*，\mathbf{A_3} \text{ 和 } \mathbf{A_3}^*旨在规避一些过于简单的平凡案例。

\mathbf{A_3}^*: \exists L' , |L'| = 4, L' \subset \mathcal{L} 且满足\forall l_1, l_2, l_3 \in \mathcal{L}, l_1 \ne l_2, l_1 \ne l_3, l_2 \ne l_3 则 \nexists p \in \mathcal{P}, p \in l_1 \land p \in l_2 \land p \in l_3 。

可以证明 \mathbf{A_1} \land \mathbf{A_2} \land \mathbf{A_3} \implies \mathbf{A_{3}^*} 。这个证明省略了，请参考 The what, how and why of Finite projective planes。

基于这些公理，我们可以推演出Finite Projective Plane系统的一些性质。

定理: 给定一个Finite Projective Plane, \{\mathcal{P}, \mathcal{L}\}。\exists l \in \mathcal{L} \text{ such that } |l| = n+ 1 \implies (\textcircled{1} \land \textcircled{2} \land \textcircled{3}), 三条结论如下:

  • \textcircled{1}: \forall l \in \mathcal{L}, |l| = n+1
  • \textcircled{2}: \forall p \in \mathcal{P}, \text{ let }L_p = \{l \in \mathcal{L} | p \in l\}, |L_p| = n +1
  • \textcircled{3}: |\mathcal{P}| = n^2+n+1 \land |\mathcal{L}| = n^2 + n + 1

满足上面条件的Finite Projective Plane称之为n阶Finite Projective Plane。为了证明上面的定理，我们先看一个引理：给定p_1,p_2,p_3 \in \mathcal{P} 是三个不同的points且不共线，则 p_i \text{ 在}n+1\text{条不同的线上} (i\in [1,3]) \implies (\forall l \in \mathcal{L}, |l|=n+1) 。

引理证明: 根据配置有，\forall l \in \mathcal{L}, \exists p_i (i\in [1,3])，p_i \notin l 。已知p_i可以锁定n+1条线(显然，这些线都和l不一样)。那么这n+1条线，和l的交点是n+1个，这些点全部属于l。显然不可能有更多的点在l上了，因为一旦还有一个多余p'\in l，根据\mathbf{A_1}, p_i,p'唯一锁定了一个新的线，这条线只能是刚刚已经算过了的。故而引理得证\square。

现在让我们来尝试证明一下上面的定理。

定理证明：令 l_0\in \mathcal{L}, |l_0| = n+1。\mathbf{A_3}，存在一个p \in \mathcal{P}, p \notin l_0 。那么对于l_0里的n+1个点, p_j \in l_0, 0 \le j \ne n, 再结合\mathcal{A_1}, 我们可以构造出n+1条线，其中每一条由p,p_j (j\in [0,n])唯一决定。利用这个技巧，我们证明了只要不属于l_0的point，都满足\textcircled{2}。

这时候我们从某个p_0开始，这个p_0从上面的由p \notin l_0 衍生出来的线里找出来。这个p_0可以锁定n+1条线。这时候根据\mathbf{A_3}^*，可以找到某条线l \in \mathcal{L}, p_0 \notin l。则再根据\mathbf{A_2}，p_0锁定的n+1条线，和这个l可以衍生出n+1个点。这就证明了\forall l \in \mathcal{L}, p_0 \notin l \implies |l| = n+1 。

为了完成所有线的证明，接下来我们想办法套用引理，这就需要构造三个点。 \mathbf{A_3} 告诉我们至少有两个点不在l_0上，假定分别是\alpha, \beta。然后我们再从l_0上找两个点\eta, \xi。前面已经证明穿过\alpha或者\beta的线分别都是用n+1条。\alpha, \beta可以唯一锁定一条直线l_{\alpha\beta}，容易证明\forall l \ne l_{\alpha\beta} 都有n+1个点(此处略去具体过程)。故而，我们唯一需要考察就是l_{\alpha\beta}的点的数目。又有\beta \notin l_{\alpha\xi}, |l_{\alpha\xi}|=n+1，以及\eta \notin l_{\alpha\xi} 和穿过\eta的线共有n+1条。这样我们就找到满足引理条件的三个点\alpha, \beta, \eta，至此\textcircled{1}完成。

然后是完成对\textcircled{2}的证明。只需要证明任何l_0上的点。根据\mathbf{A_3^*}，可以找到l_1,l_2，和l_0是三条不同的线，且|l_1| = |l_2| = |l_0| = n + 1 以及 (l_0 \cap l_1 = p_{01}) \ne (l_0 \cap l_2 = p_{02}) 。则\forall p \in l_0，如果p \ne p_{01}我们可以用l_1的所有点和p锁定出n+1条线，且不可能再多一条；否则我们就用l_2。

关于\textcircled{3}的证明：任何两个点，唯一的锁定一条线，那么考虑所有p_0衍生的n+1条线，这些线包含了所有的点。由由于任何两条线都可以锁定一个点，故而总点数就是：n(n+1) + 1。关于线的结论，对偶也容易得出。

定理得证。\square。

二阶的Finite Projective Plane也叫做Fano Plane。有7个点和7条线，示意图为(引用自: https://mathworld.wolfram.com/FanoPlane.html)：

Fano Plane

Finite Projective Plane和Steiner System

根据上面的介绍，一个n阶的Finite Projective Plane就是一个Steiner System S(2,n+1,n^2+n+1)。因此，上面的慕慕的游戏，由于点数目是57=7*8+1[/latex]，故而是一个[katex]7阶的Finite Projective Plane。7是素数，因此存在。构造也有现成算法。这部分算法和程序，我们下一篇博文再写（这篇有点长了）。

Projective Planes of Small Order

在网上搜到了一个现成的资料 https://ericmoorhouse.org/pub/planes/，里面有一个7阶的现成结果：https://ericmoorhouse.org/pub/planes/pg27.txt，贴在下面：

0 1 2 3 4 5 6 7
0 8 9 10 11 12 13 14
0 15 26 27 28 29 30 31
0 16 21 32 41 42 43 44
0 17 22 36 40 50 54 56
0 18 23 33 37 46 51 55
0 19 24 34 38 45 49 53
0 20 25 35 39 47 48 52
1 8 15 16 17 18 19 20
1 9 26 32 33 34 35 36
1 10 22 27 41 45 46 47
1 11 21 31 39 50 53 55
1 12 23 28 38 43 52 54
1 13 25 29 37 42 49 56
1 14 24 30 40 44 48 51
2 8 27 32 37 38 39 40
3 8 23 26 41 48 49 50
4 8 21 30 34 46 52 56
5 8 22 29 35 43 51 53
6 8 24 28 36 42 47 55
7 8 25 31 33 44 45 54
2 9 15 21 22 23 24 25
2 11 17 26 42 45 51 52
2 12 18 29 34 44 47 50
2 10 16 30 35 49 54 55
2 14 20 28 33 41 53 56
2 13 19 31 36 43 46 48
4 9 18 27 42 48 53 54
5 9 17 28 39 44 46 49
3 9 16 31 38 47 51 56
7 9 19 29 40 41 52 55
6 9 20 30 37 43 45 50
5 12 15 32 45 48 55 56
4 11 15 33 40 43 47 49
3 10 15 36 37 44 52 53
7 14 15 35 38 42 46 50
6 13 15 34 39 41 51 54
5 13 16 24 27 33 50 52
3 14 17 25 27 34 43 55
6 11 19 23 27 35 44 56
7 12 20 21 27 36 49 51
4 13 20 22 26 38 44 55
5 14 19 21 26 37 47 54
6 12 16 25 26 40 46 53
7 10 18 24 26 39 43 56
4 10 19 25 28 32 50 51
3 11 20 24 29 32 46 54
7 13 17 23 30 32 47 53
6 14 18 22 31 32 49 52
4 12 17 24 31 35 37 41
4 14 16 23 29 36 39 45
5 11 18 25 30 36 38 41
5 10 20 23 31 34 40 42
3 12 19 22 30 33 39 42
3 13 18 21 28 35 40 45
7 11 16 22 28 34 37 48
6 10 17 21 29 33 38 48

参考资料

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.