39 votos

Sudokus como las tablas de composición de grupos finitos

Si $G$ es un grupo finito, a continuación, la tabla de composición de $G$ es un cuadrado latino (es decir, cada fila y columna contiene cada elemento del grupo de exactamente una vez).

Supongamos ahora que $|G| = n^2$ para algún número natural $n$. A continuación, podemos dividir la tabla de composición de $G$ en $n^2$ $n\times n$ plazas, y tenemos que preguntarnos si la tabla resultante es un sudoku resuelto (de tamaño $n^2\times n^2$ en lugar de la habitual de $9\times 9$).

Al hacer la tabla de composición de $G$, hay dos opciones a elegir. Uno es el orden de los elementos de las filas, y el otro es un orden de los elementos de las columnas. Mirando la fila y la columna correspondiente a la identidad, se puede ver que si tomamos el mismo orden en filas y columnas, a continuación, la tabla de composición no puede ser un sudoku (si etiquetamos a las entradas de la tabla de composición como $a_{i,j}$ y el de la fila/columna correspondiente a la identidad es de $k$ tenemos $a_{k-1,k} = a_{k,k-1}$ y $a_{k+1,k} = a_{k,k+1}$ y al menos uno de estos pares pertenecen a la misma $n\times n$ cuadrados).

Si $G$ es cíclico, entonces podemos hacer la tabla de composición de un sudoku de la siguiente manera: Escribir $G = \{0,1,\dots ,n^2 - 1\}$ (identificados con los números enteros mod $n^2$). Orden de las columnas en la forma natural (es decir, en orden creciente con los representantes elegidos), y el orden de las filas de bloques de $n$ que en cada bloque, la diferencia entre términos consecutivos es de $n$ (de manera que cada bloque se compone de aquellos elementos con un determinado residuo mod $n$ en orden creciente).

Para el no-grupo cíclico de orden $4$, también es posible (es fácil hacerlo por ensayo y error). Para el no-grupo cíclico de orden $9$, de nuevo es posible, pero se necesita un tiempo para encontrar algunas órdenes de trabajo. Los que trabajan son las siguientes: Dejar que el grupo generado por dos elementos $a$ y $b$ y el orden de las columnas como $1,ab,a^2b^2,a,b^2,^2b^2,ab^2,b$ y las filas como $1,a,b,ab,a^2 b^2,^2b,ab^2,^2b^2$.

Mi pregunta es: ¿Para qué grupos es posible encontrar la orden de las filas y columnas que a su vez de la composición de la mesa en un sudoku?

Edit: tenga en cuenta que si esto es posible para un grupo $G$, a continuación, cada uno de esos $n\times n$ plazas corresponden a un par de subconjuntos $A,B\subseteq G$, cada uno de tamaño $n$, tal que $AB = G$.

De hecho, es posible iff hay subconjuntos de $A_i$ y $B_i$ de $G$ todos de tamaño $n$ tal que $$G = \bigcup_{i=1}^n A_i = \bigcup_{i=1}^n B_i$$ y tal que para todo $i,j$ tenemos $A_iB_j = G$.

12voto

FuzzyQ Puntos 200

Un caso en el que un sudoku arreglo es posible es cuando $G$ tiene un subgrupo de $H$ de orden $n$. Deje de $Ha_1, Ha_2, \ldots Ha_n$ ser el derecho cosets de $H$ y dejar $T_1, T_2, \ldots, T_n$ ser una partición de $G$ en juegos completos de izquierda coset representantes. Es decir, de cada $T_i$ contiene exactamente un elemento de cada uno a la izquierda coset de $H$ y $T_i \cap T_j = \emptyset$ por $i \neq j$.

Orden de las columnas por el listado de todos los elementos de $Ha_1$ primero, entonces cada elemento de $Ha_2$ y así sucesivamente hasta $Ha_n$. Del mismo modo el orden de las filas por el listado de cada elemento de $T_1$ primero, $T_2$ y así sucesivamente hasta $T_n$. A continuación, cada uno $n \times n$ bloque contiene los elementos de un $Ha_i$ en las columnas y los elementos de unos $T_j$ en las filas. Resulta que este acuerdo nos da un sudoku de la tabla.

Debemos mostrar que cada elemento de $G$ se produce exactamente una vez en el bloque correspondiente a $Ha_i$ y $T_j$. Es decir, queremos demostrar que $T_jHa_i = G$, y esto se deduce del hecho de que no hay repeticiones en el bloque. Suponga que $s_k, s_{k_0} \en T_j$ y $h, h_0 \in H$. Si $s_kha_i = s_{k_0}h_0a_i$, entonces $s_kH = s_{k_0}H$ para $s_k = s_{k_0}$ desde $T_j$ contiene exactamente un representante para cada uno de izquierda coset. Mus $h = h_0$ así.

Me encontré con la idea de la construcción aquí, donde un poco más general del problema que se considera. Si $|G| = ab$ y $[G:H] = a$, entonces la misma construcción como en esta respuesta le da un sudoku tabla con bloques de tamaño $a \times b$.

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