Quels sont les principes mathématiques/calcul derrière ce jeu ?

Question

Mes enfants ont ce jeu amusant appelé Spot! Le jeu de contraintes (du mieux que je peux décrire) sont:

• C'est un jeu de 55 cartes
• Sur chaque carte sont les 8 photos (c'est à dire une carte ne peut pas avoir 2 de la même image)
• Donné tous les 2 cartes choisies à partir de la terrasse, il y a 1 et 1 seule image correspondante.
• L'appariement des images peuvent être redimensionnées différemment sur différentes cartes, mais c'est seulement pour rendre le jeu plus difficile (c'est à dire un petit arbre correspond quand même à un gros arbre)

Le principe du jeu est: retourner sur les 2 cartes et quiconque première reprend l'image correspondante obtient un point.

Voici une photo de précisions:

(Exemple: vous pouvez le voir dans le bas 2 cartes ci-dessus que la mise en correspondance de l'image est le dinosaure vert. Entre le bas à droite et du milieu à droite de l'image, c'est un clown à la tête.)

Je suis en train d'essayer de comprendre les éléments suivants:

1. Quels sont le nombre minimum d'images différentes pour répondre à ces critères et comment voulez-vous déterminer ce?

2. À l'aide de pseudo-code (ou Ruby), comment voulez-vous générer de 55 cartes de jeu à partir d'un tableau de N images (où N est le nombre minimum de la question 1)?

Mise à jour:

Les images ne se produisent plus de deux fois par deck (contrairement à ce que certains ont supposé). Voir cette photo de 3 cartes, chacune avec un éclair:

Answer 1

Finis Les Géométries Projectives

Les axiomes de projectives (plan) de la géométrie sont légèrement différents de ceux de la géométrie Euclidienne:

• Tous les deux points ont exactement une ligne qui passe à travers eux (c'est la même chose).
• Tous les deux lignes se rencontrent en exactement un point (c'est un peu différent de d'Euclide).

Maintenant, ajoutez "fini" dans la soupe et vous avez la question:

Peut-on avoir une géométrie avec seulement 2 points? Avec les 3 points? Avec 4? Avec 7?

Il y a encore des questions ouvertes au sujet de ce problème, mais nous savons que:

• Si il y a des géométries avec Q , Q = n^2 + n + 1 et n est appelé l' order de la géométrie.
• Il y a n+1 des points dans chaque ligne.
• À partir de chaque point, passer exactement n+1 des lignes.

• Nombre Total de lignes est également Q.

• Et enfin, si n est premier, alors il existe une géométrie de la commande n.

---

Quel est le rapport avec le puzzle, on peut se demander.

Mettre card au lieu de point et picture au lieu de line et les axiomes de devenir:

• Tous les deux cartes ont exactement une image en commun.
• Pour tous les deux photos il y a exactement une carte a deux.

Maintenant, regardons n=7 et nous avons l' order-7 fini géométrie Q = 7^2 + 7 + 1 . Que fait Q=57 des lignes (photos) et Q=57 de points (les cartes). Je suppose que le puzzle décideurs décidé que 55 est plus rond que 57 de gauche et de 2 cartes.

Nous avons également obtenir de l' n+1 = 8, donc à partir de chaque point de la carte), 8 lignes de passe (8 photos apparaissent) et chaque ligne (photo) a 8 points (apparaît dans 8 cartes).

---

Voici une représentation de la plus célèbre finis projectif (ordre 2) avion (géométrie) avec 7 points, connu comme Plan de Fano, copié à partir de Noelle Evans - Finis Problème de Géométrie Page

Je pensais à la création d'une image qui expliquent comment l'ordre ci-dessus-2 plan pourrait être le même casse-tête avec 7 cartes et 7 photos, mais alors un lien à partir de la mathématique.l'échange de jumeaux question a exactement un tel diagramme: Dobble-et-la-geometrie-finie

Answer 2

Il y a donc k=55 cartes contenant m=8 images chacune à partir d'un pool de n images au total. Nous pouvons reformuler la question "Combien de photos n avons-nous besoin, de sorte que nous pouvons construire un ensemble de k cartes avec un seul d'images partagés entre toutes les paires de cartes?" de manière équivalente par demander:

Étant donné un n-dimensions d'espace vectoriel et de l'ensemble de tous les vecteurs qui contiennent exactement les m éléments égal à un et tous les autres zéro, quelle a n , de sorte que l'on peut trouver un ensemble de k vecteurs, dont les paires point des produits sont tous égaux à 1?

Il y a exactement (n choisissez m) possible vecteurs pour construire des paires de. Donc, nous avons au moins besoin d'un assez grand n , de sorte que (n choisissez m) >= k. C'est juste une limite inférieure, afin de remplir les paires de compatibilité contrainte nous avons peut-être besoin de beaucoup plus de n.

Juste pour expérimenter un peu, j'ai écrit un petit programme Haskell pour calculer valide jeux de carte:

Edit: je viens de réaliser, après avoir vu de Neil et Gajet la solution de l'algorithme j'utilise ne permet pas toujours de trouver la meilleure solution possible, donc tout ci-dessous n'est pas nécessairement valide. Je vais essayer de mettre à jour mon code rapidement.

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

Le résultant nombre maximal de cartes compatibles pour m=8 photos par carte pour différents nombre de photos à choisir n pour les premiers n ressemble à ceci:

Cette brute force méthode n'est pas très loin mais à cause de l'explosion combinatoire. Mais j'ai pensé qu'il pourrait être intéressante.

Fait intéressant, il semble que pour m, k augmente avec n seulement jusqu'à un certain n, après quoi elle reste constante.

Cela signifie que pour chaque nombre d'images par la carte il y a un certain nombre de photos à choisir, que les résultats de nombre maximum possible de juridique cartes. Ajout de photos à choisir dans le passé que le nombre optimal de ne pas augmenter le nombre de juridique cartes.

Les premiers optimal k's sont:

Answer 3

Je viens de trouver un moyen de le faire avec 57 ou 58 photos, mais maintenant, j'ai un très gros mal de tête, je vais poster le code ruby dans 8-10 heures après j'ai bien dormi! juste un conseil, mon solution de tous les 7 cartes de partager la même marque et le total de 56 cartes peuvent être construits à l'aide de ma solution.

voici le code qui génère toutes les 57 cartes ypercube était en train de parler. il utilise exactement 57 photos, et désolé les gars j'ai écrit réels de code C++, mais en sachant que vector <something> est un tableau contenant des valeurs de type something il est facile de comprendre ce que ce code ne. et ce code génère P^2+P+1 cartes à l'aide de P^2+P+1 photos contenant chacun P+1 image et le partage de seulement 1 image en commun, pour chaque nombre premier P de la valeur. ce qui signifie que nous pouvons avoir 7 cartes à l'aide de 7 photos ayant chacun 3 photos(pour p=2), 13 cartes à l'aide de 13 photos(pour p=3), 31 cartes à l'aide du 31 photos(pour p=5), 57 cartes pour les 57 photos(pour p=7) et ainsi de suite...

#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();
    }
}

encore une fois désolé pour le retard de code.

Answer 4

Voici les solution de Gajet en Python, puisque je trouve Python plus lisible. J’ai modifié il afin qu’il fonctionne avec non-nombres premiers établissements. J’ai utilisé un aperçu Thies pour générer du code d’affichage plus facile à comprendre.

Avec la sortie :

Answer 5

OK, essayons ceci : étant donné les 2 cartes au hasard du jeu de 55 cartes, nous avons toujours obtenir une paire de 8 photos sur chacun d’eux. 7 8 fois (en combinaison avec autres objectes) nous donne 56 combinaisons. Avec cette information, on peut le deviner, que deux cartes au hasard, afin d’être dans ce deck, le devoir de partager au moins un symbole. C’est ma supposition sauvage.

Pseudo-code :