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

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

+1 voto
70 visitas
perguntada Out 1, 2020 em Matemática por Arthur Quintão (11 pontos)  
editado Out 5, 2020 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

+1 voto
respondida Out 2, 2020 por Arthur Quintão (11 pontos)  
editado Out 5, 2020 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.



comentou Dez 15, 2020 por JOAO PAULO (26 pontos)  
Arthur, sua resposta (prova) está completa. Um ponto positivo foi que você mostrou as definições de propriedades utilizadas nos teoremas. Desse modo, não foi necessário buscar as definições em outras fontes. Deixo de sugestão alguns pontos para melhorar a compreensão da prova:
•    Quando se vai provar o enunciado do problema (depois das definições) seria interessante enunciar novamente o teorema.
•    Na afirmação 2 há alguns erros de digitação no mod de n.
No mais está bem explicado. Eu encontrei uma prova muito boa na internet, onde o autor também utiliza tabelas aditivas. No entanto, o teorema é ligeiramente diferente do enunciado na questão. O link dessa prova está em:  https://www.whitman.edu/mathematics/cgt_online/book/section04.03.html
Como um complemento da sua resposta adiciono abaixo um código que gera latins squares e gera combinações de latins squares. O algoritmo testa se as combinações desses latins squares são ortogonais entre si ou não.

Abraços.


from __future__ import print_function

def show_grid(g):
    for row in g:
        print(row)
    print()

def test_mols(g):
    ''' check that all entries in g are unique '''
    size = len(g) ** 2
    a = set()
    for row in g:
        a.update(row)
    return len(a) == size

def mols(n):
    ''' Generate a set of mutually orthogonal latin squares
        n must be prime
    '''
    r = range(n)

    #Generate each Latin square
    allgrids = []
    for k in range(1, n):
        grid = []
        for i in r:
            row = []
            for j in r:
                a = (k*i + j) % n
                row.append(a)
            grid.append(row)
        allgrids.append(grid)

    for g in allgrids:
        show_grid(g)

    print('- ' * 20 + '\n')

    #Combine the squares to show their orthoganility
    m = len(allgrids)
    for i in range(m):
        g0 = allgrids[i]
        for j in range(i+1, m):
            g1 = allgrids[j]
            newgrid = []
            for r0, r1 in zip(g0, g1):
                newgrid.append(list(zip(r0, r1)))
            print('A',test_mols(newgrid))
            show_grid(newgrid)

mols(5)
...