这个游戏背后的数学/计算原理是什么？

Question

我的孩子们有这款名为Spot It的有趣游戏!游戏限制(我能描述的最好)是:

• 这是一张55张牌
• 每张卡上有8张独特的图片(即一张卡不能有2张相同的图片)
• 鉴于从牌组中选择的任何2张牌,只有1张匹配图片.
• 匹配的图片可能会在不同的卡上进行不同的缩放,但这只会使游戏更难(即小树仍然匹配更大的树)

游戏的原则是:翻转2张牌,无论谁先挑选匹配的图片都能得到一分.

这是一张澄清的图片:

(例如:你可以从上面的2张卡片上看到匹配的图片是绿色恐龙.在右下角和中右图之间,它是一个小丑的头.)

我想了解以下内容:

1. 满足这些标准所需的最小不同图片数量是多少？您如何确定？

2. 使用伪代码(或Ruby),如何从N个图片阵列中生成55张游戏卡(其中N是问题1中的最小数字)？

更新:

每张照片确实发生了两次以上的照片(与一些人推测的情况相反).看到这张3张牌的照片,每张牌都有一个闪电:

Answer 1

有限射影几何

所述公理的射影(平面)的几何形状比欧几里德几何稍有不同:

• 每两个点只有一条线穿过它们(这是相同的).
• 每两行恰好在一个点上相遇(这与Euclid略有不同).

现在,在汤中加入"有限",你就有了问题:

我们可以只有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张卡片中).

这里是最着名的有限投影(阶2)平面(几何)的表示,有7个点,称为Fano平面,复制自Noelle Evans - 有限几何问题页面

我正在考虑创建一个图像,解释上面的2阶飞机如何制作一个类似的拼图,有7张卡和7张图片,但是来自math.exchange双胞胎问题的链接就是这样一张图:Dobble-et- LA-几何学,finie

Answer 2

因此,存在k = 55张卡,其中m = 8张图片,每张图片来自n张图片总数.我们可以列出这样一个问题:有多少图片ñ做我们需要的,这样我们就可以构造一个集ķ卡与任何一对牌之间只有一个共享的照片吗？" 等价地问:

给定一个n维向量空间和所有向量的集合,其中包含正好m个元素等于1和所有其他零,n有多大,这样我们就可以找到一组k向量,其成对点积是都等于1？

确切地(n选择m)可能的向量来构建对.所以我们至少需要一个足够大的n,以便(n选择m)> = k.这只是一个下限,因此为了实现成对兼容性约束,我们可能需要更高的n.

只是为了试验一点,我写了一个小的Haskell程序来计算有效的卡集:

编辑:我刚看到Neil和Gajet的解决方案后才意识到,我使用的算法并不总能找到最佳解决方案,因此下面的所有内容都不一定有效.我会尽快更新我的代码.

module Main where

cardCandidates n m = cardCandidates' [] (n-m) m
cardCandidates' buildup  0  0 = [buildup]
cardCandidates' buildup zc oc
    | zc>0 && oc>0 = zerorec ++ onerec
    | zc>0         = zerorec
    | otherwise    = onerec
    where zerorec = cardCandidates' (0:buildup) (zc-1) oc
          onerec  = cardCandidates' (1:buildup) zc (oc-1)

dot x y = sum $ zipWith (*) x y
compatible x y = dot x y == 1

compatibleCards = compatibleCards' []
compatibleCards' valid     [] = valid
compatibleCards' valid (c:cs)
  | all (compatible c) valid = compatibleCards' (c:valid) cs
  |                otherwise = compatibleCards'    valid  cs

legalCardSet n m = compatibleCards $ cardCandidates n m

main = mapM_ print [(n, length $ legalCardSet n m) | n<-[m..]]
  where m = 8

对于前几个n,从n中选择不同数量的图片,每张卡m = 8张图片的最大兼容卡数量如下所示:

由于组合爆炸,这种蛮力方法并没有走得太远.但我认为它可能仍然很有趣.

有趣的是,似乎对于给定的m,k随着n的增加而增加,直到某个n,之后它保持不变.

这意味着,对于每张卡的每个数量的图片,有一定数量的图片可供选择,这导致最大可能数量的合法卡.添加更多图片以从过去的最佳数字中进行选择不会进一步增加合法卡的数量.

前几个最佳k是:

Answer 3

对于那些难以用57点描绘投影平面几何的人来说,有一个非常好的,直观的方法来构建57张牌和57个符号的游戏(基于Yuval Filmus对这个问题的回答):

1. 对于具有8个符号的卡,创建7x7独特符号网格.
2. 为"斜率"添加额外的8个符号,从0到6,加上一个用于无限斜率.
3. 每张卡都是网格上的一条线(7个符号)加上一条符号,该符号来自为线的斜率设置的斜率.线条有一个偏移(即左边的起点)和一个斜率(即每个步骤右边有多少个符号).当线条离开顶部的网格时,重新进入底部.有两张这样的卡,请参见此示例图(来自boardgamegeek的图片):

在这个例子中,我采用斜率为零(红色)的一条线和一条斜率为1的线(绿色).它们恰好在一个共同点(猫头鹰)相交.

此方法可确保任意两张卡只有一个共同的符号,因为

1. 如果斜率不同,那么线总是在一个点上相交.
2. 如果斜率相同,则线不会相交,并且网格中没有共同的符号.在这种情况下,斜率符号将是相同的.

通过这种方式,我们可以构建7x7卡(7个偏移和7个斜率).

我们还可以通过网格从垂直线构建另外七张牌(即每列).对于那些,使用无限斜率图标.

因为每张卡由来自网格的七个符号和正好一个"斜率"符号组成,我们可以创建一个附加卡,它只包含所有8个斜率符号.

这给我们留下了7x8 + 1 = 57张可能的卡片,以及7 x 7 + 8 = 57个必需的符号.

(当然,这仅适用于素数大小的网格(例如,n = 7).否则,如果斜率是网格大小的除数,则不同斜率的线可以具有零或多于一个交点.)

Answer 4

其他人描述了设计的一般框架(有限投影平面),并展示了如何生成素数阶的有限投影平面.我想填补一些空白.

可以为许多不同的阶数生成有限投影平面,但在素数阶的情况下它们是最直接的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字段".这些领域在主要权力案例中并不像在黄金案例中那样容易构建.

幸运的是,辛勤工作已经在自由软件中完成并实施,即Sage.例如,要获得4阶投影平面设计,只需键入

print designs.ProjectiveGeometryDesign(2,1,GF(4,'z'))

你将获得看起来像的输出

ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20], blocks=[[0, 1, 2, 3, 20], [0,
4, 8, 12, 16], [0, 5, 10, 15, 19], [0, 6, 11, 13, 17], [0, 7, 9, 14,
18], [1, 4, 11, 14, 19], [1, 5, 9, 13, 16], [1, 6, 8, 15, 18], [1, 7,
10, 12, 17], [2, 4, 9, 15, 17], [2, 5, 11, 12, 18], [2, 6, 10, 14, 16],
[2, 7, 8, 13, 19], [3, 4, 10, 13, 18], [3, 5, 8, 14, 17], [3, 6, 9, 12,
19], [3, 7, 11, 15, 16], [4, 5, 6, 7, 20], [8, 9, 10, 11, 20], [12, 13,
14, 15, 20], [16, 17, 18, 19, 20]]>

我解释如下:有21张图片标记为0到20.每个块(投影几何线)告诉我哪些图片出现在卡片上.例如,第一张卡片将包含图片0,1,2,3和20; 第二张卡片上有0,4,8,12和16张图片; 等等.

可以通过生成订单7的系统

print designs.ProjectiveGeometryDesign(2,1,GF(7)) 

它产生输出

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

Answer 5

我刚刚找到了用57或58张照片做到这一点的方法,但现在我头疼得厉害,我会在睡觉后8到10小时内发布红宝石代码!只是暗示我的解决方案每7张卡共享相同的标记,并且可以使用我的解决方案构建总共56张卡.

这是生成ypercube正在讨论的所有57张卡片的代码.它使用了57张图片,对不起,我已经编写了实际的C++代码,但知道这vector <something>是一个包含类型值的数组,something很容易理解这段代码的作用.并且该代码P^2+P+1使用P^2+P+1每个包含P+1图片的图片生成卡片,并且对于每个主要P值,共享仅1个共同的图片.这意味着我们可以使用7张照片,每张照片有7张照片(p = 2),13张照片使用13张照片(p = 3张),31张照片使用31张照片(p = 5张),57张照片用于57张照片(对于p = 7)等等......

#include <iostream>
#include <vector>

using namespace std;

vector <vector<int> > cards;

void createcards(int p)
{
    cards.resize(0);
    for (int i=0;i<p;i++)
    {
        cards.resize(cards.size()+1);
        for(int j=0;j<p;j++)
        {
            cards.back().push_back(i*p+j);
        }
        cards.back().push_back(p*p+1);
    }

    for (int i=0;i<p;i++)
    {
        for(int j=0;j<p;j++)
        {
            cards.resize(cards.size()+1);
            for(int k=0;k<p;k++)
            {
                cards.back().push_back(k*p+(j+i*k)%p);
            }
            cards.back().push_back(p*p+2+i);
        }
    }

    cards.resize(cards.size()+1);

    for (int i=0;i<p+1;i++)
        cards.back().push_back(p*p+1+i);
}

void checkCards()
{
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=0;j<cards[i].size();j++)
        {
            printf("%3d",cards[i][j]);
        }
        cout << "\n";
    }
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=i+1;j<cards.size();j++)
        {
            int sim = 0;
            for(unsigned k=0;k<cards[i].size();k++)
                for(unsigned l=0;l<cards[j].size();l++)
                    if (cards[i][k] == cards[j][l])
                        sim ++;
            if (sim != 1)
                cout << "there is a problem between cards : " << i << " " << j << "\n";

        }
    }
}

int main()
{
    int p;
    for(cin >> p; p!=0;cin>> p)
    {
        createcards(p);
        checkCards();
    }
}

再次抱歉延迟代码.

Answer 6

这是Gajet的Python解决方案,因为我发现Python更具可读性.我修改了它,以便它也适用于非素数.我使用Thies insight来生成一些更容易理解的显示代码.

from __future__ import print_function
from itertools import *

def create_cards(p):
    for min_factor in range(2, 1 + int(p ** 0.5)):
        if p % min_factor == 0:
            break
    else:
        min_factor = p
    cards = []
    for i in range(p):
        cards.append(set([i * p + j for j in range(p)] + [p * p]))
    for i in range(min_factor):
        for j in range(p):
            cards.append(set([k * p + (j + i * k) % p
                              for k in range(p)] + [p * p + 1 + i]))

    cards.append(set([p * p + i for i in range(min_factor + 1)]))
    return cards, p * p + p + 1

def display_using_stars(cards, num_pictures):
    for pictures_for_card in cards:
        print("".join('*' if picture in pictures_for_card else ' '
                      for picture in range(num_pictures)))

def check_cards(cards):
    for card, other_card in combinations(cards, 2):
        if len(card & other_card) != 1:
            print("Cards", sorted(card), "and", sorted(other_card),
                  "have intersection", sorted(card & other_card))

cards, num_pictures = create_cards(7)
display_using_stars(cards, num_pictures)
check_cards(cards)

随着输出:

***      *   
   ***   *   
      ****   
*  *  *   *  
 *  *  *  *  
  *  *  * *  
*   *   *  * 
 *   **    * 
  **   *   * 
*    * *    *
 * *    *   *
  * * *     *
         ****