Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Existe latin square ortogonal a uma tabela aditiva de ordem n?

0 votos
27 visitas
perguntada Out 1 em Matemática por Arthur Quintão (1 ponto)  
editado Out 5 por Arthur Quintão

Seja \( L_{i,j} = (i+j) \)mod n para 0 ≤ i, j < n uma tabela aditiva de ordem n.
Prove que uma latin square ortogonal a L existe se, e somente se, n é ímpar.

KNUTH, Donald. E. The art of computer programming. volume 4A. página 36, exercício 12.

Compartilhe

1 Resposta

0 votos
respondida Out 2 por Arthur Quintão (1 ponto)  
editado Out 5 por Arthur Quintão





Antes de provarmos a equivalência, vamos buscar entender os principais conceitos necessários para a prova, logo entender o que está sendo pedido.

Definição (Latin square): A latin square de ordem n is um array (n × n) de n símbolos na qual cada cada símbolo ocorre uma única vez em cada linha e em cada coluna

Exemplo (latin square de ordem 4, com índices inteiros e símbolos):

A imagem será apresentada aqui.

Definição (Tabela aditiva): Uma tabela aditiva de ordem n é um array (nxn), tal que o elemento na linha i, coluna j corresponderá ao resto da divisão inteira entre i+j e n, ou seja, corresponderá a (i+j) mod n.

Exemplo (tabela aditiva de ordem 4):

A imagem será apresentada aqui.

Definição (Latin square ortogonal): Seja A = [\(a_{ij}\)] e B=[\(b_{ij}\)] latin squares de ordem n. Dizemos que A e B são ortogonais se {\( (a_{i,j},b_{ij}) | 0 \leq i,j \leq n-1\)}\(=[0,n-1] \times [0,n-1] \), onde \([0,n-1]\) denota o conjunto{\(0,1,2,..., n-1\)}.

Ou seja, se A e B são ortogonais, então o conjunto de pares ordenados definidos pelos elementos de A e B será igual as todas combinações dos elementos de A e B, dois a dois, de forma ordenada.

Exemplo:

A imagem será apresentada aqui.

Ao invés de pensarmos em pares ordenados, poderíamos pensar como a sobreposição dos elementos de arrays, tal que cada par ordenado ocorrerá uma única vez.

Teorema 1. Para \( 0 \leq i, i',j, j' \leq n-1\), onde \(i\neq i' e j\neq j'\), se \(a_{i,j} = a_{i',j'} \) então \(b_{i,j}\neq b_{i',j'}\), ou seja, um elemento arbitrário de A não poderá ser sobreposto com um único elemento de B em 2 posições distintas do novo array.
Proof. Basta notar que se \(a_{i,j} = a_{i',j'} \) e \(b_{i,j}=b_{i',j'}\) para \(i\neq i' e j\neq j'\), então existe um \((a_{i'',j''},b_{i'',j''})\), tal que \((a_{i'',j''},b_{i'',j''}) \in [0,n-1] \times [0,n-1] \) e \( (a_{i'',j''},b_{i'',j''})\notin \{(a_{i,j},b_{ij}) | 0 \leq i,j \leq n-1 \}\), onde \([0,n-1]\) denota o conjunto{\(0,1,2,..., n-1\)}.
Contradição com o fato de A e B serem ortogonais.

Definição (Transversal). A transversal de latin square é um conjunto de entradas na qual inclui exatamente uma entrada de cada linha , coluna e símbolo.

A imagem será apresentada aqui.

Teorema 2. Um latin square tem um ortogonal mate se tem uma decomposição em transversais disjuntos.
Proof. Do teorema 1, para A e B latin square ortogonais de ordem n , sabemos que para as n ocorrências de um elemento arbitrário em A, segue que os correspondentes em B serão todos distintos.

Pela definição de latin square, sabemos que ocorre uma única vez em cada linha e em cada coluna. Portanto, para um elemento arbitrário em A, segue que os correspondentes em B serão um transversal em B.

A imagem será apresentada aqui.

Da condição de ortogonalidade de A e B, isto é, dado que e \(n^2\) pares ordenados \((a_{ij} , b_{ij} )\) são distintos, então A e B podem ser decompostos em transversais disjuntos.
Definido os objetos, vamos tentar provar a proposição.
Dado que é uma equivalência, vamos dividir a prova em 2 partes: (\(\rightarrow\)) e (\(\leftarrow\)).

Proof.

(\(\leftarrow\)) Seja \(L_{i,j}=(i+j)\) mod n, tal que n é ímpar.
Queremos construir um latin square ortogonal a L, ou seja, queremos demonstrar que existe pelo menos um latin square ortogonal a L quando n é ímpar.
Seja \(A_{i,j}=L_{2i,j}=(2i+j)\) mod n.

Afirmação 1. A é um latin square.

Afirmação 1.1 As linhas de A são definidas como uma translação das linhas de L.
Queremos mostrar que as linhas de A são iguais as linhas de L, entretanto em ordens distintas.

Primeiramente, note no exemplo da tabela aditiva que cada uma das linhas da tabela segue uma ordenação fixa dos inteiros ( a cada linha, replicamos a linha anterior, empurrando cada um dos elementos para a próxima casa, tal que os elementos que ultrapassam o limite da tabela são realocados no início da linha, mantendo a ordem [ 0 1 2 3 ]). Esse padrão será observado para qualquer tabela aditiva de ordem n.

Nesse sentido, para provar a afirmação 1.1, basta provar que
{\( A_{i,0}| i \in \{0,1,..., n-1\} \) } ={\( 0,1,2,...,(n-1) \)},
ou seja, provar que a coluna 0 contenha todos os valores inteiros de 1 a (n-1), uma vez que o restante de cada uma das linhas seguirá a mesma regra da tabela L, isto é, teremos o resto da soma de mais 1 unidade a cada casa.

Note que, se para algum \( i \leq (n-1) \) temos que se \( 2i < n \), então \(2i\) (mod n) = 2i, ou seja, se o dobro de i continua menor do que n, então o resto será o próprio dobro de i. Nesse sentido, \( \forall i \in \{0,...(n-1)\} \) que satisfaz a condição anterior \(A_{i,j}\) é par.

E para os índices i tal que \(2i> n\)? Para tais índices \(A_{i,j}\) será ímpar.
De fato, podemos argumentar de forma indutiva.

Considere o elemento \(k=n-1\). Dado que n é ímpar, então k é par. Dado que o 2k = k+k, então 2k (mod n) = k-1, ou seja, a parte excedente a n será igual a k-1. Dado que k é par, então k-1 é ímpar, ou seja, 2k (mod n) é ímpar.
A imagem a seguir ilustra o argumento.

A imagem será apresentada aqui.

E para o índice i tal que \(2i=n\)? Tal índice não existirá, pois n é ímpar e \(2i\) é par.

Dado que \(\forall i \in \{0,1,2,3,...,(n-1)\}\): \(2i<2n\), então para \(2i \) (mod n) \(\neq\) \(2j\), para \(i\neq j\), seja \(2i\) e \(2j \) pares ou \(2i\) e \(2j \) ímpares.</p>

Portanto, {\( A_{i,0}| i \in \{0,1,..., n-1\} \) } ={\( 0,1,2,...,(n-1) \)}.

Logo, as linhas de A são definidas como uma translação das linhas de L.

Afirmação 1.2: As colunas de A são definidas como uma translação das colunas de L.
O argumento é equivalente ao das linhas.

Portanto, A é um latin square.

Afirmação 2: A é ortogonal a L.
Pela definição de ortogonalidade, sabemos que {\( (a_{i,j},l_{ij}) | 0 \leq i,j \leq n-1\)}\(=[0,n-1] \times [0,n-1] \), onde \([0,n-1]\) denota o conjunto{\(0,1,2,..., n-1\)}.

Nesse sentido, suponha por contradição que A e L não são ortogonais, ou seja, \(\exists (i_1,j_1), (i_2,j_2) \in \{0,...,(n-1)\}\times \{0,...,(n-1)\}\) tal que \( ( (i_1+j_1) mod n, (2i_1+j_1) mod n)=( (i_2+j_2) mod n ,(2i_2+j_2) mod n) \) e \(i_1\neq i_2\) e \(j_1 \neq j_2 \).

Dado que \(i_k +j_k < n\) e \( 2i_k + j_k < 2n\) para \(k=1,2\), então da suposição anterior:
\(i_1+j_1 =i_2 +j_2\) (1)
\(2i_1 +j_1 = 2i_2 + j_2\) (2)

Portanto, subtraindo (1) de (2):
\(i_1=i_2\)

Logo, \(j_1=j_2\), contradição com o fato de \(i_1\neq i_2\) e \(j_1 \neq j_2 \).

Portanto, A e L são ortogonais.

( \( \rightarrow\)) Nessa parte da prova utilizaremos um resultado provado por Euler.

Seja L a tabela aditiva de ordem n, tal que n é par.

Teorema 3 (Euler,1782). A tabela aditiva de \(Z_n\) não tem transversais quando n é par.

Da contrapositiva do teorema 2, isto é, se um latin square não pode ser decomposto em transversais disjuntos então não possui algum latin square ortogonal, concluímos que não existe um latin square ortogonal a tabela aditiva L.

Portanto, se existe uma latin square ortogonal a L, então n é ímpar.



...