157 votos

¿Cuáles son los principios de cálculo / matemáticas detrás de este juego?

Mis hijos tienen este divertido juego llamado Spot! El juego de las restricciones (como mejor puedo describir) son:

  • Es una baraja de 55 cartas
  • En cada tarjeta es de 8 imágenes únicas (es decir, una tarjeta que no puede tener 2 de la misma imagen)
  • Dado a cualquiera de las 2 tarjetas elegido desde la cubierta, hay 1 y solo 1 imagen correspondiente.
  • La coincidencia de las fotografías pueden ampliarse de manera diferente en diferentes tarjetas, pero que es sólo para hacer el juego más difícil (es decir, un árbol pequeño, que todavía coincide con un árbol grande)

El principio del juego es: flip más de 2 cartas y quien primero escoge la imagen correspondiente obtiene un punto.

Aquí está una foto de aclaración:

spot it

(Ejemplo: se puede ver desde la parte de abajo 2 cartas por encima de la correspondencia de la imagen es la de dinosaurio de color verde. Entre la parte inferior-derecha y centro-derecha de la imagen, es un payaso de la cabeza.)

Estoy tratando de comprender lo siguiente:

  1. ¿Cuál es el mínimo número de imágenes diferentes necesario cumplir estos criterios y cómo determinar esto?

  2. Utilizando pseudocódigo (o Ruby), ¿cómo se generan 55 tarjetas de juego a partir de una matriz de N imágenes (donde N es el mínimo número de la pregunta 1)?

Actualización:

Las imágenes se producen más de dos veces en cada deck (contrario a lo que algunos han conjeturado). Ver esta imagen de 3 cartas, cada una con un rayo:3 cards

116voto

ypercube Puntos 62714

Finito Proyectiva Geometrías

Los axiomas de la proyectiva (plano) de la geometría son ligeramente diferentes de la geometría Euclidiana:

  • Cada dos puntos tienen exactamente una línea que pasa a través de ellos (es el mismo).
  • Cada dos líneas de cumplir en exactamente un punto (esto es un poco diferente de la de Euclides).

Ahora, agregue "finito" en la sopa y tendrás la pregunta:

Podemos tener una geometría con sólo 2 puntos? Con 3 puntos? Con 4? Con 7?

Todavía hay preguntas abiertas sobre este problema, pero sí sabemos esto:

  • Si hay geometrías con Q puntos Q = n^2 + n + 1 y n se llama la order de la geometría.
  • Hay n+1 puntos en cada línea.
  • A partir de cada punto, pasar exactamente n+1 líneas.
  • Número Total de líneas es también Q.

  • Y por último, si n es un número primo, entonces no existe una geometría de orden n.


¿Qué tiene que ver con el rompecabezas, uno se puede preguntar.

Poner card en lugar de point y picture en lugar de line y los axiomas ser:

  • Cada dos tarjetas tienen exactamente una imagen en común.
  • Por cada dos fotos no es exactamente una tarjeta que tiene dos de ellos.

Ahora, vamos a echar n=7 y tenemos la order-7 finito de geometría, Q = 7^2 + 7 + 1 . Que hace Q=57 líneas, (fotos) y Q=57 puntos (tarjetas). Supongo que el rompecabezas de los fabricantes decidieron que 55 es más redondo número de 57 y a la izquierda 2 cartas.

También podemos n+1 = 8, por lo que desde todos los puntos (de la tarjeta), 8 líneas de pase (8 imágenes) y cada línea (en la foto) tiene 8 puntos (aparece en 8 cartas).


Aquí una representación de la más famosa proyectiva finita (de orden 2) plano (geometría) con 7 puntos, conocido como Plano de Fano, copiado de Noelle Evans - Finito Geometría del Problema de la Página

enter image description here

Yo estaba pensando en crear una imagen que explique cómo el orden anterior-2 plano podría ser algo similar rompecabezas con 7 cartas y 7 fotos, pero, a continuación, un enlace desde el math.exchange doble pregunta tiene exactamente un diagrama de este tipo: Dobble-et-la-geometrie-finie

Fano Plane

14voto

Thies Heidecke Puntos 1609

Así que hay k=55 tarjetas con m=8 fotos cada una a partir de un conjunto de n imágenes en total. Podemos reformular la pregunta " ¿cuántas fotos n necesitamos, de modo que podemos construir un conjunto de k tarjetas con sólo una imagen compartida entre cualquier par de cartas?', equivalentemente, preguntando:

Dada una n-dimensional espacio vectorial y el conjunto de todos los vectores, que contienen exactamente m elementos igual a uno y todos los demás cero, cómo de grande ha de n , por lo que podemos encontrar un conjunto de k vectores, cuyos pares dot los productos son todos iguales a 1?

Hay exactamente (n elija m) posibles vectores para generar pares. Así que necesitamos al menos una lo suficientemente grande como n (n elija m) >= k. Esto es sólo un límite inferior, por lo que para el cumplimiento de los pares de compatibilidad de restricción posiblemente necesita un mucho mayor n.

Sólo para experimentar un poco escribí un pequeño Haskell programa para calcular la validez de la tarjeta de conjuntos:

Edit: me acabo de dar cuenta que después de ver a Neil y Gajet la solución, que el algoritmo yo uso no siempre encontrar la mejor solución posible, así que todo lo de abajo no es necesariamente válida. Voy a tratar de actualizar mi código de pronto.

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

El resultando número máximo de tarjetas compatibles para m=8 imágenes por tarjeta para diferente número de imágenes a elegir de n para los primeros n se parece a esto:



Este método de fuerza bruta no llegará muy lejos, aunque debido a la explosión combinatoria. Pero pensé que todavía podría ser interesante.

Curiosamente, parece que para que dado m, k aumenta con n sólo hasta un cierto n, después de lo cual se mantiene constante.

Esto significa, que por cada número de imágenes por tarjeta hay un cierto número de imágenes a elegir, que se traduce en el máximo número posible de tarjetas legal. Agregar más imágenes a elegir pasado que el número óptimo no aumenta el número de tarjetas legal.

Los primeros óptimo de k's son:

optimal k table

7voto

Ali.S Puntos 1990

Acabo de encontrar una manera de hacerlo con 57 o 58 fotos, pero ahora tengo un dolor de cabeza muy fuerte, voy a publicar el código ruby en 8-10 horas después de haber dormido bien! sólo una sugerencia de mi de mi de la solución de cada 7 tarjetas de compartir la misma marca y total de 56 cartas puede ser construido con mi solución.

aquí está el código que genera todo el 57 cartas que ypercube estaba hablando. se utiliza exactamente 57 fotos, y lo siento chico, he escrito reales de código de C++, pero saber que vector <something> es una matriz que contiene los valores de tipo something es fácil de entender lo que este código. y este código genera P^2+P+1 tarjetas utilizando P^2+P+1 fotos de cada una conteniendo P+1 foto y compartir solo 1 imagen en común, para todos los primos P valor. lo que significa que podemos tener 7 cartas con 7 fotos cada una tiene 3 imágenes(para p=2), 13 tarjetas con 13 imágenes(para p=3), el 31 de tarjetas con 31 imágenes(para p=5), 57 tarjetas de 57 imágenes(para p=7) y así sucesivamente...

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

de nuevo lo siento por el retraso en el código.

5voto

Neil G Puntos 7028

Aquí está la solución de Gajet en Python, ya que me parece Python más legible. He modificado para que funcione con números no primos también. He utilizado una visión Thies para generar un código de visualización más fácil de entender.

 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)
 

Con salida:

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

-6voto

alfa64 Puntos 1355

ok, vamos a probar esto: dado 2 cartas al azar de la baraja de 55 cartas, siempre nos dan un par de 8 imágenes en cada uno. 8 veces 7 (combinaciones con otros simbols) nos da 56 combinaciones. Con esa información podemos adivinar, que da dos cartas al azar, con el fin de estar en esta cubierta, la tienen que compartir al menos un símbolo. Esa es mi suposición.

pseudocódigo:

 count:=0;
for i:=1 to 7 do
   for j:=1 to 8 do
      count+=1;
      print "card " && count && "haz zimbol" && j
   next j
next i
 

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: