Digamos que quiero colocar 8 torres en un tablero de ajedrez de forma que ninguna de ellas se ataque entre sí. Trivialmente, sólo puede haber una torre por fila y columna, lo que implica que hay $8! = 40320$ soluciones en total.
Sin embargo, algunas de estas soluciones son idénticas, como en rotación, o reflexivamente simétricas, por lo que me preguntaba cuántas soluciones únicas existen, de tal manera que no se puede crear otra a partir de una.
Gracias.
Para resolver este problema podemos utilizar el lema de Burnsides.
el grupo de actuación es claramente $D_8$ . Contemos cuántos elementos están fijados por el $8$ simetrías.
La identidad fija claramente todos $8!$ simetrías
Las reflexiones horizontales y verticales claramente no fijan ninguna solución porque todas las órbitas están contenidas en una fila/columna.
Las rotaciones por $90$ grados tienen órbitas de $4$ cuadrados cada uno. Así que claramente una solución debe consistir exactamente en $2$ órbitas. Cada órbita puede describirse de la forma $(x,y)$ con $1\leq x,y \leq 4$ (porque cada órbita tiene exactamente $1$ elemento en la esquina inferior izquierda) y está claro que queremos que nuestras dos órbitas cubran todas $4$ números. Por lo tanto, hay $12$ diferentes soluciones de este tipo. ( existen $\binom{4}{2}$ formas de seleccionar el $x$ coordenadas y $2$ formas de emparejar las coordenadas restantes)
La rotación por $180$ grados divide el tablero en órbitas de $2$ cuadrados cada uno. Una solución puede representarse mediante $4$ elementos que están en el lado izquierdo del tablero. Estos $4$ deben cubrir los elementos $4$ Las columnas y las filas que ocupan deben ser distintas, también está prohibido tener dos filas ocupadas que estén en simetría con respecto a la línea horizontal de simetría. Por lo tanto, hay $4!2^4$ tales soluciones.
Finalmente trabajamos con las reflexiones diagonales, éstas están en biyección con el número de involuciones en $S_8$ que es $764$ (consulte los números de teléfono para más información)
En conclusión, el número de soluciones distintas es $\frac{8!+ 2(0)+2(12)+(4!2^4)+2(764)}{8}=5282$ como desee.
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.
