我曾经玩过一款名为“set”的休闲卡牌桌游，中文名叫“神奇形色牌”。这个翻译还不错，因为游戏中有两个要素确实是关于形状和颜色。
它是是一款考验观察力的休闲卡牌游戏，规则非常简单。游戏中有81张卡牌：
（上图：SET游戏中的全部卡牌。图片中有些卡牌是黄色背景的，稍后解释黄色背景的含义。）
每张卡牌中有一个图形，每个图形有四个要素：数量、形状、颜色、纹理。而每一种要素都有三种取值情况。
对数量要素，每张卡牌上的图形数量都是1到3个。形状有椭圆、菱形和波浪形三种情况。颜色有红、绿、蓝三种情况。纹理有空心、实心和竖线三种情况。
因为有4个要素，每种要素有3种取值，那么总的可以组合出的卡牌数量为张卡牌。
这81张牌，就是游戏的全部道具。游戏的目标是寻找其中的“SET”。相信多数读者知道“set”这个单词，它作名词时的意思是“一套、一组”，这个单词也是数学中的常用术语：“集合”。
SET游戏的目标就是寻找一组牌，一个“SET”。一个“SET”是这样规定的：它由三张牌构成，并且这三张牌的四个要素，分别考察时，要么全一样，要么全不一样。
以下是一些SET的例子：
以上三张牌的颜色相同，数量、形状、纹理全不同，所以是一个SET。
以上三张牌的颜色和数量相同，形状、纹理全不同，所以是一个SET。
以上三张牌的颜色、数量、形状、纹理全不同，所以是一个SET。
游戏的玩法是一开始随机翻出9张卡牌，任意数量的玩家可以同时参与，看谁先从这9张卡牌里找出一个SET。找出一个SET后，补三张牌。如果大家都认为找不出，那么就再加三张牌，继续进行。直到所有卡牌用完，游戏结束。谁找出的SET最多为胜。
这里有一个在线的单人版的SET游戏。游戏目标就是从12张牌里找出所有的SET，是非常简单和休闲的小游戏。
SET游戏是1974年由一名生物学基因工程研究者Marsha Falco发明的，你不难发现这个游戏与基因工程的联系。
SET游戏的规则介绍完了，那么要说说这个游戏中的数学问题了。之前我说过，当桌面有9张牌的时候，其中不一定能找到一个SET。
那问题来了，最多有多少张牌，使得这些牌之中没有SET？或者说，至少要多少牌，其中一定要有SET？
可以想象，当牌多到一定数量后，其中肯定会有SET了，那么一定有个最大牌数，其中没有SET；或者说有个最小牌数，其中一定有SET，这两个数值之间相差1。数学中，我们一般考虑前一个数值，即最大的，没有SET的牌数。
相信你现在想回看卡牌列表，找找看最大值。但是可以告诉大家，这个问题仅凭肉眼观察，要找出确切的最大值是相当困难的。
稍微尝试一下，你会发现，这个问题的难点在于，从这组卡牌中任意选取两张，这两张牌都可以处于同一个SET中，没有任何两张卡牌不可以组成SET，且这两张卡牌仅可以与另外一张卡牌构成SET。
当手动求解时，你每增加一张卡牌，你就需要考虑这张卡牌与之前所有卡牌进行一一组合，然后从剩下卡牌中把可能构成SET的卡牌排除掉，然后再加入一张，这个步骤本身相当繁琐。
问题是，当你如此完成所有操作时，你无法确认所得到的，是数量最多的不含有SET的一组卡牌，这就是问题的困难之处。
这里剧透该问题的答案是20。之前81张卡牌图片中，有20张卡牌的背景是黄色的。这20张卡牌中，就是没有任何SET的。
历史上这个结果最早在1971年，由朱塞佩·佩莱格里诺（Giuseppe Pellegrino）用数学方法论证并给出的。
有意思的是，佩莱格里诺在证明的时候就说，这个问题将来可以做成桌游。确实，三年后，SET游戏被发明出来，并在1990年正式商业化生产。
以下介绍一下数学家是怎么处理这个问题的。首先当然得进行一般化。原版的SET游戏中，你很容易看出，有这么几个参数。
第一个参数是有要素数量，原版要素里是4个要素；第二个参数是每个要素有几种取值，原版游戏中的取值是3。另外一个参数是，多少张牌构成一个SET，原版游戏是3。但这个参数是有点依赖于第二个参数。这个参数小于等于单个参数的取值数量时，才可能满足某个参数全不同这个条件。否则的话，你多少得修改游戏规则。
在本文的讨论中，就把第二个参数，即参数的取值范围，固定为3。并且把一个SET的卡牌数也固定为3，只考虑要素数量不同时，不含有SET的最大卡牌数。 这类问题，在数学中被称为Cap set / 帽集问题，而Cap Set是仿射几何(Affine Geometry)中的概念。这个问题又是怎么与仿射几何联系上的呢？
ChatGTP生成的仿射几何介绍：
仿射几何是数学中的一个领域，它研究的是在不考虑度量结构（如长度和角度）的情况下，通过平移和线性变换所保持的几何性质。简而言之，仿射几何关注的是图形的基本形状和相对位置，而不是它们的实际大小或角度。
在仿射几何中，重要的概念包括仿射空间、仿射变换、仿射子空间（如直线和平面），以及点、直线和平面之间的相互关系。仿射变换包括平移、缩放、旋转和倾斜等操作，但所有这些操作都不会改变图形的平行性。换句话说，仿射变换可以改变一个图形的大小和形状，但不能改变直线的平行关系。
（上图：在仿射几何中，人们使用Playfair's axiom来找到通过C1且平行于B1B2的直线，以及找到通过B2且平行于B1C1的直线：它们的交点C2就是所指示平移的结果。图片来自维基百科）
举个简单的例子，考虑一个平面上的正方形。通过应用仿射变换，这个正方形可以变形成为一个任意的平行四边形，但其四边仍然是两两平行的。这种变换改变了正方形的大小和角度，但保持了边的平行性，这正是仿射几何研究的内容。
仿射几何在计算机图形学、机器视觉、图像处理和各种工程应用中都有广泛的应用。例如，在计算机图形学中，通过使用仿射变换，可以轻松地对图像进行旋转、缩放和移动等操作，而在机器视觉中，它有助于从不同角度和距离观察到的物体中提取出相同的特征。
第一个要点，我们要把SET游戏中的每一张卡牌看成一个点或者一个向量。向量在物理当中，是有方向的量。在数学中，向量的概念被大大抽象和简化了。向量的定义就是一组有序的数组，这个数组中的数字个数，就是向量的维度数。比如对于(1,2)，就可以认为是一个从原点出发，指向坐标(1,2)位置向量。所以，我们有时也会说复数等价于二维向量。
那么再看看SET游戏。可以发现，SET游戏中的每一张卡牌对应了一个4维的向量。因为我们可以把每一张卡牌的四个要素规定一个顺序，比如：数量、形状、颜色、纹理。然后对每个属性的取值用1到3表示，或者用程序员更习惯的0到2来表示，那么四个数字就对应一张卡牌。
比如，(0,0,0,0),(0,1,1,2),(2,2,2,2)等等，这些有序的数字与SET游戏中的卡牌构成了一一对应。所以，SET里的每一张卡牌是一个4维的向量。
现在，定义一个有限域，域中的加法和乘法就是我们熟悉的整数加法和乘法，再模3。比如，。
那么SET的卡牌就构成了，其中每个元素都是一个四维向量，每个维度的分量都是的元素。
经过以上定义后，我们得到一个非常愉快的性质，的三个元素,,构成SET，当且仅当：
。
比如，规定四种属性顺序为：数量、颜色，形状、纹理，且：数量1用1表示，数量2用2表示，数量3用0表示；红色用1表示；椭圆为0，菱形为1，弯曲S形为3；空心纹理为0，实心纹理为1，横线纹理为2；则以下三张牌所对应的向量是
(0,1,0,1),(1,1,1,2)和(2,1,2,0)。
这三个向量相加（回忆一下，向量加法为对应分量相加）为：
（我们的加法是有模3的）
读者可以自行验证，所有构成SET的三张牌对应向量之和都是0，反之则不为0。
而在仿射空间中，3个点,,共线的条件是恰好就是3个点之和为0：
而当三点不共线时，即时，称三个点构成Cap Set。其原因可能是因为“Cap”一词在英语中有“覆盖”的意思，而不共线点，总能围成一定的面积，能“覆盖”一些区域，而共线的点就肯定不像Cap了。
那么之前SET游戏的问题，在仿射几何里的描述就是：
在4维仿射空间中，最多有几个点，其中没有任何三点共线？
以下我们开始降维打击，按维数从低到高的顺序，依次考察以上问题的结论。
先看一维，此时卡牌只有一个属性，一共3张牌。那显然，最多只能有两张牌不含有SET，有三张牌的话，必然构成一个SET。
二维情况，每张卡牌两个属性，一种9张牌。那么我们可以把这9张牌排成一个的九宫格的形式。问题就变为，从这个9个点中，最多可以选多少个点，使得其中没有任何三点共线。
（上图：二维的Cap Set问题。9个点共有12条三点共线，且每个点位于4条线上）
但如前所述，这里的三点共线的定义与我们熟悉的定义略有区别。除了我们熟悉的三横三纵、两条对角线意外，它还包含一些其他的三点共线情况。这9个点中，一共有12种三点共线的情况，上图图列出了这全部12条线，每条线恰好通过三个点。
根据这张图，你目测就能看出最多取4个点，其中没有三点共线。上图中的4个黄点就是一种取法。当取5个点时，必然出现三点共线。这个结论是对的，但并不是一个数学证明。
2维的Cap Set问题的简要证明：（参考：https://www.ams.org/publicoutreach/feature-column/fc-2015-08）
用反证法。假设中有某个5个点构成的Cap Set，记作C。
考虑中的三条“横线”，，，C必与其中的两条横线交于2点，不妨设为，，并与另一条横线交于1点，把这点记作p。
从上图中可以看到，每个点处于4条线上。经过p点的4条线中，仅有C的一个点，则C上的另外4个点必处于经过p点的其他3条线上。
则根据鸽巢原理，这3条线中，必有某条线，比如L，含有C的两个点。而L也包含P，所以P和这两个点共线。
这与C是Cap Set矛盾，所以命题得证。
3维的SET游戏中，有27个点了。
问题变为以上27个点中，最多取多少个点，可以不发生3点共线。最终答案是9。同样可以用反证法证明这一点，证明有点繁琐，各位可以自行尝试一下。
继续推进到4维，就是标准的SET游戏。答案之前说了，是20。这是在1971年，有朱塞佩·佩莱格里诺首先证明的，方法已经相当复杂了。从编程验证的角度，也可以说明4维SET的问题是很难的。
在1990年代，科学家高德纳（Donald Knuth，1938 -- ）曾经编程验证过4维的SET游戏。高德纳发现，在所有81张卡牌取20张的各种组合中，如果合并那种同构的组合，其中只有1中组合是不含有SET的，所占比例少至数量级。
下表列出了高德纳的计算结果。从81张牌中取n张牌，为不出现SET的组合数量，为在仿射变换群同构下，不出现SET的组合数量，为占所有组合的比例。
这也是为什么我们随机从SET游戏中挑20张牌，让它不含有SET是几乎做不到的。
5维的情况，通过计算机验证，现在知道答案是40。2008年，有人利用了5维的结论，证明6维情况下，Cap Set最大是112。这也是目前能够确切知道结果的最高维度。
更高维度下，虽然不知道确切答案，数学家还是想知道上下界和渐进趋势。一个简单的下界是。即在n维情况下，把每个属性的某一种取值都不选，就当它每种属性只有2种取值，那么其中是肯定不含SET的。
所以Cap Set的大小是介于到之间。1984年，有人证明了，Cap Set的大小是比低阶的无穷大，也就是维数越来越多之后，Cap Set的大小占全体的比值是趋向于0的。并且猜想，Cap Set的大小应该是与同阶，这个c介于2到3之间的某个常数，这个猜想就被称为“Cap Set猜想”。
这个猜想在20多年间，是加性组合数学和拉姆齐理论中的一个重要猜想。陶哲轩在2007年的一篇博客中，也说这个猜想是他“最喜欢的一个开放问题”。
(上图: 陶哲轩2007年的博客截图，他说Cap Set问题是他的一个"favorite open problem")
Cap Set猜想最终在2016年被三名研究者证明。他们确认，n维的Cap Set的大小与同阶，其中c是介于2到3之间的一个数值。
具体到已知的最好下界和上界，处于2.2202到2.756之间。值得一提的是这个下界，是去年由DeepMind公司推出的AI——funSearch发现的。
（上图：openAI公司官网上关于Funsearch的介绍，其中提到了cap set problem是它们主要用来测试的一个数学问题）
FunSearch的原理其实也很简单。众所周知，AI不擅长做数学题，但是非常擅长编程。所以对Cap SET问题，我们就不让AI直接回答问题，而是不断地让AI去写程序，去构造最大的Cap Set。
并且通过某种反馈机制告诉AI，这个算法好不好，再让AI改进程序，继续反馈。经过这样多次演化，最终FunSearch找出了一个突破以往下界的Cap Set。FunSearch其实是function search一词的简写。
关于Cap Set问题我就给大家介绍到这里。我比较惊讶于这个看似简单的排列组合问题，蕴含非常深的数学知识。Cap Set问题在很多地方有应用，也还有很多未解决的问题等待解决。
最后，给大家留一道思考题，也是一款桌游中的数学问题，它与Cap Set问题有异曲同工之妙。这款桌游叫嗒宝·宝可梦。
嗒宝·宝可梦是基于宝可梦IP的一款桌游。规则非常简单，其中有一些卡牌，每张卡牌上有8个不同的精灵。并且每两张卡牌之间，恰好有一个相同的精灵。游戏玩法就是，每次翻出两张卡牌，看谁先喊出两张卡牌上都有的那个宠物小精灵的名称，谁就赢得这两张卡牌，最后看谁赢的牌多，就是这么简单。
我的问题是：根据以上规则，这款游戏中最多可以有多少张卡牌？每个精灵出现了几次？可以想象，卡牌数量没法任意增加，否则到后来总有两张卡牌之间没有相同的小精灵或者有两个以上重复的小精灵，那么必然存在卡牌数量上限。
可以剧透一下，这款游戏实际上并没有用到理论上最多的卡牌数。所以你可以去搜索这款游戏到底有多少张牌，那么问题的答案会大于这款游戏的实际卡牌数。
在另外，如果每张卡牌上的小精灵数量不是8会怎样？如果是7或9，是否能设计出同样的游戏，卡牌数又该是多少？
参考文献：
https://en.wikipedia.org/wiki/Cap_set
https://www.ams.org/publicoutreach/feature-column/fc-2015-08
https://www.ams.org/publicoutreach/feature-column/fc-2016-08
https://oeis.org/A090245
https://web.archive.org/web/20130605073741/http://www.math.rutgers.edu/~maclagan/papers/set.pdf
https://en.wikipedia.org/wiki/Affine_space
