我的孩子有这个有趣的游戏叫Spot It!游戏限制(我能说的最好)是:
-
这是一张55张牌
-
每张卡上有8张独特的图片(即一张卡不能有2张相同的图片)
-
Given any 2 cards chosen from the deck, there is 1 and only 1 matching picture .
-
匹配的图片在不同的卡片上可能会有不同的缩放比例,但这只会让游戏变得更难(即小树仍与较大的树匹配)
游戏的原理是:翻转2张牌,无论谁先挑选匹配的图片都能获得一分 .
这是一张澄清的图片:
(例如:你可以从上面的2张牌看到匹配的图片是绿色的恐龙 . 在右下角和右中角的图片之间,它是一个小丑的头 . )
我想了解以下内容:
-
满足这些标准所需的最小不同图片数量是多少?您如何确定?
-
使用伪代码(或Ruby),如何从N个图片阵列中生成55张游戏卡(其中N是问题1中的最小数字)?
Update:
每张照片确实发生了两次以上的照片(与一些人猜测的情况相反) . 看到这张3张牌的照片,每张牌都带有闪电:
9 回答
Finite Projective Geometries
projective (plane) geometry的projective (plane) geometry与欧氏几何略有不同:
每两个点只有一条线穿过它们(这是相同的) .
每两行恰好在一个点上相遇(这与Euclid略有不同) .
现在,将"finite"添加到汤中,您就有了问题:
我们可以只有2个点的几何?有3分? 4?有7?
关于这个问题仍然存在悬而未决的问题,但我们知道这一点:
如果存在具有
Q
点的几何,则Q = n^2 + n + 1
和n
称为几何的order
.每行都有
n+1
个点 .从每一点开始,准确传递
n+1
行 .总行数也是
Q
.最后,如果
n
是素数,那么确实存在一个阶数n
的几何 .有人可能会问,这与谜题有什么关系 .
放
card
而不是point
和picture
而不是line
,公理成为:每两张卡片只有一张共同的图片 .
对于每两张图片,只有一张卡片同时具有这两张图片 .
现在,让我们拿
n=7
,我们有order-7
有限几何与Q = 7^2 + 7 + 1
. 这使Q=57
行(图片)和Q=57
点(卡片) . 我猜拼图制造商认为55是圆形数字而不是57,剩下2张牌 .我们也得到
n+1 = 8
,所以从每个点(卡),8行通过(出现8张图片),每行(图片)有8个点(出现在8张卡片中) .这里是最着名的有限投影(order-2)平面(几何)的表示,有7个点,称为Fano Plane,复制自Noelle Evans - Finite Geometry Problem Page
我正在考虑创建一个图像,解释上面的2阶飞机如何制作一个类似的拼图,有7张卡片和7张图片,但是来自math.exchange双胞胎问题的链接就是这样一张图: Dobble-et-la-geometrie-finie
因此,存在k = 55张卡,其中m = 8张图片,每张图片来自n张图片的总数 . 我们可以重申一个问题'我们需要多少张图片,以便我们可以构建一组k卡,在任何一张卡片之间只有一张共享图片?'等价地问:
确切地(n选择m)可能的向量来构建对 . 所以我们至少需要一个足够大的n,以便(n选择m)> = k . 这只是一个下限,因此为了实现成对兼容性约束,我们可能需要更高的n .
只是为了试验一点,我写了一个小的Haskell程序来计算有效的卡集:
Edit: 我刚看到Neil 's and Gajet'解决方案后才意识到,我使用的算法并不一定有效 . 我会尽快更新我的代码 .
每张卡m = 8张图片的兼容卡的最大数量,对于前几个n,从n中选择不同数量的图片,如下所示:
由于组合爆炸,这种蛮力方法并没有走得太远 . 但我认为它可能仍然很有趣 .
有趣的是,似乎对于给定的m,k随着n的增加而增加,直到某个n,之后它保持不变 .
这意味着,对于每张卡的每个数量的图片,有一定数量的图片可供选择,这导致最大可能数量的合法卡 . 添加更多图片以从过去的最佳数字中进行选择不会进一步增加合法卡的数量 .
前几个最佳k是:
对于那些无法用57个点描绘投影平面几何体的人来说,有一个非常好的,直观的方法来构建57张牌和57个符号的游戏(根据Yuval Filmus为this question的答案):
对于具有8个符号的卡片,请创建7x7独特符号网格 .
为"slopes"添加额外的8个符号,从0到6,加上一个用于无限斜率 .
每张卡是网格上的一条线(7个符号)加上一条符号,该符号来自为该线的斜率设置的斜率 . 线具有偏移(即左边的起点)和斜率(即,每个步骤右边有多少个符号) . 当线条离开顶部的网格时,重新进入底部 . 对于两张这样的卡,请参见此示例图(来自boardgamegeek的图片):
在这个例子中,我采用斜率为零(红色)的一条线和一条斜率为1的线(绿色) . 它们恰好在一个共同点(猫头鹰)相交 .
此方法可确保任意两张卡只有一个共同的符号,因为
如果斜率不同,则线条将始终在一个点上相交 .
如果斜率相同,则线不会相交,并且网格中没有公共符号 . 在这种情况下,斜率符号将是相同的 .
通过这种方式,我们可以构建7x7卡(7个偏移和7个斜率) .
我们还可以通过网格从垂直线构建七个附加卡(即,取每列) . 对于那些,使用无限斜率图标 .
因为每张卡由网格中的七个符号和正好一个“斜率”符号组成,我们可以创建一个附加卡,它只包含所有8个斜率符号 .
这给我们留下了7x8 1 = 57张可能的牌,7 x 7 8 = 57张所需的牌 .
(当然,这仅适用于素数大小的网格(例如,n = 7) . 否则,如果斜率是网格大小的除数,则不同斜率的线可以具有零或多于一个交点 . )
我刚刚找到了用57或58张照片做的方法,但现在我头疼得厉害,我会在睡觉后8-10小时内发布红宝石代码!只是暗示我的解决方案每7张卡共享相同的标记,并且可以使用我的解决方案构建总共56张卡 .
这是生成ypercube正在讨论的所有57张卡片的代码 . 它只使用了57张图片,抱歉的是's I'已经编写了实际的C代码,但是知道
vector <something>
是一个包含something
类型值的数组,很容易理解这段代码的作用 . 此代码使用P^2+P+1
图片生成P^2+P+1
张卡片,每张图片包含P+1
图片,并且每个素数P值共享1张图片 . 这意味着我们可以拥有7张卡片,每张7张图片,每张图片有3张图片(p = 2),13张卡片使用13张图片(p = 3),31张卡片使用31张图片(p = 5),57张卡片用于57张图片(对于p = 7)等等......再次抱歉延迟代码 .
其他人已经描述了设计的一般框架(有限投影平面),并展示了如何生成素数阶的有限投影平面 . 我想填补一些空白 .
可以为许多不同的阶数生成有限投影平面,但在素数阶
p
的情况下它们是最直接的 . 然后,整数模p
形成一个有限域,可用于描述平面中点和线的坐标 . 点有3种不同的坐标:(1,x,y)
,(0,1,x)
和(0,0,1)
,其中x
和y
可以取值0
到p-1
的值 . 3种不同的点解释了系统中点数的公式p^2+p+1
. 我们还可以描述具有相同3种不同坐标的线:[1,x,y]
,[0,1,x]
和[0,0,1]
.我们通过坐标的点积是否等于0 mod
p
来计算点和线是否发生事故 . 因此,例如(1,2,5)
和[0,1,1]
行是p=7
自1*0+2*1+5*1 = 7 == 0 mod 7
以来的事件,但是点(1,3,3)
和行[1,2,6]
自1*1+3*2+3*6 = 25 != 0 mod 7
以来不是事件 .转换为卡片和图片的语言,这意味着坐标为
(1,2,5)
的卡片包含坐标为[0,1,1]
的图片,但坐标为(1,3,3)
的卡片不包含坐标为[1,2,6]
的图片 . 我们可以使用此程序开发完整的卡片列表及其中包含的图片 .顺便说一句,我认为将图片看作点和卡就像线条一样容易,但点和线之间的投影几何图形存在二元性,所以它确实无关紧要 . 但是,接下来我将使用点卡片和卡片线 .
相同的结构适用于任何有限的场 . 我们知道有一个有限的订单字段
q
当且仅当q=p^k
,一个主要力量 . 该字段名为GF(p^k)
,代表"Galois field" . 在主要情况下,这些字段并不像在素数情况下那样容易构建 .幸运的是,辛勤工作已经在自由软件中完成并实施,即Sage . 例如,要获得4阶投影平面设计,只需键入
你将获得看起来像的输出
我解释如下:有21张图片标记为0到20.每个块(投影几何线)告诉我哪些图片出现在卡片上 . 例如,第一张卡片将包含图片0,1,2,3和20;第二张卡片上有0,4,8,12和16张图片;等等 .
可以通过生成订单7的系统
它产生输出
这是Gajet在Python中的解决方案,因为我发现Python更具可读性 . 我修改了它,以便它也适用于非素数 . 我使用Thies insight来生成一些更容易理解的显示代码 .
带输出:
Using the z3 theorem prover
设
P
是每张卡的符号数 . 根据this article和ypercubeᵀᴹ
的答案,分别有N = P**2 - P + 1
卡片和符号 . 一副牌可以用其入射矩阵表示,每个卡有一行,每个可能符号有一列 . 如果卡i
上有符号j
,则(i,j)
元素为1
. 我们只需要考虑这些约束来填充这个矩阵:每个元素都是零或一个
每行的总和正是
P
每列的总和正是
P
任何两行必须只有一个共同的符号
这意味着
N**2
变量和N**2 + 2*N + (N choose 2)
约束 . 对于小输入,在不太长的时间内似乎可以管理z3
.edit :不幸的是,对于这种方法,P = 8似乎太大了 . 我在14小时的计算时间后杀了这个过程 .
Results
我非常喜欢这个帖子 . 我使用此代码的一部分构建此github python项目,以将自定义卡片绘制为png(因此可以在互联网上订购自定义卡片游戏) .
https://github.com/plagtag/ProjectiveGeometry-Game
我写了一个article关于如何使用Perl中的代码生成这种类型的套牌 . 代码没有优化,但它至少能够生成"reasonable"订单的甲板......还有更多 .
这是一个8阶的例子,它必须考虑稍微复杂的基础数学,因为8虽然是生成这种甲板的有效顺序,但不是素数 . 请参阅上文或文章以获得更详细的解释,如果您只想生成稍微困难的Spot-It :-)
0
至72
中的每个标识符都可以作为卡标识符和图片标识符读取 . 例如,最后一行表示:卡
72
包含图片2
,13
,22
,...,59
,68
,AND图片
72
出现在卡2
,13
,22
,...,59
和68
中 .