7 votos

Contando las fichas del juego Tsuro

Me gustaría contar el número de Tsuro fichas de juego. En el juego, una ficha es un cuadrado con dos puntos en cada lado donde cada punto está conectado exactamente con otro punto (ningún punto se conecta a sí mismo). Las baldosas se pueden girar, así que me gustaría contar el número de baldosas únicas. El juego viene con 35 fichas.

¿Debería tratar esto como un problema de coloración sobre el número de pares de puntos e intentar utilizar la enumeración de Polya? Si es así, agradecería una pista.

¿Hay algún método mejor, algo fácil que se me haya escapado?

En definitiva, me gustaría un método generalizable (digamos n puntos en cada lado).

Gracias.

1 votos

Crudamente, parece que se podría hacer lo siguiente. Elegir una orientación y etiquetar los puntos de las aristas en el sentido de las agujas del reloj como $1,2,\dots,8$ . Entonces se quiere contar cuántas maneras de emparejar los 8 puntos. Esto es, por supuesto, sólo el coeficiente multinomial $8!/(2!2!2!2!)=7!/2=2520$ . Esto es definitivamente un límite superior en el número de fichas. Creo que se obtiene un límite inferior si se asume que para cada baldosa, las 4 rotaciones posibles son idénticas; entonces habría $7!/8=630$ posibles baldosas. No estoy seguro de que esto sea un límite inferior válido, porque no estoy seguro de si todavía cuenta algo doble.

1 votos

(Cont.) Tratar con el hecho de que diferentes baldosas tienen diferentes grados de simetría rotacional parece un problema difícil en la situación general, que podría tener que abordar con algo de teoría de grupos.

0 votos

2voto

mjqxxxx Puntos 22955

La forma habitual de hacerlo es utilizando el lema de Burnside, que dice que el tamaño del grupo cociente viene dado por $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^{g}|, $$ donde $|X^{g}|$ es el número de elementos de $X$ arreglado por $g$ . Aquí $G$ es el grupo cíclico de orden cuatro, y cada ficha de Tsuro puede no tener simetría, o $180^{\circ}$ simetría rotacional, o bien, la plena $90^{\circ}$ simetría rotacional. Por lo tanto, el número de fichas Tsuro no equivalentes viene dado por $$ \frac{1}{4}\left(|X|+|X_{2}|+2|X_{4}|\right). $$ Al contar las fichas con $180^{\circ}$ simetría rotacional, considera dos lados adyacentes. Puedes elegir algunos de estos puntos para emparejarlos con sus compañeros de espejo; los restantes (que deben ser pares) deben emparejarse entre sí, pero cada emparejamiento puede hacerse en $2$ diferentes maneras (puedes emparejar un punto con otro punto en la misma mitad o en la mitad del espejo). Del mismo modo, al contar fichas con $90^{\circ}$ simetría rotacional, se eligen algunos puntos para emparejarlos con sus compañeros de espejo, dejando un número par para emparejarlos entre sí, y cada uno de estos emparejamientos puede hacerse en $4$ diferentes maneras. G $q$ puntos, donde $q$ es uniforme, hay $(q-1)!!$ formas de emparejarlos entre sí. Así que si hay $n$ puntos en cada lado, y luego $$ |X| = (4n-1)!!, $$ $$ |X_2|=\sum_{k\le n}2^{k}{{2n}\choose{2k}}(2k-1)!!, $$ y $$ |X_4|=\sum_{k\le n/2}4^{k}{{n}\choose{2k}}(2k-1)!!. $$ Para $n=2$ entonces $$ |X|=7!!=105, \\ |X_2|=4\cdot 3!! + 2\cdot {{4}\choose{2}} + 1 = 25, \\ |X_4|=4+1=5,$$ así que $$ T_2 = \frac{1}{4}\left(105 + 25 + 2\cdot 5\right)=35. $$ Una implementación directa de Python es:

def fac(n, k=1):
  if n<=1: return 1
  return n*fac(n-k, k)

def ch(m, n):
  return fac(m)/(fac(n)*fac(m-n))

def T(n):
  x = fac(4*n-1, 2)
  x2 = sum([2**k * ch(2*n, 2*k) * fac(2*k-1, 2) for k in xrange(n+1)])
  x4 = sum([4**k * ch(n, 2*k) * fac(2*k-1, 2) for k in xrange(n/2+1)])
  return (x + x2 + 2*x4) / 4

Se reproducen los resultados conocidos:

>>> [T(n) for n in xrange(2,8)]
[35, 2688, 508277, 163715822, 79059439095, 53364540054860]

1 votos

Muy buen trabajo. (+1).

0voto

Marko Riedel Puntos 19255

Este problema puede ser tratado por Power Group Enumeration y puedo publicar el código si hay interés. Sin embargo, en este caso particular es posible enumerar todos los azulejos diferentes, y la respuesta que obtenemos es $$35\quad\text{tiles}.$$

Este es el código de Maple para este cálculo.

with(combinat);
with(numtheory);

verif :=
proc()
    option remember;
    local eset, res, all, sel, p, q, rotind, sl, item;

    eset :=
    {seq(seq(U\[p\]\*U\[q\], q=p+1..7), p=0..7)};

    res := {}; all := mul(U\[p\], p=0..7);

    sl := \[\];
    for rotind to 3 do
        sl := \[op(sl),
               \[seq(U\[p\]=U\[(p+2\*rotind) mod 8\], p=0..7)\]\];
    od;

    for sel in choose(eset, 4) do
        if mul(sel\[p\], p=1..4) = all then
            item := {sel};

            for rotind to 3 do
                item := item
                union {subs(sl\[rotind\], sel)};
            od;

            res := res union {item};
        fi;
    od;

    nops(res);
end;

Observación. Sospecho que el enfoque PGE podría ser capaz de contar baldosas con $n$ puntos por lado donde la enumeración directa ya no es factible.

0voto

Marko Riedel Puntos 19255

A modo de respuesta a la pregunta de cómo la Enumeración de Grupos de Potencia a este problema, he conseguido aplicar PGE y, de hecho, esto me ha llevado a revisar parte de mi software PGE. hecho, esto me llevó a revisar parte de mi software PGE, lo que agradezco gracias por ello. PGE permite calcular los cinco primeros valores de $n$ conectores por lado, que son $$2, 35, 2688, 508277, 163715822, \ldots$$

Esto nos lleva a OEIS A132100 donde aprendemos aprendemos que la forma correcta de abordar este problema es a través de un análisis combinatorio que produce una recurrencia bastante simple que puede utilizarse para calcular rápidamente valores grandes.

La técnica de PGE es exactamente la misma que presenté en este MSE enlace al contar subconjuntos de tamaño $k$ de una baraja de cartas bajo permutación de palos.

El repertorio de la función generadora son las aristas que representadas a través del producto de dos variables $U_k U_m$ que indica un borde de $k$ à $m.$ Seleccionamos un subconjunto de $q=4n/2$ de de modo que el grupo que actúa sobre las ranuras es el grupo simétrico $S_q$ actuando en $q$ elementos. El grupo $Q$ que permuta el repertorio es la acción de las cuatro rotaciones del cuadrado sobre las aristas, que contiene cuatro permutaciones sobre $4n(4n-1)/2$ elementos. A continuación, ejecutamos el cálculo habitual de PGE sobre pares de permutaciones $(\alpha,\beta)$ con $\alpha\in S_q$ y $\beta\in Q$ , comprobando si podemos cubrir $\alpha$ con ciclos de $\beta$ y haciendo la contabilidad como descrito en el enlace de la baraja. Las contribuciones en las que un vértice aparece más de una vez no se conservan. (Estas representan un grado de vértice grado de más de uno que no admitimos). El código ha sido optimizado en varios aspectos, en particular la colocación de los ciclos de $\beta$ en $\alpha$ donde la complejidad y la huella de memoria son mucho mejor. Parece notable que un método complejo como PGE pueda implementarse en un programa tan compacto. Es posible una mayor optimización de los dos bucles principales es posible, pero no es probable que se extienda $n$ a seis.

Este es el código de Arce.

with(combinat);
with(numtheory);

pet\_flatten\_term :=
proc(varp)
local terml, d, cf, v;

    terml := \[\];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := \[op(terml), seq(v, k=1..d)\];
        cf := cf/v^d;
    od;

    \[cf, terml\];
end;

pet\_autom2cyclesA :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, data, item, cpos, clen;

    numsubs := \[seq(src\[k\]=k, k=1..nops(src))\];
    numa := subs(numsubs, aut);

    marks := Array(\[seq(true, pos=1..nops(aut))\]);

    cycs := \[\]; pos := 1; data := \[\];

    while pos <= nops(aut) do
        if marks\[pos\] then
            clen := 0; item := \[\]; cpos := pos;

            while marks\[cpos\] do
                marks\[cpos\] := false;
                item := \[op(item), aut\[cpos\]\];

                cpos := numa\[cpos\];
                clen := clen+1;
            od;

            cycs := \[op(cycs), clen\];
            data := \[op(data), item\];
        fi;

        pos := pos+1;
    od;

    return \[data, mul(a\[cycs\[k\]\], k=1..nops(cycs))\];
end;

pet\_cycleind\_symm :=
proc(n)
local p, s;
option remember;

    if n=0 then return 1; fi;

    expand(1/n\*add(a\[l\]\*pet\_cycleind\_symm(n-l), l=1..n));
end;

pet\_perms\_edges :=
proc(n)
    option remember;
    local cind, p, q, perm, sl,
    edges, edgeperm, rotind;

    edges :=
    \[seq(seq(U\[p\]\*U\[q\], q=p+1..4\*n-1), p=0..4\*n-1)\];

    cind := \[\];

    for rotind from 0 to 3 do
        sl :=
        \[seq(U\[p\]=U\[(p+n\*rotind) mod 4\*n\], p=0..4\*n-1)\];
        edgeperm := subs(sl, edges);

        cind :=
        \[op(cind), pet\_autom2cyclesA(edges, edgeperm)\];
    od;

    cind;
end;

choose\_sum\_prod :=
proc(data, pos, count)
    if count = 0 then return 1 fi;
    if nops(data) < pos + count -1 then return 0 fi;

    choose\_sum\_prod(data, pos+1, count) +
    data\[pos\]\*choose\_sum\_prod(data, pos+1, count-1);
end;

tiles :=
proc(n)
    option remember;
    local idx\_slots, idx\_edges, res, a, b, resA, term,
    flat\_a, flat\_b, cycs\_a, cycs\_b, p1, p2, q, v, admit,
    tbl\_a, tbl\_b, f1, f2, f3,
    cyc, cyc\_set, cyc\_contrib, cyc\_mset;

    idx\_slots := pet\_cycleind\_symm(4\*n/2);
    idx\_edges := pet\_perms\_edges(n);

    res := 0;

    for a in idx\_slots do
        flat\_a := pet\_flatten\_term(a);
        cycs\_a := sort(flat\_a\[2\]);

        tbl\_a := table();
        for q in convert(cycs\_a, 'multiset') do
            tbl\_a\[op(1, q\[1\])\] := q\[2\];
        od;

        f1 := map(q -> op(1, q), cycs\_a);
        f1 := mul(f1\[q\], q=1..nops(cycs\_a));

        for b in idx\_edges do
            flat\_b := pet\_flatten\_term(b\[2\]);
            cycs\_b := sort(flat\_b\[2\]);

            tbl\_b := table();
            for q in convert(cycs\_b, 'multiset') do
                tbl\_b\[op(1, q\[1\])\] := q\[2\];
            od;

            if tbl\_a\[1\] = 4\*n/2 and
            tbl\_b\[1\] = 4\*n\*(4\*n-1)/2 then
                res := res +
                (4\*n)!/(2^(4\*n/2))/(4\*n/2)!;
                next;
            fi;

            admit := true;
            for q in \[indices(tbl\_a, 'nolist')\] do
                if not (type(tbl\_b\[q\], integer) and
                        tbl\_b\[q\] >= tbl\_a\[q\]) then
                    admit := false;
                    break;
                fi;
            end;

            if not admit then next fi;

            f3 := 1;
            for q in \[indices(tbl\_a, 'nolist')\] do
                cyc\_set :=
                map(cyc->mul(p1, p1 in cyc),
                    select(cyc->nops(cyc)=q, b\[1\]));

                cyc\_contrib :=
                choose\_sum\_prod(cyc\_set, 1, tbl\_a\[q\]);

                f3 := f3\*tbl\_a\[q\]!\*cyc\_contrib;
            od;

            f3 := expand(f3);
            for v from 0 to 4\*n-1 do
                f3 := coeff(f3, U\[v\], 1);
            od;

            res := res +
            f1\*f3\*flat\_a\[1\]\*flat\_b\[1\];
        od;
    od;

    res/4;
end;

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X