Es un Sudoku una tabla de Cayley de un grupo?

Question

Quiero saber si estoy en el popular rompecabezas de Sudoku es una tabla de Cayley de un grupo.

Los métodos que yo he mirado: Alguien de los que he hablado me dijeron que no porque al contar el número de soluciones de rompecabezas contra el número de tablas con ciertas permutaciones de los elementos, filas y columnas, las soluciones son más grandes que las tablas, pero no puedo ver por qué, porque no sé cómo contar las diferentes tablas para un grupo de orden 9 y, a continuación, permutar las filas, columnas y elementos de diferentes maneras. También creo que las rotaciones/reflexiones le importa en la comparación de estas cifras. También sería agradable si había una manera de saber si la operación es asociativa sólo a partir de la tabla.

Answer 1

Una tabla de Cayley de un grupo no puede ser nunca un sudoku. Supongamos que usted tiene una $9 \times 9$ tabla de Cayley de un grupo de orden $9$, y decir que su identidad es el elemento en el índice de $1 \le i \le 9$. Luego de la fila $i$ y la columna $i$ son simétricas a cada uno de los otros, ya que se corresponden a la multiplicación con la identidad. En particular, si se mira el $3\times3$ sub-cuadrado que contiene el elemento de coordenadas $(i,i)$, esta plaza se ha duplicado (porque contiene simétrica de los elementos de la fila $i$ y la columna $i$). Por lo que la tabla no es un Sudoku.

Si usted permite intercambiar filas o columnas, esto es posible. Tomar la tabla de $G = \mathbb{Z}/9\mathbb{Z}$ (escribí $0$ en lugar de $9$ por conveniencia): $$ \begin{array}{r|lllllllll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 1&1&2&3&4&5&6&7&8&0\\ 2&2&3&4&5&6&7&8&0&1\\ 3&3&4&5&6&7&8&0&1&2\\ 4&4&5&6&7&8&0&1&2&3\\ 5&5&6&7&8&0&1&2&3&4\\ 6&6&7&8&0&1&2&3&4&5\\ 7&7&8&0&1&2&3&4&5&6\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

Y de intercambio de las filas en orden de $0,3,6,1,4,7,2,5,8$, para obtener el Sudoku

$$ \begin{array}{r|lll|lll|lll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 3&3&4&5&6&7&8&0&1&2\\ 6&6&7&8&0&1&2&3&4&5\\ \hline 1&1&2&3&4&5&6&7&8&0\\ 4&4&5&6&7&8&0&1&2&3\\ 7&7&8&0&1&2&3&4&5&6\\ \hline 2&2&3&4&5&6&7&8&0&1\\ 5&5&6&7&8&0&1&2&3&4\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

Answer 2

Es fácil construir un Sudoku que no puede ser una tabla de Cayley. No, incluso si la etiqueta de las filas y columnas de forma independiente el uno del otro. Considere el siguiente. $$ \begin{array}{ccc|ccc|ccc} 1&2&3&4&5&6&7&8&9\\ 4&5&6&7&8&9&1&3&2\\ 7&8&9&1&2&3&4&5&6\\ \hline 2&3&1&5&6&4&9&7&8\\ 5&6&4&8&9&7&2&1&3\\ 8&9&7&2&3&1&6&4&5\\ \hline 3&1&2&6&4&5&8&9&7\\ 6&4&5&9&7&8&3&2&1\\ 9&7&8&3&1&2&5&6&4 \end{array} $$ Mi argumento sólo necesita las dos primeras filas. El resto se rellena sólo para no dejar lugar a dudas sobre el hecho de que esas dos filas forman parte de un sistema completo de Sudoku.

Vemos que tenemos la segunda fila de la primera mediante la aplicación de la permutación $\sigma=(147)(258369)$ . Esto es todo lo que necesita para demostrar que esta no es una tabla de Cayley. Si en una tabla de Cayley la primera fila ha $a$ como el común de la izquierda factor y la segunda fila ha $b$ como el común de la izquierda factor, se obtiene la segunda fila de la primera multiplicando todo, desde la izquierda por $c:=ba^{-1}$. Si $n=\operatorname{ord}(c)$, la permutación $\sigma$ traer la primera fila a la segunda, a continuación, sólo tiene ciclos de longitud $n$ a un ciclo ley de transitivamente sobre un derecho coset $Hx$, $H=\langle c\rangle, x\in G$.

Pero nuestra $\sigma$ tipo de ciclo $(3,6)$. Esto ya nos da dos contradicciones:

• las longitudes de los ciclos varían, y
• $\sigma$ tiene orden de seis, por lo que no puede ser un elemento de un grupo de orden de nueve.

Answer 3

Otro enfoque: Estamos considerando un grupo de orden $9 = 3^2$, por lo que un primer cuadrado. Es bien sabido que los grupos de orden $p^2$ debe ser abelian. (abelian = conmutativa) Ahora una soduku nunca puede representar un grupo abelian, como nunca es simétrica. (Simétrica como en matrices, que significa simétrica wrt. la diagonal.)