Transversales de cuadrados latinos

Question

Según esta tesis , página $28$ el siguiente cuadrado latino tiene $3$ $0$ -s transversales: $$\begin{bmatrix}1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 4 & 2 & 1\\ 4 & 1 & 5 & 3 & 2\\5 & 3 & 2 & 1 & 4\end{bmatrix} \implies \begin{bmatrix}1 & & & &\\ & & & 5 & \\ & & 4 & & \\ & & & & 2\\ & 3\end{bmatrix}, \begin{bmatrix}& & & 4 &\\2 & & & &\\ & & & & 1 \\ & & 5 & &\\ & 3\end{bmatrix}, \begin{bmatrix}& & & &5\\& & 1 & &\\ & & & 2 &\\4 & & & &\\& 3\end{bmatrix}.$$ La definición de $0$ -s transversal para un cuadrado latino de orden $n$ es

un conjunto de $n$ triples ordenadas de tal manera que la primera y segunda entradas son las filas y columnas respectivamente en las que los valores $1,\ldots,n$ ocurren exactamente una vez y la tercera entrada de la triple es el valor, del que hay $n$ valores distintos.

Básicamente, tenemos que visitar cada fila y columna sólo una vez y debemos tener $5$ símbolos distintos al final. Puedo representar cada transversal como $$t_1 = \{(1,1,1),(2,4,5),(3,3,4),(4,5,2),(5,2,3)\}$$ $$t_2 = \{(1,4,4),(2,1,2),(3,5,1),(4,3,5),(5,2,3)\}$$ $$t_3 = \{(1,5,5),(2,3,1),(3,4,2),(4,1,4),(5,2,3)\}$$ Entonces, ¿por qué estos son los sólo ¿tres? ¿Cómo sé que sólo son tres?

Answer 1

No creo que haya ninguna forma astuta de determinar que este cuadrado latino tiene exactamente $3$ transversales sólo las contamos. Por ejemplo GAP código:

L:=[[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]];;

ExtendPartialTransversal:=function(T)
  local i,j,TNew;

  # we try to add entry (i,j,L[i][j]) to T without clashing  

  # looking at row i
  i:=Size(T)+1;

  # looking at column j
  for j in [1..5] do

    # column already used
    if(ForAny([1..i-1],k->T[k][2]=j)) then continue; fi;

    # symbol already used
    if(ForAny([1..i-1],k->T[k][3]=L[i][j])) then continue; fi;

    # add to partial transversal
    TNew:=Concatenation(T,[[i,j,L[i][j]]]);

    # if transversal complete, then print, otherwise extend
    if(Size(TNew)=5) then
      Print(TNew,"\n");
    else
      ExtendPartialTransversal(TNew);
    fi;

  od;
end;;

# start with the empty partial transversal
ExtendPartialTransversal([]);

que devuelve las tres transversales:

[ [ 1, 1, 1 ], [ 2, 4, 5 ], [ 3, 3, 4 ], [ 4, 5, 2 ], [ 5, 2, 3 ] ]
[ [ 1, 4, 4 ], [ 2, 1, 2 ], [ 3, 5, 1 ], [ 4, 3, 5 ], [ 5, 2, 3 ] ]
[ [ 1, 5, 5 ], [ 2, 3, 1 ], [ 3, 4, 2 ], [ 4, 1, 4 ], [ 5, 2, 3 ] ]

y demuestra que no hay otros mediante una búsqueda exhaustiva.

Answer 2

"Estoy trabajando con un cuadrado latino más grande (concretamente 10x10). En mi situación, ya conocemos la posición de algunas transversales. Quiero ver si, de todas las terminaciones que he encontrado, una de ellas podría descomponerse en transversales".

Si encuentras todas las transversales del cuadrado latino, entonces es fácil encontrar transversales disjuntas.

Ejemplo

Este cuadrado latino diagonal

0 2 4 7 8 9 5 6 3 1
5 1 9 6 3 2 4 8 0 7
6 7 2 9 1 0 8 3 5 4
9 4 0 3 5 7 2 1 6 8
7 0 3 8 4 6 9 2 1 5
2 8 6 0 7 5 1 4 9 3
1 5 8 4 2 3 6 9 7 0
4 3 5 1 9 8 0 7 2 6
3 9 1 5 6 4 7 0 8 2
8 6 7 2 0 1 3 5 4 9

tiene 104 diagonales transversales. Entre ellas hay 8 conjuntos de 10 transversales que no se intersecan, lo que da 8 cuadrados latinos diagonales ortogonales para un cuadrado latino diagonal dado.

#1
 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 1 0 5 2 7 3 9 4 6 8
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#2
 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 1 0 5 2 7 3 9 4 6 8
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#3
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 8 0 5 2 7 3 9 4 6 1
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#4
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 8 0 5 2 7 3 9 4 6 1
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#5
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 1 3 5 0 6 2 7 4 9 8
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#6
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 1 3 5 0 6 2 7 4 9 8
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3

#7
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 8 3 5 0 6 2 7 4 9 1
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#8
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 8 3 5 0 6 2 7 4 9 1
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3

introduzca aquí la descripción de la imagen

Answer 3

Un cuadrado latino se representa como $t_i=(r,c,s)$ lo que significa que r representa la fila del cuadrado latino, c representa la columna del cuadrado latino y s es el número cuya ubicación es $row=r\;\;and\;\;column=c$ .