Latas en una estantería

Question

Se colocan 6 latas en una estantería en disposición circular. Después de ordenar y limpiar la cocina, las latas se colocan de nuevo en posiciones aleatorias alrededor de un círculo. ¿Cuál es la probabilidad de que ninguna de las latas esté en su posición inicial o en las adyacentes?

¿No es así? $(\frac{3}{6})^6$ ?

Answer 1

Si crees que es $(\frac{3}{6})^6$ porque supones que son eventos independientes... entonces estás haciendo una suposición errónea. Por ejemplo, si la primera lata se coloca en el lugar en el que estaba la segunda, entonces la probabilidad de que la segunda lata se coloque en un lugar distinto a su posición inicial o adyacente es $\frac{3}{5}$ en lugar de $\frac{3}{6}$

En general, la colocación de las latas afecta a la colocación de otras latas, haciendo que los resultados de estos eventos dependan unos de otros.

Answer 2

El problema combinatorio es (relativamente) demasiado complicado, y escribir algo de código es (realmente) demasiado sencillo, así que aquí está el código y la cuenta:

S = SymmetricGroup(6)
R = Zmod(6)
cansPermutations = \
    [ s for s in S 
      if not {R(0), R(1), R(-1)}.intersection( 
             {R(s(k)-1) - R(k-1) for k in [1..6]}) ]

(Esto es "todo el código").

Luego pedimos las variables.

sage: len(cansPermutations)
20
sage: cansPermutations
[(1,5,3)(2,6,4),
 (1,4)(2,5)(3,6),
 (1,3,5)(2,4,6),
 (1,5,2,4)(3,6),
 (1,3,6,4)(2,5),
 (1,4,6,3)(2,5),
 (1,5,2,4,6,3),
 (1,3)(2,5)(4,6),
 (1,3,5,2,6,4),
 (1,4)(2,6,3,5),
 (1,4,2,5)(3,6),
 (1,5)(2,4)(3,6),
 (1,3,6,4,2,5),
 (1,3,5)(2,6,4),
 (1,4,2,6,3,5),
 (1,4)(2,5,3,6),
 (1,5,3,6,2,4),
 (1,4,6,2,5,3),
 (1,5,3)(2,4,6),
 (1,4)(2,6)(3,5)]

Hay $20$ "buenas permutaciones".

---

La pregunta no aclara si es necesario calcular la probabilidad o sólo demostrar que no es $(3/6)^6$ . Aquí, calcularé explícitamente el conjunto de las permutaciones "buenas" de las latas. (Es decir, de las que mueven cada lata $k\in R=\Bbb Z/6$ a algún lugar que no esté entre $k$ y $k\pm 1$ .)

Obsérvese que cada permutación puede escribirse de forma única como un producto de ciclos disjuntos. Hacemos esto con cada una de las permutaciones buenas. Ningún elemento es fijo, por lo que las longitudes de los ciclos que aparecen son al menos $2$ . Sólo tenemos las siguientes posibilidades para dividir la longitud total $6$ en piezas $\ge 2$ : $$ \begin{aligned} 6 &= 2+2+2\\ &=2+4\\ &=3+3\\ &=6\ . \end{aligned} $$ Ahora contamos para cada división el número de las posibilidades de rellenar las plazas.

• Para el tipo $2+2+2$ buscamos permutaciones de la forma $(1a)(bc)(de)$ . Si mapeamos $1\to 3$ es decir $a=3$ , entonces para $5$ sólo tenemos la posibilidad $2$ y sólo hay un caso, $(13)(25)(46)$ . Simétricamente, si decidimos mapear $1\to 5$ entonces sólo hay una posibilidad para el $3$ obtenemos el único caso $(15)(36)(24)$ . Para $1\to 4$ tenemos después de alguna persecución de posibilidades sólo $(14)(25)(36)$ y $(14)(26)(35)$ . Así pues, tenemos $1+1+2=4$ casos de esta forma. Este problema combinatorio era sencillo.

• Para el caso $3+3$ todavía tenemos un recuento fácil. Una buena permutación de la forma $(1bc)(def)$ debe tener valores Impares para $b,c$ Si no, el $4$ es $b$ o $c$ . Pero los vecinos de $1,4$ cubren todos los posibles valores restantes, por lo que no hay un "buen lugar" para $c$ . Así que $1,b,c$ son los números $1,3,5$ en algún orden (para $3,5$ ), el resto $2,e,f$ son $2,4,6$ en algún orden (de $4,6$ ). Así pues, tenemos $2\times 2=4$ casos en esta forma. De nuevo un caso sencillo.

• El siguiente caso es $2+4$ . Sea $(ab)(cdef)$ ser una buena permutación, $a<b$ . Lo conjugamos cíclicamente, es decir, permutamos cíclicamente las letras hasta $a$ se convierte en $1$ . Para ello basta con estudiar las buenas permutaciones de la forma $(1B)(CDEF)$ y luego producir todos los conjugados de la misma, teniendo cuidado de no repetir soluciones. Como $B\ne 2$ El $2$ está entre $C,D,E,F$ y podemos asumir, y de hecho lo hacemos, que $C=2$ . También, $5$ está entre $D,E,F$ . La primera observación es que $B=4$ . Si no, podemos suponer (cambiando la orientación del círculo) $B=3$ entonces $2,D,E,F$ son $2,4,5,6$ en algún orden. Así que $5\to 2$ , pero entonces qué número va a $5$ sólo nos quedan los vecinos, la contradicción. Nuestra permutación es pues $(14)(2DEF)$ , y una rápida persecución valida sólo $(14)(2536)$ y sus inversos $(14)(2635)$ . Ahora volvemos a $(ab)(cdef)$ . Está claro que $(ab)$ puede ser sólo entre $(14)$ y/o $(25)$ y/o $(36)$ y en cada caso obtenemos dos soluciones. Por lo tanto, hay $3\times 2$ soluciones de esta forma.

• Queda por conseguir las buenas permutaciones de forma $6$ es decir, con un aspecto como el de $(1bcdef)$ . Tal vez la forma más sencilla de proceder sea fijar el posible lugar del $4$ . No puede ser $c$ (y simétricamente en el ciclo $e$ ) porque no tenemos una buena opción para la letra intermedia, $b$ (y respctivamente $f$ ). Podemos colocar así el $4$ en $b$ , obteniendo finalmente sólo los casos $(142635)$ y $(146253)$ los ciclos invertidos en el patrón $(1bcde4)$ y dos soluciones más para el patrón $(1bc4ef)$ que son $(152463)$ y su inversa $(136425)$ . Así que tenemos $2+2+2$ más soluciones.

Totalmente, hay $4+4+6+6=20$ soluciones.