¿Cuántos resultados únicos se pueden obtener a partir de las 12 fichas de río en Carcassonne?

Question

He estado reflexionando sobre esta pregunta durante algún tiempo y está un poco fuera de mi alcance resolverla. Me gustaría saber cuántos arreglos son posibles para la expansión del río 1 en Carcassonne.

Las reglas para jugar con el río son las siguientes: La loseta fuente se juega primero, la loseta del lago se juega al final y si dos curvas del río se dibujan en secuencia deben tener orientación opuesta.

Entiendo lo siguiente: La primera y última loseta jugada no se tendrán en cuenta en el conteo, así que solo miramos las $10$ losetas entre ellas. Cada loseta tiene $2$ orientaciones y hay $8$ losetas únicas, más $1$ esquina repetida y una recta repetida. También debemos excluir las posibilidades que se vuelven inútiles cuando el río hace una curva sobre sí mismo.

Aquí tienes una imagen de las $12$ losetas del río:

Mis primeros cálculos para contar son

$$\frac{(2^8)10!}{2!2!}$$

Mi razonamiento es: $10!/2!2!$ porque importa el orden de selección y las losetas repetidas se excluyen dividiendo por $2!$

$2^8$ porque cada loseta se puede colocar de $2$ maneras (las $2$ losetas rectas no se incluyen porque no son únicas)

Sé que está mal. Es solo mi primera suposición y no ha excluido las posibilidades en las que el río hace una curva sobre sí mismo y crea un juego no jugable. Cualquier ayuda sería muy apreciada, ¡gracias!

Answer 1

El problema principal consiste en contar los diferentes diseños autoevitantes que se pueden producir utilizando las cuatro fichas de la siguiente figura:

Un diseño admisible comienza con $A$, termina con $B$ y contiene $4$ fichas $L/R$. Podemos asumir que la primera ficha de este tipo es una $L$ (y multiplicar por $2$ al final). Hay $8$ palabras $L/R$ de longitud $4$ que comienzan con $L$, a saber $$LLLL, LLLR, LLRL, LLRR,LRLL, LRLR,LRRL,LRRRR\ .$$ Estas palabras deben ser decoradas con $A$, $B$ y seis letras $S$, donde ciertos $S$ son obligatorios. Entonces obtenemos los siguientes $8$ patrones, donde en los puntos los $S$ opcionales se pueden llenar: $$\eqalign{p_1:\quad&A\cdot LS\cdot LS\cdot LS\cdot L\cdot B \cr p_2:\quad&A\cdot LS\cdot LS\cdot L\cdot R\cdot B \cr p_3:\quad&A\cdot LS\cdot L\cdot R\cdot L\cdot B \cr p_4:\quad&A\cdot LS\cdot L\cdot RS\cdot R\cdot B \cr p_5:\quad&A\cdot L\cdot R\cdot LS\cdot L\cdot B \cr p_6:\quad&A\cdot L\cdot R\cdot L\cdot R\cdot B \cr p_7:\quad&A\cdot L\cdot RS\cdot R\cdot L\cdot B \cr p_8:\quad&A\cdot L\cdot RS\cdot RS\cdot R\cdot B \cr}$$ Estos $8$ patrones caen en tres tipos:

(i) El patrón $p_1$ contiene cuatro giros consecutivos iguales, y debe ser tratado utilizando un análisis de casos para asegurar que sea autoevitante.

(ii) Los dos patrones $p_2$ y $p_7$ contienen tres giros consecutivos iguales, y deben ser tratados utilizando un análisis de casos para asegurar que sean autoevitantes. (Nota que $p_7$ es equivalente a $p_2$.)

(iii) Los patrones restantes son autoevitantes sin importar cómo se llenen las letras opcionales $S$. El número de formas de hacer esto es un problema de estrellas y barras para cada $p_k$, dependiendo del número de letras obligatorias $S$ en $p_k$.

Supongamos que el número total $N$ de diseños autoevitantes ha sido determinado. Entonces debemos distribuir las fichas de imagen en estos diseños. El número $M$ de posibilidades es el mismo para todos los diseños. Considerando que las dos imágenes que aparecen dos veces son "secretamente" diferentes, dividimos por $2\cdot2$ al final. De esta manera obtenemos $$M={6!\> 2^6\>4!\over2\cdot2}=276\,480\ .$$

Answer 2

Estás empezando bien, pero no entiendo por qué utilizaste $2^8$ en lugar de $2^{10}$. Escribes “las $2$ piezas rectas no se incluyen porque no son únicas”, pero si son únicas no tiene nada que ver con contar sus $2$ orientaciones diferentes - ya has contabilizado correctamente el hecho de que no son únicas dividiendo por $2!$ dos veces.

Dejaré fuera el factor $2!^2$ hasta el final porque se aplica a todas las configuraciones y podemos aplicarlo una vez.

Quedan dos condiciones por tener en cuenta: no pueden haber intersecciones consigo mismo, y dos giros consecutivos deben ser en direcciones opuestas.

Empecemos con la segunda condición. Cada par de giros consecutivos reduce las opciones en un factor de $2$, por lo que necesitamos contar las configuraciones según el número de pares de giros consecutivos que contienen. Esto se puede hacer utilizando el principio de inclusión-exclusión.

Encontremos los números $a_k$ de formas en las que $k$ pares de giros pueden ser adyacentes (aún no contando las orientaciones).

$a_0$ es simplemente $10!=3628800$.

Para $a_1$, podemos elegir un par en $\binom42=6$ formas, ordenarlo en 2 maneras, y ordenar los $9$ elementos resultantes (un par, ocho piezas sin pareja) en $9!=362880$ formas, para un total de $a_1=4354560$.

Para $a_2$, hay dos opciones. Podemos elegir dos pares disjuntos en $3$ formas, ordenar cada uno de ellos en $2$ maneras para un factor de $2^2=4$, y ordenar los $8$ elementos resultantes (dos pares, seis piezas sin pareja) en $8!=40320$ maneras; o podemos elegir dos pares superpuestos para formar un triple consecutivo en $\binom43=4$ formas, ordenarlos en $3!=6$ maneras y ordenar los $8$ elementos resultantes (un triple, siete piezas sin pareja) en $8!=40320$ maneras, para un total de conteo de $a_2=(3\cdot4+4\cdot6)\cdot40320=1451520$.

Para $a_3$, no hay elección; tenemos que tener los $4$ giros seguidos. Podemos ordenarlos en $4!=24$ formas, y luego podemos ordenar los $7$ elementos resultantes (un cuádruple, seis piezas sin pareja), en $7!=5040$ formas, para un total de conteo de $a_3=120960$.

Luego, por inclusión-exclusión, el número $b_j$ de configuraciones que tienen exactamente $j$ pares de giros adyacentes es

$$ b_j=\sum_{k=j}^3(-1)^{j+k}\binom kja_k\;, $$

entonces

\begin{eqnarray*} b_0&=&a_0-a_1+a_2-a_3=3628800-4354560+1451520-120960=604800\;,\\ b_1&=&a_1-2a_2+3a_3=4354560-2\cdot1451520+3\cdot120960=1814400\;,\\ b_2&=&a_2-3a_3=1451520-3\cdot120960=1088640\;,\\ b_3&=&a_3=120960\;. \end{eqnarray*}

Cada par de giros adyacentes reduce las opciones en un factor de $2$, por lo que el número total de configuraciones (ahora contando las orientaciones) es

$$ \sum_{j=0}^32^{10-j}b_j=1024\cdot604800+512\cdot1814400+256\cdot1088640+128\cdot120960=1842462720\;. $$

Eso es un poco menos de la mitad (aproximadamente $49.6\%$) del conteo $2^{10}\cdot10!$ que obtendríamos sin tener en cuenta las restricciones de los giros.

Ahora necesitamos ocuparnos de las intersecciones consigo mismo. Esas solo pueden ocurrir si todos los giros son separados, ya que la cadena no puede intersectarse a sí misma una vez que colocamos dos giros adyacentes en direcciones opuestas. Así que tenemos al menos una pieza recta entre cada dos giros; y si también consideramos el inicio y el fin (lo cual debemos hacer para comprobar la autocintersección), tenemos al menos una pieza antes del primer giro y después del último giro. Por lo tanto, podemos describir la secuencia de giros y piezas rectas por una quíntupla $(v,w,x,y,z)$ de los números de piezas antes, entre y después de los giros, donde cada entrada es al menos $1$ y suman $8$.

Para que ocurra una autocintersección, los dos giros en el medio deben girar en la misma dirección. Cuál de los dos giros exteriores también debe girar en la misma dirección depende de la secuencia. (En este punto, sugeriría que te dibujes un diagrama. :-) Si el primer giro gira en la misma dirección que los giros interiores y $y\ge w$ y $v\gt x$, hay una intersección independientemente de la orientación del último giro. Del mismo modo, si el último giro gira en la misma dirección que los giros interiores y $w\ge y$ y $z\gt x$, hay una intersección independientemente de la orientación del primer giro. Además, si $w=y$ y todos los giros giran en la misma dirección, hay una intersección si $v+z\gt x$.

Así, para $(2,1,1,1,3)$ y su imagen en espejo hay tres opciones para los giros exteriores (todas excepto aquella en la que giran lejos el uno del otro); para $(2,1,2,1,2)$ hay una opción para los giros exteriores (aquella donde giran uno hacia el otro), y para todas las demás quintuplas con $y\ge w$ y $v\gt x$ o $w\ge y$ y $z\gt x$ hay dos opciones para los giros exteriores (uno debe girar hacia el otro y la orientación del otro es irrelevante). Este último caso comprende $(4,1,1,1,1)$, $(2,2,1,1,2)$, $(1,3,1,1,2)$, $(1,2,1,2,2)$, $(1,2,1,1,3)$, $(1,1,2,1,3)$, y sus imágenes en espejo. En total, son $2\cdot3+1\cdot1+2\cdot6\cdot2=31$ casos. Cada uno de estos puede tener $2$ orientaciones de los giros en el medio, $2^6=64$ orientaciones de las piezas rectas, $4!=24$ permutaciones de los giros y $6!=720$ permutaciones de las piezas rectas, para un total de $31\cdot2\cdot64\cdot24\cdot720=68567040$ configuraciones auto-intersectantes, una fracción pequeña del número total de configuraciones. Eso nos deja con

$$1842462720-68567040=1773895680$$

configuraciones admisibles, aún casi la mitad (aproximadamente $47.7\%$) del $2^{10}\cdot10!$ que obtendríamos sin restricciones.

Ahora, al final, podemos dividir por $2!^2=4$ para tener en cuenta el hecho de que dos giros y dos piezas rectas son intercambiables; el resultado es

$$ \frac{1773895680}4=443473920\;. $$

Aquí está el código Java que verifica este resultado enumerando las cadenas.