这个游戏背后的数学/计算原理是什么？
我的孩子们有一个有趣的游戏，叫做发现它！ 游戏限制（我能描述的最好的） ）是：
- 这是一副 55 张卡片
- 每张卡片上有 8 张独特的图片（即一张卡片上不能有 2 张相同的图片）
- 给定从这副卡片中选择任意 2 张卡片，有 1 且只有 1 张匹配图片。
- 不同卡片上的匹配图片可能会有不同的缩放比例，但这只是让游戏变得更困难（即小树仍然匹配较大的树）
游戏的原则是：翻转 2 张卡片，谁先选择匹配图片，谁就得分。
这里有一张图片用于澄清：
（示例：您可以从上面的底部 2 张卡片中看到匹配的图片是绿色恐龙。在右下角和右中角的图片之间，它是一个小丑的头。）
我试图理解以下内容：
满足这些标准所需的不同图片的最少数量是多少，您会如何做确定这个？
使用伪代码（或 Ruby），如何从 N 张图片数组（其中 N 是问题 1 中的最小数字）生成 55 张游戏卡？
更新：
每副牌中的图片确实出现两次以上（与一些人的猜测相反）。请参阅这张 3 张卡片的图片，每张卡片上都有一个闪电：
My kids have this fun game called Spot It! The game constraints (as best I can describe) are:
- It is a deck of 55 cards
- On each card are 8 unique pictures (i.e. a card can't have 2 of the same picture)
- Given any 2 cards chosen from the deck, there is 1 and only 1 matching picture.
- Matching pictures may be scaled differently on different cards but that is only to make the game harder (i.e. a small tree still matches a larger tree)
The principle of the game is: flip over 2 cards and whoever first picks the matching picture gets a point.
Here's a picture for clarification:
(Example: you can see from the bottom 2 cards above that the matching picture is the green dinosaur. Between the bottom-right and middle-right picture, it's a clown's head.)
I'm trying to understand the following:
What are the minimum number of different pictures required to meet these criteria and how would you determine this?
Using pseudocode (or Ruby), how would you generate 55 game cards from an array of N pictures (where N is the minimum number from question 1)?
Update:
Pictures do occur more than twice per deck (contrary to what some have surmised). See this picture of 3 cards, each with a lightning bolt:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
有限射影几何
公理 投影（平面）几何与欧几里得几何：
现在，将 "finite" 添加到汤中，你就会有这样的问题：
我们可以有只有 2 个点的几何图形？有3分？与 4？与7？
关于这个问题仍然存在悬而未决的问题，但我们确实知道这一点：
如果存在带有
Q点的几何图形，则Q = n^2 + n + 1并且n称为几何的阶。每行有
n+1个点。从每个点，精确传递
n+1行。总行数也是
Q。最后，如果
n是素数或素数幂，则确实存在n阶几何。有人可能会问，这与谜题有什么关系。
用
card代替point，用picture代替line，公理就变成：现在，我们以
n=7为例，得到7 阶有限几何，其中Q = 7^2 + 7 + 1。这就形成了Q=57线（图片）和Q=57点（卡片）。我猜谜题制作者认为 55 比 57 更整数，因此留下了 2 张卡片。我们还得到
n+1 = 8，因此从每个点（卡片）开始，经过8条线（出现8张图片），每条线（图片）有8个点（出现在8张卡片中）。这是最著名的 7 点有限射影（2 阶）平面（几何）的表示，称为 法诺平面，复制自Noelle Evans - 有限几何问题页面
我在想创建一个图像来解释如何使用 7 张卡片和 7 张图片制作上述 2 阶平面的类似拼图，但来自 math.exchange 孪生问题的链接恰好具有这样的图表： Dobble-et-la-geometrie-finie
Finite Projective Geometries
The axioms of projective (plane) geometry are slightly different than the Euclidean geometry:
Now, add "finite" into the soup and you have the question:
Can we have a geometry with just 2 points? With 3 points? With 4? With 7?
There are still open questions regarding this problem but we do know this:
If there are geometries with
Qpoints, thenQ = n^2 + n + 1andnis called theorderof the geometry.There are
n+1points in every line.From every point, pass exactly
n+1lines.Total number of lines is also
Q.And finally, if
nis prime or a prime power, then there does exists a geometry of ordern.What does that have to do with the puzzle, one may ask.
Put
cardinstead ofpointandpictureinstead oflineand the axioms become:Now, lets take
n=7and we have theorder-7finite geometry withQ = 7^2 + 7 + 1. That makesQ=57lines (pictures) andQ=57points (cards). I guess the puzzle makers decided that 55 is more round number than 57 and left 2 cards out.We also get
n+1 = 8, so from every point (card), 8 lines pass (8 pictures appear) and every line (picture) has 8 points (appears in 8 cards).Here's a representation of the most famous finite projective (order-2) plane (geometry) with 7 points, known as Fano Plane, copied from Noelle Evans - Finite Geometry Problem Page
I was thinking of creating an image that explain how the above order-2 plane could be made a similar puzzle with 7 cards and 7 pictures, but then a link from the math.exchange twin question has exactly such a diagram: Dobble-et-la-geometrie-finie
对于那些难以想象 57 个点的射影平面几何的人来说，有一种非常好的、直观的方法来用 57 张卡片和 57 个符号构建游戏（基于 尤瓦尔·电影公司 这个问题）：
在该示例中，我取了一条斜率为零的线（红色）和一条斜率为 1 的线（绿色）。它们正好相交于一个公共点（猫头鹰）。
此方法可确保任何两张牌恰好有一个公共符号，因为
这样，我们就可以构建 7x7 的卡片（7 个偏移量和 7 个斜率）。
我们还可以通过网格的垂直线构造七张额外的卡片（即取每一列）。对于这些，使用无限斜率图标。
由于每张卡片由网格中的 7 个符号和一个“斜率”符号组成，因此我们可以创建一张额外的卡片，它仅由所有 8 个斜率符号组成。
这给我们留下了 7x8 + 1 = 57 张可能的牌，以及 7 x 7 + 8 = 57 个所需的符号。
（当然，这仅适用于素数大小的网格（例如 n=7）。否则，如果斜率是网格大小的约数，则不同斜率的线可能有零个或多个交点。）
For those who have trouble picturing the projective plane geometry with 57 points, there is a really nice, intuitive way to construct the game with 57 cards and 57 symbols (based on the answer by Yuval Filmus for this question):
In the example, I take one line with slope zero (red), and one with slope 1 (green). They intersect at exactly one common point (the owl).
This method ensures that any two cards have exactly one common symbol, because
In this way, we can construct 7x7 cards (7 offsets and 7 slopes).
We can also construct seven additional cards from vertical lines through the grid (i.e. taking each column). For those, the infinity slope icon is used.
Because each card consists of seven symbols from the grid and exactly one "slope" symbol, we can create one additional card, which simply consists of all the 8 slope symbols.
This leaves us with 7x8 + 1 = 57 possible cards, and 7 x 7 + 8 = 57 required symbols.
(Naturally, this only works with a prime-number-sized grid (e.g. n=7). Otherwise, lines of different slope could have zero or more than one intersection if the slope is a divisor of the grid size.)
因此，共有 k=55 张卡片，每张卡片包含 n 张图片池中的 m=8 张图片。
我们可以重申这个问题：“我们需要多少张图片n，以便我们可以构造一组k张卡片，并且任意一对卡片之间只有一张共享图片？”等效地通过询问：
正好有（n 个选择 m）个可能的向量来构建对。所以我们至少需要一个足够大的n，以便（n选择m）>=k。这只是一个下限，因此为了满足成对兼容性约束，我们可能需要更高的n。
只是为了进行一些实验，我编写了一个小型 Haskell 程序来计算有效的卡组：
编辑： 在看到 Neil 和 Gajet 的解决方案后我才意识到，我使用的算法并不总能找到最佳解决方案，所以下面的所有内容不一定有效。我会尽快尝试更新我的代码。
对于前几个 n 种外观，每张卡 m=8 张图片的兼容卡的最大数量可供选择 n 幅不同的图片像这样：
由于组合爆炸，这种暴力方法并没有走得太远。但我认为这可能仍然很有趣。
有趣的是，似乎对于给定的 m，k 随 n 增加，仅达到某个 n，之后它保持不变。
这意味着，对于每张卡上的每个图片数量，都有一定数量的图片可供选择，这会导致合法卡的最大可能数量。添加更多图片以从过去的最佳数量中进行选择不会进一步增加合法卡的数量。
前几个最佳 k 为：
So there are k=55 cards containing m=8 pictures each from a pool of n pictures total.
We can restate the question 'How many pictures n do we need, so that we can construct a set of k cards with only one shared picture between any pair of cards?' equivalently by asking:
There are exactly (n choose m) possible vectors to build pairs from. So we at least need a big enough n so that (n choose m) >= k. This is just a lower bound, so for fulfilling the pairwise compatibility constraint we possibly need a much higher n.
Just for experimenting a bit i wrote a small Haskell program to calculate valid card sets:
Edit: I just realized after seeing Neil's and Gajet's solution, that the algorithm i use doesn't always find the best possible solution, so everything below isn't necessarily valid. I'll try to update my code soon.
The resulting maximum number of compatible cards for m=8 pictures per card for different number of pictures to choose from n for the first few n looks like this:
This brute force method doesn't get very far though because of combinatorial explosion. But i thought it might still be interesting.
Interestingly, it seems that for given m, k increases with n only up to a certain n, after which it stays constant.
This means, that for every number of pictures per card there is a certain number of pictures to choose from, that results in maximum possible number of legal cards. Adding more pictures to choose from past that optimal number doesn't increase the number of legal cards any further.
The first few optimal k's are:
其他人描述了设计的一般框架（有限射影平面），并展示了如何生成素数阶的有限射影平面。我只是想填补一些空白。
可以为许多不同的阶生成有限射影平面，但在素数阶
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=p^k（素数幂）时，存在q阶有限域。该域称为GF(p^k)，代表“伽罗瓦域”。在主要功率情况下，这些场并不像在主要情况下那样容易构造。幸运的是，这项艰苦的工作已经在免费软件中完成并实现了，即 Sage Math。例如，要获得 4 阶射影平面设计，只需键入
，您将获得看起来像
我将上面解释如下的输出：有 21 张图片，标记为从 0 到 20。每个块（射影几何中的线） ）告诉我哪些图片出现在卡片上。例如，第一张卡片将有图片 0、1、2、3 和 20；第二张卡片上有图片 0、4、8、12 和 16；等等。
7 阶系统可以生成输出，
如果
您想要最多 57 张卡，您可以使用 GF(7)。如果您想要 58 张卡片，则必须使用更大的区域。由于 8 是素数的幂，因此您可以使用
GF(8)。请注意，基于GF(8)的投影平面将具有8^2 + 8 + 1 =73 个点和 73 条线。您可以制作 73 张卡片，但如果您想要一组正好 58 张卡片，则只需扔掉其中的 15 张即可。如果您想要 73 到 91 张卡，您可以使用GF(9)等。没有GF(10)因为 10 不是质数的幂。接下来是GF(11)，然后是GF(13)，然后是GF(16)，因为16=2^4代码>，等等。顺便说一句，我有一个理论，即最初的 Spot It 牌组使用 55，而不是 57，因为他们与一家扑克牌制造商签订了合同，该制造商已经为 55 张牌的牌组（一副牌中 52 张普通牌，加上两张王牌和一张标题牌）签订了合同。卡片）。
Others have described the general framework for the design (finite projective plane) and shown how to generate finite projective planes of prime order. I would just like to fill in some gaps.
Finite projective planes can be generated for many different orders, but they are most straightforward in the case of prime order
p. Then the integers modulopform a finite field which can be used to describe coordinates for the points and lines in the plane. There are 3 different kinds of coordinates for points:(1,x,y),(0,1,x), and(0,0,1), wherexandycan take on values from0top-1. The 3 different kinds of points explains the formulap^2+p+1for the number of points in the system. We can also describe lines with the same 3 different kinds of coordinates:[1,x,y],[0,1,x], and[0,0,1].We compute whether a point and line are incident by whether the dot product of their coordinates is equal to 0 mod
p. So for example the point(1,2,5)and the line[0,1,1]are incident whenp=7since1*0+2*1+5*1 = 7 == 0 mod 7, but the point(1,3,3)and the line[1,2,6]are not incident since1*1+3*2+3*6 = 25 != 0 mod 7.Translating into the language of cards and pictures, that means the picture with coordinates
(1,2,5)is contained in the card with coordinates[0,1,1], but the picture with coordinates(1,3,3)is not contained in the card with coordinates[1,2,6]. We can use this procedure to develop a complete list of cards and the pictures that they contain.I think it's easier to think of pictures as points and cards as lines, but there's a duality in projective geometry between points and lines so it really doesn't matter. However, in what follows I will be using points for pictures and lines for cards.
The same construction works for any finite field. We know that there is a finite field of order
qif and only ifq=p^k, a prime power. The field is calledGF(p^k)which stands for "Galois field". The fields are not as easy to construct in the prime power case as they are in the prime case.Fortunately, the hard work has already been done and implemented in free software, namely Sage Math. To get a projective plane design of order 4, for example, just type
and you'll obtain output that looks like
I interpret the above as follows: there are 21 pictures labelled from 0 to 20. Each of the blocks (lines in projective geometry) tells me which pictures appears on a card. For example, the first card will have pictures 0, 1, 2, 3, and 20; the second card will have pictures 0, 4, 8, 12, and 16; and so on.
The system of order 7 can be generated by
which generates the output
If you want up to 57 cards you can use GF(7). If you want 58 cards you'll have to use a larger field. Since 8 is a power of a prime, you could use
GF(8). Note that the projective plane based onGF(8)will have8^2 + 8 + 1 =73 points and 73 lines. You can make 73 cards, but then just throw away 15 of them if you want a set of exactly 58 cards. If you want between 73 and 91 cards you could useGF(9), etc. There is noGF(10)because 10 is not a power of a prime.GF(11)is next, thenGF(13), thenGF(16)because16=2^4, and so on.By the way, I have a theory that the original Spot It deck uses 55, not 57, because they contracted a playing card manufacturer which was already tooled for decks of 55 cards (52 regular cards in a deck, plus two jokers and a title card).
这是 Gajet 在 Python 中的解决方案，因为我发现 Python 更具可读性。我对其进行了修改，使其也适用于非素数。我使用 Thies Insight 生成了一些更容易理解的显示代码。
带输出：
Here's Gajet's solution in Python, since I find Python more readable. I have modified it so that it works with non-prime numbers as well. I have used Thies insight to generate some more easily understood display code.
With output:
我刚刚找到了一种方法，可以用 57 或 58 张图片来实现，但现在我头疼得厉害，我会在睡好后 8-10 小时内发布 ruby 代码！只是一个提示，我的解决方案每 7 张卡片共享相同的标记，并且使用我的解决方案可以构建总共 56 张卡片。
这是生成 ypercube 所说的所有 57 张卡片的代码。它使用了 57 张图片，抱歉，我已经编写了实际的 C++ 代码，但知道
vector是一个包含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）等等...再次对延迟的代码表示歉意。
I just found a way to do it with 57 or 58 pictures but now I have a very bad headache, I'll post the ruby code in 8-10 hours after I slept well! just a hint my my solution every 7 cards share same mark and total 56 cards can be constructed using my solution.
here is the code that generates all 57 cards that ypercube was talking about. it uses exactly 57 pictures, and sorry guy's I've written actual C++ code but knowing that
vector <something>is an array containing values of typesomethingit's easy to understand what this code does. and this code generatesP^2+P+1cards usingP^2+P+1pictures each containingP+1picture and sharing only 1 picture in common, for every prime P value. which means we can have 7 cards using 7 pictures each having 3 pictures(for p=2), 13 cards using 13 pictures(for p=3), 31 cards using 31 pictures(for p=5), 57 cards for 57 pictures(for p=7) and so on...again sorry for the delayed code.
使用
z3定理证明者令
P为每张卡片的符号数量。根据这篇文章和ypercubeᵀᴹ的答案有N = P**2 - P + 1分别是卡片和符号。一副纸牌可以用其关联矩阵来表示，该矩阵具有每张纸牌的行和每个可能的符号的列。如果卡片i上有符号j，则其(i,j)元素为1。我们只需要记住这些约束来填充这个矩阵：PP这意味着
N**2变量和N**2 + 2*N + (N select 2)约束。对于小输入，使用z3似乎可以在不长的时间内进行管理。编辑：不幸的是，P=8 对于这种方法来说似乎太大了。我在 14 小时的计算时间后终止了该进程。
结果
Using the
z3theorem proverLet
Pbe the number of symbols per card. According to this article andypercubeᵀᴹ's answer there areN = P**2 - P + 1cards and symbols, respectively. A deck of cards can be represented with its incidence matrix which has a row for each card and a column for each possible symbol. Its(i,j)element is1if cardihas symboljon it. We only need to fill this matrix with these constraints in mind:PPThat means
N**2variables andN**2 + 2*N + (N choose 2)constraints. It seems to be manageable in a not-so-long time withz3for small inputs.edit: Unfortunately P=8 seems to be too big for this method. I killed the process after 14 hour of computation time.
Results
我非常喜欢这个线程。我用这里的部分代码构建了这个 github python 项目，以将自定义卡片绘制为 png（这样就可以在互联网上订购自定义卡片游戏）。
https://github.com/plagtag/ProjectiveGeometry-Game
I very much like this thread. I build this github python project with parts of this code here to draw custom cards as png (so one can order custom card games in the internet).
https://github.com/plagtag/ProjectiveGeometry-Game
我写了一篇文章关于如何生成这种牌组，并附有代码在 Perl 中。该代码尚未优化，但它至少能够生成“合理”订单的牌组......等等。
这是一个阶数为 8 的示例，它必须考虑稍微复杂的基础数学，因为 8 不是素数，尽管它是生成此类牌组的有效阶数。请参阅上面或文章以获取更详细的说明，如果您只想生成稍微困难一点的 Spot-It，请参阅下面的文章 :-)
从
0到72的每个标识符都可以既可读取为卡片标识符，也可读取为图片标识符。例如，最后一行表示：72包含图片2、13、22、... 、59、68和72出现在卡片2、13中，22、...、59和68。I wrote an article about how to generate this kind of decks, with code in Perl. The code is not optimized but it's at least capable of generating decks of "reasonable" orders... and some more.
Here's an example with order 8, which has to consider a slightly more complicated underlying math, because 8 is not prime although a valid order for generating these kind of decks. See above or the article for a more detailed explanation, below if you just want to generate a slightly more difficult Spot-It :-)
Each identifier from
0to72can be read both as a card identifier and as a picture identifier. For example, the last row means that:72contains pictures2,13,22, ...,59,68, AND72appears in cards2,13,22, ...,59, and68.我编写了以下代码来计算卡片。这个想法是创建第一张带有 n 个图像的卡片。 来增加每个索引，从而轻松生成其余的卡片：
如果每对图像索引的差异是唯一的，则可以通过使用相同的值模 m = n * n - n + 1输出
I wrote the following code to calculate the cards. The idea is to create the first card with n images on it. If the difference of every pair of image indexes is unique then the rest of the cards can be generated trivially, by increasing each index with the same value modulo m = n * n - n + 1
output: