algorithm - qué - ¿Cuáles son los principios matemáticos/computacionales detrás de este juego?

nicolas bourbaki ø

Question

Mis hijos tienen este divertido juego llamado Spot It! Las limitaciones del juego (lo mejor que puedo describir) son:

• Es un mazo de 55 cartas
• En cada tarjeta hay 8 imágenes únicas (es decir, una carta no puede tener 2 de la misma imagen)
• Dadas 2 cartas elegidas del mazo, hay 1 y solo 1 foto correspondiente .
• Las imágenes coincidentes se pueden escalar de forma diferente en diferentes cartas, pero eso es solo para hacer el juego más difícil (es decir, un árbol pequeño aún coincide con un árbol más grande)

El principio del juego es: dar la vuelta a 2 cartas y quien escoja primero la imagen correspondiente obtiene un punto.

Aquí hay una imagen para aclarar:

(Ejemplo: puede ver desde abajo 2 tarjetas que la imagen correspondiente es el dinosaurio verde. Entre la imagen inferior derecha y la imagen central derecha, es la cabeza de un payaso).

Estoy tratando de entender lo siguiente:

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

2. Usando un pseudocódigo (o Ruby), ¿cómo generarías 55 cartas de juego de un conjunto de N imágenes (donde N es el número mínimo de la pregunta 1)?

Actualizar:

Las imágenes ocurren más de dos veces por mazo (a diferencia de lo que algunos han supuesto). Mira esta imagen de 3 cartas, cada una con un rayo:

Answer 1

Acabo de encontrar una manera de hacerlo con 57 o 58 fotos pero ahora tengo un dolor de cabeza muy fuerte, ¡publicaré el código de rubí en 8-10 horas después de haber dormido bien! Solo una pista mi solución: cada 7 tarjetas comparten la misma marca y se pueden construir un total de 56 tarjetas con mi solución.

aquí está el código que genera todas las 57 cartas de las que Ypercube estaba hablando. usa exactamente 57 imágenes, y lo siento amigo, he escrito código C ++ real, pero sabiendo que vector <something> es una matriz que contiene valores de tipo something , es fácil entender lo que hace este código. y este código genera tarjetas P^2+P+1 usando P^2+P+1 imágenes cada una conteniendo P+1 imagen y compartiendo solo 1 foto en común, para cada valor P principal. lo que significa que podemos tener 7 tarjetas con 7 imágenes, cada una con 3 imágenes (para p = 2), 13 tarjetas con 13 imágenes (para p = 3), 31 tarjetas con 31 imágenes (para p = 5), 57 tarjetas para 57 fotos (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 código retrasado.

Answer 2

Aquí está la solución de Gajet en Python, ya que considero que Python es más legible. Lo he modificado para que también funcione con números no primos. He utilizado Thies Insight 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:

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

Answer 3

Entonces, hay k = 55 cartas que contienen m = 8 imágenes cada una de un grupo de n imágenes en total. Podemos repetir la pregunta ''¿Cuántas imágenes necesitamos para poder construir un conjunto de k cartas con una sola imagen compartida entre un par de cartas?'' equivalentemente preguntando:

Dado un espacio vectorial n- dimensional y el conjunto de todos los vectores, que contienen exactamente m elementos iguales a uno y todos los otros cero, qué tan grande debe ser n , de modo que podamos encontrar un conjunto de k vectores, cuyos productos de puntos pairwise son todo igual a 1 ?

Hay exactamente ( n elija m ) posibles vectores para construir pares. Por lo tanto, al menos necesitamos una n suficientemente grande para que ( n elija m )> = k . Esto es solo un límite inferior, por lo que para cumplir la restricción de compatibilidad por pares posiblemente necesitemos una n mucho mayor.

Solo por experimentar un poco escribí un pequeño programa Haskell para calcular juegos de cartas válidos:

Editar: Me acabo de dar cuenta después de ver la solución de Neil y Gajet, que el algoritmo que uso no siempre encuentra la mejor solución posible, por lo que todo lo que sigue a continuación no es necesariamente válido. Trataré de actualizar mi código 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 número máximo resultante de tarjetas compatibles para m = 8 imágenes por tarjeta para diferentes números de imágenes para elegir n para las primeras n tiene este aspecto:

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

Curiosamente, parece que para m dado, k aumenta con n solo hasta cierto n , después del cual permanece constante.

Esto significa que, para cada número de imágenes por tarjeta, hay una cierta cantidad de imágenes para elegir, lo que da como resultado la cantidad máxima posible de tarjetas legales. Agregar más imágenes para elegir más allá de ese número óptimo no aumenta más el número de tarjetas legales.

Los primeros pocos k óptimos son:

Answer 4

Escribí un article sobre cómo generar este tipo de mazos, con código en Perl. El código no está optimizado, pero al menos es capaz de generar mazos de órdenes "razonables" ... y algo más.

Aquí hay un ejemplo con el orden 8, que tiene que considerar una matemática subyacente un poco más complicada, porque 8 no es primo, aunque es un orden válido para generar este tipo de mazos. Vea arriba o el artículo para una explicación más detallada, a continuación, si solo desea generar un Spot-It ligeramente más difícil :-)

$ time pg2 8
elements in field: 8
0. (1, 9, 17, 25, 33, 41, 49, 57, 65)
1. (0, 9, 10, 11, 12, 13, 14, 15, 16)
2. (2, 9, 18, 27, 36, 45, 54, 63, 72)
3. (6, 9, 22, 26, 37, 43, 56, 60, 71)
4. (7, 9, 23, 32, 34, 46, 52, 59, 69)
5. (8, 9, 24, 30, 35, 42, 55, 61, 68)
6. (3, 9, 19, 29, 39, 44, 50, 64, 70)
7. (4, 9, 20, 31, 38, 48, 53, 58, 67)
8. (5, 9, 21, 28, 40, 47, 51, 62, 66)
9. (0, 1, 2, 3, 4, 5, 6, 7, 8)
10. (1, 10, 18, 26, 34, 42, 50, 58, 66)
11. (1, 14, 22, 30, 38, 46, 54, 62, 70)
12. (1, 15, 23, 31, 39, 47, 55, 63, 71)
13. (1, 16, 24, 32, 40, 48, 56, 64, 72)
14. (1, 11, 19, 27, 35, 43, 51, 59, 67)
15. (1, 12, 20, 28, 36, 44, 52, 60, 68)
16. (1, 13, 21, 29, 37, 45, 53, 61, 69)
17. (0, 17, 18, 19, 20, 21, 22, 23, 24)
18. (2, 10, 17, 28, 35, 46, 53, 64, 71)
19. (6, 14, 17, 29, 34, 48, 51, 63, 68)
20. (7, 15, 17, 26, 40, 44, 54, 61, 67)
21. (8, 16, 17, 27, 38, 47, 50, 60, 69)
22. (3, 11, 17, 31, 37, 42, 52, 62, 72)
23. (4, 12, 17, 30, 39, 45, 56, 59, 66)
24. (5, 13, 17, 32, 36, 43, 55, 58, 70)
25. (0, 49, 50, 51, 52, 53, 54, 55, 56)
26. (3, 10, 20, 30, 40, 43, 49, 63, 69)
27. (2, 14, 21, 32, 39, 42, 49, 60, 67)
28. (8, 15, 18, 28, 37, 48, 49, 59, 70)
29. (6, 16, 19, 31, 36, 46, 49, 61, 66)
30. (5, 11, 23, 26, 38, 45, 49, 64, 68)
31. (7, 12, 22, 29, 35, 47, 49, 58, 72)
32. (4, 13, 24, 27, 34, 44, 49, 62, 71)
33. (0, 57, 58, 59, 60, 61, 62, 63, 64)
34. (4, 10, 19, 32, 37, 47, 54, 57, 68)
35. (5, 14, 18, 31, 35, 44, 56, 57, 69)
36. (2, 15, 24, 29, 38, 43, 52, 57, 66)
37. (3, 16, 22, 28, 34, 45, 55, 57, 67)
38. (7, 11, 21, 30, 36, 48, 50, 57, 71)
39. (6, 12, 23, 27, 40, 42, 53, 57, 70)
40. (8, 13, 20, 26, 39, 46, 51, 57, 72)
41. (0, 65, 66, 67, 68, 69, 70, 71, 72)
42. (5, 10, 22, 27, 39, 48, 52, 61, 65)
43. (3, 14, 24, 26, 36, 47, 53, 59, 65)
44. (6, 15, 20, 32, 35, 45, 50, 62, 65)
45. (2, 16, 23, 30, 37, 44, 51, 58, 65)
46. (4, 11, 18, 29, 40, 46, 55, 60, 65)
47. (8, 12, 21, 31, 34, 43, 54, 64, 65)
48. (7, 13, 19, 28, 38, 42, 56, 63, 65)
49. (0, 25, 26, 27, 28, 29, 30, 31, 32)
50. (6, 10, 21, 25, 38, 44, 55, 59, 72)
51. (8, 14, 19, 25, 40, 45, 52, 58, 71)
52. (4, 15, 22, 25, 36, 42, 51, 64, 69)
53. (7, 16, 18, 25, 39, 43, 53, 62, 68)
54. (2, 11, 20, 25, 34, 47, 56, 61, 70)
55. (5, 12, 24, 25, 37, 46, 50, 63, 67)
56. (3, 13, 23, 25, 35, 48, 54, 60, 66)
57. (0, 33, 34, 35, 36, 37, 38, 39, 40)
58. (7, 10, 24, 31, 33, 45, 51, 60, 70)
59. (4, 14, 23, 28, 33, 43, 50, 61, 72)
60. (3, 15, 21, 27, 33, 46, 56, 58, 68)
61. (5, 16, 20, 29, 33, 42, 54, 59, 71)
62. (8, 11, 22, 32, 33, 44, 53, 63, 66)
63. (2, 12, 19, 26, 33, 48, 55, 62, 69)
64. (6, 13, 18, 30, 33, 47, 52, 64, 67)
65. (0, 41, 42, 43, 44, 45, 46, 47, 48)
66. (8, 10, 23, 29, 36, 41, 56, 62, 67)
67. (7, 14, 20, 27, 37, 41, 55, 64, 66)
68. (5, 15, 19, 30, 34, 41, 53, 60, 72)
69. (4, 16, 21, 26, 35, 41, 52, 63, 70)
70. (6, 11, 24, 28, 39, 41, 54, 58, 69)
71. (3, 12, 18, 32, 38, 41, 51, 61, 71)
72. (2, 13, 22, 31, 40, 41, 50, 59, 68)
errors in check: 0
real 0m0.303s
user 0m0.200s
sys 0m0.016s

Cada identificador de 0 a 72 puede leerse como un identificador de tarjeta y como un identificador de imagen. Por ejemplo, la última fila significa que:

• la tarjeta 72 contiene imágenes 2 , 13 , 22 , ..., 59 , 68 , Y
• la imagen 72 aparece en las tarjetas 2 , 13 , 22 , ..., 59 y 68 .

Answer 5

Me gusta mucho este hilo. Construyo este proyecto github python con partes de este código aquí para dibujar tarjetas personalizadas como png (por lo que uno puede ordenar juegos de cartas personalizados en Internet).

https://github.com/plagtag/ProjectiveGeometry-Game

Answer 6

Otros han descrito el marco general para el diseño (plano proyectivo finito) y se muestra cómo generar planos proyectivos finitos de primer orden. Me gustaría llenar algunos vacíos.

Los planos proyectivos finitos se pueden generar para muchos órdenes diferentes, pero son más sencillos en el caso de orden principal p . Luego, los enteros módulo p forman un campo finito que se puede usar para describir las coordenadas de los puntos y líneas en el plano. Hay 3 tipos diferentes de coordenadas para los puntos: (1,x,y) , (0,1,x) y (0,0,1) , donde y pueden tomar valores de 0 a p-1 . Los 3 tipos diferentes de puntos explican la fórmula p^2+p+1 para la cantidad de puntos en el sistema. También podemos describir líneas con los mismos 3 tipos diferentes de coordenadas: [1,x,y] , [0,1,x] y [0,0,1] .

Calculamos si un punto y una línea son incidentes según si el producto escalar de sus coordenadas es igual a 0 mod p . Entonces, por ejemplo, el punto (1,2,5) y la línea [0,1,1] son incidentes cuando p=7 desde 1*0+2*1+5*1 = 7 == 0 mod 7 , pero el el punto (1,3,3) y la línea [1,2,6] no son incidentes, ya que 1*1+3*2+3*6 = 25 != 0 mod 7 .

Traduciendo al lenguaje de tarjetas e imágenes, eso significa que la tarjeta con coordenadas (1,2,5) contiene la imagen con coordenadas [0,1,1] , pero la tarjeta con coordenadas (1,3,3) no contiene la imagen con coordenadas [1,2,6] . Podemos usar este procedimiento para desarrollar una lista completa de tarjetas y las imágenes que contienen.

Por cierto, creo que es más fácil pensar en imágenes como puntos y cartas como líneas, pero hay una dualidad en geometría proyectiva entre puntos y líneas, así que realmente no importa. Sin embargo, en lo que sigue usaré puntos para imágenes y líneas para tarjetas.

La misma construcción funciona para cualquier campo finito. Sabemos que hay un campo de orden finito q si y solo si q=p^k , una potencia principal. El campo se llama GF(p^k) que significa "campo de Galois". Los campos no son tan fáciles de construir en el caso de energía principal como en el caso principal.

Afortunadamente, el trabajo duro ya se ha realizado e implementado en software libre, es decir, Sage . Para obtener un diseño de plano proyectivo de orden 4, por ejemplo, solo escriba

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

y obtendrás un resultado que se parece a

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]]>

Interpreto lo anterior de la siguiente manera: hay 21 imágenes etiquetadas de 0 a 20. Cada uno de los bloques (línea en geometría proyectiva) me dice qué imágenes aparecen en una tarjeta. Por ejemplo, la primera tarjeta tendrá imágenes 0, 1, 2, 3 y 20; la segunda tarjeta tendrá imágenes 0, 4, 8, 12 y 16; y así.

El sistema de orden 7 puede ser generado por

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

que genera la salida

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 7

Para aquellos que tienen problemas para representar la geometría del plano proyectivo con 57 puntos, hay una manera realmente agradable e intuitiva de construir el juego con 57 cartas y 57 símbolos (en base a la respuesta de Yuval Filmus para esta pregunta ):

1. Para cartas con 8 símbolos, crea una cuadrícula 7x7 de símbolos únicos.
2. Agregue 8 símbolos adicionales para las "pendientes" de 0 a 6, más uno para la pendiente infinita.
3. Cada carta es una línea en la cuadrícula (7 símbolos) más un símbolo de la pendiente establecida para la pendiente de la línea. Las líneas tienen un desplazamiento (es decir, un punto de inicio a la izquierda) y una pendiente (es decir, cuántos símbolos subir para cada paso a la derecha). Cuando la línea sale de la cuadrícula en la parte superior, vuelva a ingresar en la parte inferior. Vea esta figura de ejemplo (imágenes de boardgamegeek ) para dos de estas cartas:

En el ejemplo, tomo una línea con pendiente cero (rojo) y una con pendiente 1 (verde). Se cruzan exactamente en un punto común (el búho).

Este método asegura que dos cartas tengan exactamente un símbolo común, porque

1. Si las pendientes son diferentes, las líneas siempre se cruzan exactamente en un punto.
2. Si las pendientes son las mismas, las líneas no se intersectarán y no habrá un símbolo común de la cuadrícula. En este caso, el símbolo de pendiente será el mismo.

De esta forma, podemos construir tarjetas 7x7 (7 desplazamientos y 7 pendientes).

También podemos construir siete cartas adicionales a partir de líneas verticales a través de la cuadrícula (es decir, tomando cada columna). Para ellos, se usa el ícono de la pendiente infinita.

Como cada carta consta de siete símbolos de la cuadrícula y exactamente un símbolo de "pendiente", podemos crear una carta adicional, que consiste simplemente en los 8 símbolos de pendiente.

Esto nos deja con 7x8 + 1 = 57 cartas posibles, y 7 x 7 + 8 = 57 símbolos requeridos.

(Naturalmente, esto solo funciona con una cuadrícula del tamaño del número primo (p. Ej., N = 7). De lo contrario, las líneas de diferente pendiente podrían tener cero o más de una intersección si la pendiente es un divisor del tamaño de la cuadrícula).

Answer 8

Geometría proyectiva finita

Los axioms de la geometría proyectiva (plana) son ligeramente diferentes a la geometría euclidiana:

• Cada dos puntos tienen exactamente una línea que los atraviesa (es lo mismo).
• Cada dos líneas se encuentran en exactamente un punto (esto es un poco diferente de Euclid).

Ahora, agrega "finite" a la sopa y tienes la pregunta:

¿Podemos tener una geometría con solo 2 puntos? Con 3 puntos? Con 4? Con 7?

Todavía hay preguntas abiertas con respecto a este problema, pero sí lo sabemos:

• Si hay geometrías con puntos Q , entonces Q = n^2 + n + 1 y n se llama el order de la geometría.
• Hay n+1 puntos en cada línea.
• De cada punto, pasa exactamente n+1 líneas.

• El número total de líneas también es Q

• Y finalmente, si n es primo, entonces existe una geometría de orden n .

¿Qué tiene eso que ver con el acertijo, uno puede preguntar?

Coloque la card lugar del point y la picture lugar de la line y los axiomas se convierten en:

• Cada dos cartas tienen exactamente una imagen en común.
• Por cada dos imágenes hay exactamente una carta que tiene ambas.

Ahora, tomemos n=7 y tenemos la geometría finita de order-7 con Q = 7^2 + 7 + 1 . Eso hace que Q=57 líneas (imágenes) y Q=57 puntos (tarjetas). Supongo que los creadores de acertijos decidieron que 55 es un número más redondo que 57 y dejaron 2 cartas.

También obtenemos n+1 = 8 , por lo que desde cada punto (tarjeta), pasan 8 líneas (aparecen 8 imágenes) y cada línea (imagen) tiene 8 puntos (aparece en 8 tarjetas).

Aquí hay una representación del plano (geometría) proyectivo finito (orden-2) más famoso con 7 puntos, conocido como Plano Fano , copiado de Noelle Evans - Página de problemas de geometría finita

Estaba pensando en crear una imagen que explique cómo el avión de orden 2 anterior podría convertirse en un rompecabezas similar con 7 tarjetas y 7 imágenes, pero luego un enlace de la pregunta gemela math.exchange tiene exactamente ese diagrama: Dobble-et-la-geometrie-finie

Answer 9

Usando el probador de teorema z3

Deje que P sea ​​la cantidad de símbolos por tarjeta. Según este artículo y la respuesta de ypercubeᵀᴹ , hay N = P**2 - P + 1 tarjetas y símbolos, respectivamente. Un mazo de cartas se puede representar con su matriz de incidencia que tiene una fila para cada carta y una columna para cada símbolo posible. Su elemento (i,j) es 1 si la tarjeta i tiene el símbolo j en ella. Solo tenemos que llenar esta matriz con estas restricciones en mente:

• cada elemento es cero o uno
• la suma de cada fila es exactamente P
• la suma de cada columna es exactamente P
• dos filas deben tener exactamente un símbolo en común

Eso significa N**2 variables y N**2 + 2*N + (N choose 2) restricciones. Parece ser manejable en un tiempo no tan largo con z3 para pequeñas entradas.

editar : Desafortunadamente P = 8 parece ser demasiado grande para este método. Maté el proceso después de 14 horas de tiempo de cálculo.

from z3 import *
from itertools import combinations
def is_prime_exponent(K):
return K > 1 and K not in 6 # next non-prime exponent is 10,
# but that is too big anyway
def transposed(rows):
return zip(*rows)
def spotit_z3(symbols_per_card):
K = symbols_per_card - 1
N = symbols_per_card ** 2 - symbols_per_card + 1
if not is_prime_exponent(K):
raise TypeError("Symbols per card must be a prime exponent plus one.")
constraints = []
# the rows of the incidence matrix
s = N.bit_length()
rows = [[BitVec("r%dc%d" % (r, c), s) for c in range(N)] for r in range(N)]
# every element must be either 1 or 0
constraints += [Or([elem == 1, elem == 0]) for row in rows for elem in row]
# sum of rows and cols must be exactly symbols_per_card
constraints += [Sum(row) == symbols_per_card for row in rows]
constraints += [Sum(col) == symbols_per_card for col in transposed(rows)]
# Any two rows must have exactly one symbol in common, in other words they
# differ in (symbols_per_card - 1) symbols, so their element-wise XOR will
# have 2 * (symbols_per_card - 1) ones.
D = 2 * (symbols_per_card - 1)
for row_a, row_b in combinations(rows, 2):
constraints += [Sum([a ^ b for a, b in zip(row_a, row_b)]) == D]
solver = Solver()
solver.add(constraints)
if solver.check() == unsat:
raise RuntimeError("Could not solve it :(")
# create the incidence matrix
model = solver.model()
return [[model[elem].as_long() for elem in row] for row in rows]
if __name__ == "__main__":
import sys
symbols_per_card = int(sys.argv[1])
incidence_matrix = spotit_z3(symbols_per_card)
for row in incidence_matrix:
print(row)

Resultados

$python spotit_z3.py 3
[0, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 1, 0, 0]
[1, 0, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 0, 0, 1]
python spotit_z3.py 3 1.12s user 0.06s system 96% cpu 1.225 total
$ time python3 spotit_z3.py 4
[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1]
[0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
python spotit_z3.py 4 664.62s user 0.15s system 99% cpu 11:04.88 total
$ time python3 spotit_z3.py 5
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1]
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
python spotit_z3.py 5 1162.72s user 20.34s system 99% cpu 19:43.39 total
$ time python3 spotit_z3.py 8
<I killed it after 14 hours of run time.>