Artigos

4.4: Quadrados latinos - Matemática


Definição: quadrado latino

UMA Quadrado latino de ordem (n ) é uma grade (n times n ) preenchida com (n ) símbolos de forma que cada símbolo apareça uma vez em cada linha e coluna.

Exemplo ( PageIndex {1} )

Aqui está um quadrado latino de ordem 4:

Normalmente usamos os inteiros (1 ldots n ) para os símbolos. Existem muitos, muitos quadrados latinos de ordem (n ), então vale a pena limitar o número concordando em não contar os quadrados latinos que são "realmente iguais" e diferentes. A maneira mais simples de fazer isso é considerar reduzido Quadrados latinos. Um quadrado latino reduzido é aquele em que a primeira linha é (1 ldots n ) (em ordem) e a primeira coluna é da mesma forma (1 ldots n ).

Exemplo ( PageIndex {2} )

Considere este quadrado latino:

4231
2413
1342
3124

A ordem das linhas e colunas não é muito importante para a ideia de um quadrado latino. Se reordenarmos as linhas e colunas, podemos considerar o resultado como sendo essencialmente o mesmo quadrado latino. Reordenando as colunas, podemos transformar o quadrado acima neste:

1234
3412
2341
4123

Então, podemos trocar as linhas dois e três:

1234
2341
3412
4123

Este quadrado latino está em forma reduzida e é essencialmente igual ao original.

Outra maneira simples de mudar a aparência de um quadrado latino sem mudar sua estrutura essencial é trocar os símbolos.

Exemplo ( PageIndex {3} )

Começando com o mesmo quadrado latino de antes:

4231
2413
1342
3124

podemos trocar os símbolos 1 e 4 para obter:

1234
2143
4312
3421

Agora, se trocarmos as linhas três e quatro, obteremos:

1234
2143
3421
4312

Observe que este quadrado latino está em forma reduzida, mas não é a mesma que a forma reduzida do exemplo anterior, embora tenhamos começado com o mesmo quadrado latino. Portanto, podemos considerar alguns quadrados latinos reduzidos iguais entre si.

Definição: classes isotópicas e isotópicas

Dois quadrados latinos são isotópico se cada um pode ser transformado no outro permutando as linhas, colunas e símbolos. Esta relação de isotopia é uma relação de equivalência; as classes de equivalência são isotopia Aulas.

Os quadrados latinos são aparentemente muito difíceis de contar sem um poder de computação substancial. O número de quadrados latinos é conhecido apenas até (n = 11 ). Aqui estão os primeiros valores para todos os quadrados latinos, quadrados latinos reduzidos e quadrados latinos não isotópicos (ou seja, o número de classes de isotopia):

(n )TudoReduzidoNão isotópico
1111
2211
31211
457642
5161280562

Como podemos produzir um quadrado latino? Se você sabe o que é um grupo, você deve saber que a tabuada de qualquer grupo finito é um quadrado latino. (Além disso, qualquer quadrado latino é a tabuada de uma quasigrupo.) Mesmo se você não encontrou grupos com esse nome, você pode saber de alguns. Por exemplo, considerando o módulo de inteiros (n ) sob adição, a tabela de adição é um quadrado latino.

Exemplo ( PageIndex {4} )

Exemplo 4.3.6 Aqui está a tabela de adição para o módulo 6 de inteiros:

012345
123450
234501
345012
450123
501234

Exemplo 4.3.7 Aqui está outra maneira de gerar potencialmente muitos quadrados latinos. Comece com a primeira linha (1, ldots, n ). Considere os conjuntos (A_i = [n] barra invertida {i } ). De exercício 1 na seção 4.1 sabemos que este sistema de conjuntos tem muitos sdrs; if (x_1, x_2, ldots, x_n ) é um sdr, podemos usá-lo para a linha dois. Em geral, depois de escolhermos as linhas (1, ldots, j ), deixamos (A_i ) ser o conjunto de inteiros que ainda não foram escolhidos para a coluna (i ). Este conjunto de sistema tem um sdr, que usamos para a linha (j + 1 ).

Definição 4.3.8 Suponha que (A ) e (B ) sejam dois quadrados latinos de ordem (n ), com entradas (A_ {i, j} ) e (B_ {i, j} ) na linha (i ) e coluna (j ). Forme a matriz (M ) com entradas (M_ {i, j} = (A_ {i, j}, B_ {i, j}) ); vamos denotar esta operação como (M = A xícara B ). Dizemos que (A ) e (B ) são ortogonal se (M ) contém todos os (n ^ 2 ) pares ordenados ((a, b) ), (1 le a le n ), (1 le b le n ) , isto é, todos os elementos de ( {0,1, ldots, n-1 } times {0,1, ldots, n-1 } ).

Como veremos, é fácil encontrar quadrados latinos ortogonais de ordem (n ) se (n ) for ímpar; não é muito difícil encontrar quadrados latinos ortogonais de ordem (4k ), e difícil, mas é possível encontrar quadrados latinos ortogonais de ordem (4k + 2 ), com exceção das ordens (2 ) e (6 ) No século XVIII, Euler mostrou que existem quadrados latinos ortogonais de todas as ordens, exceto da ordem (4k + 2 ) e conjeturou que não existem quadrados latinos ortogonais de ordem (6 ). Em 1901, o matemático amador Gaston Tarry mostrou que de fato não há nenhuma ordem (6 ), mostrando que todas as possibilidades para tais quadrados latinos falharam em ser ortogonais. Em 1959, foi finalmente mostrado que existem quadrados latinos ortogonais de todas as outras ordens.

Teorema 4.3.9

Existem pares de quadrados latinos ortogonais de ordem (n ) quando (n ) é ímpar.

Prova

Esta prova pode ser resumida usando idéias da teoria dos grupos, mas apresentaremos uma versão independente. Considere a tabela de adição para o mod de adição (n ):

0 ( cdots ) (j ) ( cdots ) (n-1 )
00 ( cdots ) (j ) ( cdots ) (n-1 )
( vdots )
(eu)(eu) ( cdots ) (i + j ) ( cdots ) (n + i-1 )
( vdots )
(n-1 ) (n-1 ) ( cdots ) (n + j-1 ) ( cdots ) (n-2 )

Afirmamos primeiro que este (sem a primeira linha e coluna, é claro) é um quadrado latino com símbolos (0,1, ldots, n-1 ). Considere duas entradas na linha (i ), digamos (i + j ) e (i + k ). Se (i + j equiv i + j pmod {n} ), então (j equiv k ), então (j = k ). Assim, todas as entradas da linha (i ) são distintas, então cada um dos (0,1, ldots, n-1 ) aparece exatamente uma vez na linha (i ). A prova de que cada um aparece uma vez em qualquer coluna é semelhante. Chame isso de quadrado latino (A ). (Observe que até agora tudo é verdade, seja (n ) ímpar ou par.)

Agora forme um novo quadrado (B ) com entradas (B_ {i, j} = A_ {2i, j} = 2i + j ), onde por (2i ) e (2i + j ) nós significa esses valores mod (n ). Assim, a linha (i ) de (B ) é igual à linha (2i ) de (A ). Agora, afirmamos que de fato as linhas de (B ) são exatamente as linhas de (A ), em uma ordem diferente. Para fazer isso, basta mostrar que se (2i equiv 2k pmod {n} ), então (i = k ). Isso implica que todas as linhas de (B ) são distintas e, portanto, devem ser todas as linhas de (A ).

Suponha, sem perda de generalidade, que (i ge k ). Se (2i equiv 2k pmod {n} ) então (n divide 2 (i-k) ). Como (n ) é ímpar, (n divide (i-k) ). Uma vez que (i ) e (k ) estão em (0,1, ldots, n-1 ), (0 le i-k le n-1 ). Destes valores, apenas (0 ) é divisível por (n ), então (i-k = 0 ). Assim, (B ) também é um quadrado latino.

Para mostrar que (A cup B ) contém todos os elementos (n ^ 2 ) de ( {0,1, ldots, n-1 } times {0,1, ldots, n -1 } ), é suficiente mostrar que não há dois elementos de (A cup B ) iguais. Suponha que ((i_1 + j_1,2i_1 + j_1) = (i_2 + j_2,2i_2 + j_2) ) (a aritmética é mod (n )). Então, subtraindo as equações, (i_1 = i_2 ); com a primeira equação, isso implica (j_1 = j_2 ).

(quadrado)

Exemplo 4.3.10 Quando (n = 3 ), $$ left [ matrix {0 & 1 & 2 cr 1 & 2 & 0 cr 2 & 0 & 1 cr} right] cup left [ matrix {0 & 1 & 2 cr 2 & 0 & 1 cr 1 & 2 & 0 cr} right] = left [ matrix {(0,0) & (1,1) & (2,2) cr (1,2) & (2,0) & (0,1) cr (2,1) & (0,2) & (1,0) cr} right]. $$

Uma abordagem óbvia para construir quadrados latinos, e pares de quadrados latinos ortogonais, é começar com quadrados latinos menores e usá-los para produzir quadrados maiores. Iremos produzir um quadrado latino de ordem (mn ) a partir de um quadrado latino de ordem (m ) e um de ordem (n ).

Seja (A ) um quadrado latino de ordem (m ) com símbolos (1, ldots, m ) e (B ) um quadrado de ordem (n ) com símbolos (1, ldots, n ). Sejam (c_ {i, j} ), (1 le i le m ), (1 le j le n ), ser (mn ) novos símbolos. Forme uma grade (mn times mn ) substituindo cada entrada de (B ) por uma cópia de (A ). Em seguida, substitua cada entrada (i ) nesta cópia de (A ) por (c_ {i, j} ), onde (j ) é a entrada de (B ) que foi substituída. Denotamos este novo quadrado latino (A vezes B ). Aqui está um exemplo, combinando um quadrado latino (4 vezes 4 ) com um quadrado latino (3 vezes 3 ) para formar um quadrado latino (12 vezes 12 ):}

(1)(2)(3)(4)
(2)(3)(4)(1)
(3)(4)(1)(2)
(4)(1)(2)(3)
( times )
(1)(2)(3)
(2)(3)(1)
(3)(1)(2)
(=)
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )

Teorema 4.3.11

f (A ) e (B ) são quadrados latinos, assim como (A vezes B ).

Prova

Considere dois símbolos (c_ {i, j} ) e (c_ {k, l} ) na mesma linha. Se as posições contendo esses símbolos estão na mesma cópia de (A ), então (i not = k ), uma vez que (A ) é um quadrado latino, e assim os símbolos (c_ {i, j} ) e (c_ {k, l} ) são distintos. Caso contrário, (j not = l ), uma vez que (B ) é um quadrado latino. O argumento é o mesmo para colunas.

(quadrado)

Notavelmente, esta operação preserva ortogonalidade:

Teorema 4.3.12

Se (A_1 ) e (A_2 ) são quadrados latinos de ordem (m ), (B_1 ) e (B_2 ) são quadrados latinos de ordem (n ), (A_1 ) e (A_2 ) são ortogonais, e (B_1 ) e (B_2 ) são ortogonais, então (A_1 vezes B_1 ) é ortogonal a (A_1 vezes B_2 ).

Prova

Denotamos o conteúdo de (A_i times B_i ) por (C_i (w, x, y, z) ), significando a entrada na linha (w ) e coluna (x ) da cópia de (A_i ) que substituiu a entrada na linha (y ) e coluna (z ) de (B_i ), que denotamos (B_i (y, z) ). Usamos (A_i (w, x) ) para denotar a entrada na linha (w ) e coluna (x ) de (A_i ).

Suponha que ((C_1 (w, x, y, z), C_2 (w, x, y, z)) = (C_1 (w ', x', y ', z'), C_2 (w ', x ', y', z ')) ), onde ((w, x, y, z) não = (w', x ', y', z ') ). Ou ((w, x) not = (w ', x') ) ou ((y, z) not = (y ', z') ). Se for o último, então ((B_1 (y, z), B_2 (y, z)) = (B_1 (y ', z'), B_2 (y ', z')) ), uma contradição, uma vez que (B_1 ) é ortogonal a (B_2 ). Portanto, ((y, z) = (y ', z') ) e ((w, x) não = (w ', x') ). Mas isso implica que ((A_1 (w, x), A_2 (w, x)) = (A_1 (w ', x'), A_2 (w ', x')) ), uma contradição. Portanto, (A_1 vezes B_1 ) é ortogonal a (A_1 vezes B_2 ).

(quadrado)

Queremos construir quadrados latinos ortogonais de ordem (4k ). Escreva (4k = 2 ^ m cdot n ), onde (n ) é ímpar e (m ge 2 ). Sabemos que existem quadrados latinos ortogonais de ordem (n ), por teorema 4.3.9. Se houver quadrados latinos ortogonais de ordem (2 ^ m ), então por teorema 4.3.12 podemos construir quadrados latinos ortogonais de ordem (4k = 2 ^ m cdot n ).

Para obter um quadrado latino de ordem (2 ^ m ), também usamos o teorema 4.3.12. Basta encontrar dois quadrados latinos ortogonais de ordem (4 = 2 ^ 2 ) e dois de ordem (8 = 2 ^ 3 ). Em seguida, aplicação repetida do teorema 4.3.12 nos permite construir quadrados latinos ortogonais de ordem (2 ^ m ), (m ge 2 ).

Dois quadrados latinos ortogonais de ordem 4:

$$ left [ matrix {1 & 2 & 3 & 4 cr 2 & 1 & 4 & 3 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr} right] left [ matrix {1 & 2 & 3 & 4 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr 2 & 1 & 4 & 3 cr} right], $$

e dois da ordem 8:

$$ esquerda [ matriz {1 & 3 & 4 & 5 & 6 & 7 & 8 & 2 cr 5 & 2 & 7 & 1 & 8 & 4 & 6 & 3 cr 6 & 4 & 3 & 8 & 1 & 2 & 5 & 7 cr 7 & 8 & 5 & 4 & 2 & 1 & 3 & 6 cr 8 & 7 & 2 & 6 & 5 & 3 & 1 & 4 cr 2 & 5 & 8 & 3 & 7 & 6 & 4 & 1 cr 3 & 1 & 6 & 2 & 4 & 8 & 7 & 5 cr 4 & 6 & 1 & 7 & 3 & 5 & 2 & 8 cr} direita] esquerda [ matriz {1 & 4 & 5 & 6 & 7 & 8 & 2 & 3 cr 8 & 2 & 6 & 5 & 3 & 1 & 4 & 7 cr 2 & 8 & 3 & 7 & 6 & 4 & 1 & 5 cr 3 & 6 & 2 & 4 & 8 & 7 & 5 & 1 cr 4 & 1 & 7 & 3 & 5 & 2 & 8 & 6 cr 5 & 7 & 1 & 8 & 4 & 6 & 3 & 2 cr 6 & 3 & 8 & 1 & 2 & 5 & 7 & 4 cr 7 & 5 & 4 & 2 & 1 & 3 & 6 & 8 cr} right]. $$


Os 4x4 quadrados latinos e padrões alfabéticos

O tapete mágico 4x4 fundamental pode ser representado por pontos e espaços. Qualquer linha em qualquer direção de comprimento quatro contém dois pontos, ou seja, soma 2, qualquer área 4x4 selecionada é um padrão pan-magic. Podemos pegar quatro amostras deste grande tapete, girar duas delas e fazer as únicas quatro possíveis ordenar quatro tapetes mágicos.

Substituição alfabética.

Por se parecerem um pouco com as letras do alfabeto, recebem uma letra para identificá-los.

O Tapete Mágico Alfabético Composto

O ponto em cada um dos quadrados acima é substituído por sua própria letra. Os quatro quadrados são então combinados para formar o quadrado composto à esquerda e o tapete maior à direita.

Existe apenas um padrão composto. Este quadrado composto é a base de todos os quadrados mágicos da ordem 4. Qualquer área 4x4 contém cada letra duas vezes em cada linha, cada linha e cada diagonal. Para fazer um quadrado mágico 4x4 real, as letras neste quadrado seriam substituídas, respectivamente, por 8, 4, 2 e 1 (consulte a Página 4x4 Principal).

Padrão limpo.

Quando o padrão se repete, surge um grande tapete mágico - agradável e simétrico - que torna o padrão colorido interessante à esquerda.

Não é um quadrado latino

A rigor, não se trata de um "Quadrado Latino". Um quadrado latino para a ordem N usa N letras N vezes e cada linha e cada coluna contém uma de cada letra. O quadrado acima pode ser convertido em dois quadrados latinos.

Dois quadrados latinos 4x4

A ilustração abaixo combina dois quadrados latinos 4x4 em um único, chamado quadrado greco-latino. Por conveniência, ele emprega letras romanas maiúsculas e minúsculas em vez de caracteres romanos e gregos. As letras no novo quadrado são derivadas do quadrado acima:

A quando nem S nem N estão presentes
B quando N está presente
C quando S está presente
D quando S e N estão presentes
a quando nem C nem A estão presentes
b quando C está presente
c quando A está presente
d quando C e A estão presentes

UMA B C D
C D UMA B
B UMA D C
D C B UMA
+
uma d c b
d uma b c
b c d uma
c b uma d
=
Aa Bd Cc Db
CD Da Ab Bc
Bb Ac Dd Ca
Dc Cb BA de Anúncios

Não Pan-Magic.

A inspeção do greco-latim resultante mostra que as linhas e colunas são inevitavelmente "mágicas" - elas contêm uma de cada letra. Isso, no entanto, não é verdade para qualquer uma das diagonais, elas podem apenas somar a soma mágica para substituições numéricas selecionadas apropriadamente.

Valor limitado para quadrados latinos 4x4.

Por causa dessa limitação, os quadrados latinos têm uso limitado na construção de quadrados pan-mágicos 4x4. Existem dois outros quadrados alfabéticos 4x4 possíveis e todos os três são mostrados abaixo. A terceira nem é latina porque, agora, apenas as diagonais contêm uma de cada letra.


Versões alternativas de ortogonalidade

(f) Quadrados latinos parciais mutuamente ortogonais

Dois quadrados latinos parciais (não necessariamente distintos) são ortogonal se, quando eles são justapostos, nenhum par ordenado de elementos aparece mais de uma vez. Uma coleção de quadrados latinos parciais é chamada compatível com r se cada um tem r células ocupadas e essas células ocupadas estão em posições correspondentes.

Segue-se que, em particular, um quadrado latino parcial de ordem n que tem apenas n de suas células ocupadas é ortogonal a e n-compatível consigo mesmo. Assim, a maior parte do interesse é parcial n × n quadrados latinos que têm mais de n células preenchidas. Este conceito, que se deve a Abdel-Ghaffar (1996), surgiu em conexão com a teoria da codificação: ou seja, na minimização do tempo de recuperação de itens pertencentes a um grande arquivo de dados armazenados em vários discos.

Deixar Mn(r) denotam o número máximo de pares ortogonais r- quadrados latinos parciais compatíveis. Para a aplicação acima, Abdel-Ghaffar estava interessado em encontrar limites para Mn(r) quando r & gt n. Ele mostrou isso, por n + 1 ≤ rn 2 ,

Observe que este resultado implica em particular que Mn(n 2 ) ≤ n - 1. Abdel-Ghaffar mostrou ainda que, para n +1 ≤ r ≤ 2n, Mn(r) = ⌊r(r − 1)/2(rn) ⌋ - 2 e ele construiu quadrados que atendem ao último limite.

Na aplicação da teoria da codificação mencionada anteriormente, os limites acima Mn(r) fornecem limites no melhor tempo de recuperação possível.


4.4: Quadrados latinos - Matemática

Como um lembrete, devemos mencionar aqui que o pedido de um quadrado mágico é o número de células em um de seus lados.

Lembre-se de que o primeiro quadrado mágico de quarta ordem registrado parece ter sido encontrado em uma inscrição em Khajuraho, Índia, datada de cerca de 1000-1100 d.C.

Examinaremos um método para criar um quadrado mágico 44; no entanto, esse método não gera o quadrado encontrado na Índia. (Esta não é a única maneira, mas é rápida e segura.) Começamos criando uma matriz quadrada de 44 e depois desenhamos duas linhas diagonais para obter a figura a seguir.


Em seguida, começamos no canto superior esquerdo para colocar o número 1,2,3. 14,15,16 nas células. No entanto, não colocamos um número em qualquer célula onde a linha diagonal apareça. Começamos com 1, mas essa célula tem uma linha diagonal nela, então vamos para a próxima célula que está em branco e inserimos um 2, então colocamos um 3 na próxima célula. A última célula da primeira linha tem uma linha diagonal, então não escrevemos na 4. Vamos para a próxima linha e inserimos 5 na primeira célula, que está em branco, as próximas duas células têm uma linha diagonal, então nós pule 6 e 7. Continuamos esse padrão até chegarmos à última célula da última linha. Nosso quadrado ficará assim:

Agora começamos no canto inferior direito e voltamos usando os números 1,4,6,7,10,11,13 e 16. Colocamos esses números nas células que originalmente tinham as linhas diagonais começando com 1 no canto inferior direito. Nosso produto acabado tem a seguinte aparência:

Vemos que em nosso quadrado acabado cada linha, coluna e diagonal somam o número mágico 34, que é encontrado, como mencionamos acima, calculando 4 (4 2 + 1) / 2.

Assim que tivermos este quadrado, podemos cuidadosamente reorganize as linhas e colunas para obter outros 44 quadrados mágicos. Abaixo estão alguns rearranjos de nosso quadrado mágico 44 original.

Observe no rearranjo que os números em nosso quadrado mágico original 44 permanecem juntos. Ou seja, os números 16,2,3,13 que aparecem na primeira linha estarão sempre juntos, em alguma ordem, em uma linha ou coluna de um novo quadrado. Isso é verdade para todos os outros conjuntos de quatro números. Por exemplo, se você tem uma linha ou coluna que contém os números 3 e 6, essa linha ou coluna também deve ter os números 10 e 15.

Em nossos exemplos reorganizados acima, o último quadrado mágico é de interesse histórico particular em matemática e arte. Este quadrado mágico aparece no fundo da gravura Melencolia por Albrecht D & uumlrer, o que ele fez em 1514. Observe que os números 15 e 14 (a data da gravura) aparecem juntos no centro da linha inferior. Esta gravura pode ser vista em muitos lugares. Um conveniente é o WebMuseum. Se esse link não levar você até lá, tente a porta da frente. O principal ponto de entrada para o WebMuseum é o Pyramide.


Exercícios 4.3

Ex 4.3.1 Mostre que há apenas um quadrado latino reduzido de ordem 3.

Ex 4.3.2 Verifique se a relação de isotopia é uma relação de equivalência.

Ex 4.3.3 Encontre todos os 4 quadrados latinos reduzidos de ordem 4. Mostre que existem no máximo 2 classes de isotopia para a ordem 4.

Ex 4.3.4 Mostre que o segundo sistema definido no exemplo 4.3.7 tem um sdr conforme reivindicado.

Ex 4.3.5 Mostre que não há quadrados latinos ortogonais de ordem 2.

Ex 4.3.6 Encontre os dois quadrados latinos ortogonais da ordem $ 5 $ conforme descrito no teorema 4.3.9. Mostre sua resposta como no exemplo 4.3.10.

Ex 4.3.7 Prove que para construir quadrados latinos ortogonais de ordem $ 2 ^ m $, $ m ge2 $, basta encontrar dois quadrados latinos ortogonais de ordem $ 4 = 2 ^ 2 $ e dois de ordem $ 8 = 2 ^ 3 $.

Ex 4.3.8 Um quadrado latino $ n times n $ $ A $ é simétrico se for simétrico em torno da diagonal principal, ou seja, $ A_= A_$ para todos os $ i $ e $ j $. É fácil encontrar quadrados latinos simétricos: cada módulo de tabela de adição $ n $ é um exemplo, como no exemplo 4.3.6. Um quadrado latino é idempotente se todos os símbolos aparecerem na diagonal principal. Mostre que se $ A $ é simétrico e idempotente, então $ n $ é ímpar. Encontre um quadrado latino simétrico e idempotente $ 5 vezes 5 $.

Ex 4.3.9 O transpor $ A ^ top $ de um quadrado latino $ A $ é o reflexo de $ A $ na diagonal principal, de modo que $ A_^ top = A_$. Um quadrado latino é auto-ortogonal se $ A $ for ortogonal a $ A ^ top $. Mostre que não existe um quadrado latino auto-ortogonal de ordem 3. Encontre um de ordem 4.


Pesquisadores em teoria de projeto combinatório e áreas da estatística, como projeto e análise de experimentos. O livro também pode ser do interesse de matemáticos amadores interessados ​​em quadrados mágicos, em projetos de torneios de jogos e / ou em quadrados latinos relacionados a quebra-cabeças de Sudoku

Capítulo 1: Propriedades elementares

  • 1.1 A tabuada de um quase-grupo
  • 1.2 A mesa Cayley de um grupo
  • 1.3 Isotopia
  • 1.4 Conjugação e parastrofia
  • 1.5 Transversais e mapeamentos completos
  • 1.6 subquasigrupos e subquasigrupos latinos

Capítulo 2: Tipos especiais de quadrado latino

  • 2.1 Identidades de quasigrupo e quadrados latinos
  • 2.2 Quasigrupos de alguns tipos especiais e o conceito de associatividade generalizada
  • 2.3 Sistemas triplos e quase-grupos
  • 2.4 Quadrados latinos baseados em grupo e núcleos de loops
  • 2.5 Transversais em quadrados latinos baseados em grupo
  • 2.6 Quadrados latinos completos

Capítulo 3: Quadrados latinos parciais e transversais parciais

  • 3.1 retângulos latinos e quadrados latinos de linha
  • 3.2 Conjuntos críticos e quebra-cabeças Sudoku
  • 3.3 Problemas de Fuchs
  • 3.4 Quadrados latinos incompletos e quase-grupos parciais
  • 3.5 Transversais parciais e transversais generalizadas

Capítulo 4: Classificação e enumeração de quadrados latinos e retângulos latinos

  • 4.1 O grupo de autotopismo de um quase-grupo
  • 4.2 Classificação dos quadrados latinos
  • 4.3 História da classificação e enumeração dos quadrados latinos
  • 4.4 Enumeração de retângulos latinos
  • 4.5 Enumeração de transversais
  • 4.6 Enumeração de subquares

Capítulo 5: O conceito de ortogonalidade

  • 5.1 Questões de existência para conjuntos incompletos de quadrados latinos ortogonais
  • 5.2 Conjuntos completos de quadrados latinos ortogonais e planos projetivos
  • 5.3 Conjuntos de MOLS de tamanho máximo e mínimo
  • 5.4 quasigrupos ortogonais, grupóides e sistemas triplos
  • 5.5 Quadrados latinos auto-ortogonais e outros parastróficos ortogonais latinos e quase-grupos
  • 5.6 Ortogonalidade em outras estruturas relacionadas aos quadrados latinos

Capítulo 6: Conexões entre quadrados latinos e quadrados mágicos

  • 6.1 Quadrados latinos diagonais (ou mágicos)
  • 6.2 Construção de quadrados mágicos com auxílio de quadrados latinos ortogonais
  • 6.3 Resultados adicionais em quadrados mágicos
  • 6.4 Quadrados de salas: sua construção e usos

Capítulo 7: Construções de quadrados latinos ortogonais que envolvem o rearranjo de linhas e colunas


Seção do Caso 3

Nesse caso, temos níveis diferentes de fatores de linha e coluna. Novamente, em nosso cenário de fábrica, teríamos máquinas diferentes e diferentes operadores nas três réplicas. Em outras palavras, esses dois fatores seriam aninhados nas réplicas do experimento.

Escreveríamos este modelo como:

Aqui, usamos termos aninhados para ambos os fatores de bloco, representando o fato de que os níveis desses fatores não são os mesmos em cada uma das réplicas.

A tabela de análise de variância incluiria:


Tudo menos quadrado: de quadrados mágicos a Sudoku

Existe uma antiga lenda chinesa que é mais ou menos assim. Há cerca de três mil anos, uma grande enchente aconteceu na China. A fim de acalmar o contrariado deus do rio, o povo fez uma oferenda ao rio Lo, mas ele não pôde ser apaziguado. Cada vez que eles faziam uma oferenda, uma tartaruga aparecia do rio. Um dia, um menino percebeu marcas nas costas da tartaruga que pareciam representar os & # 13 números de 1 a 9. Os números foram arranjados de forma que cada linha somasse 15. Portanto, as pessoas entenderam que sua oferta não era o quantidade certa.

As marcas nas costas da tartaruga eram na verdade um quadrado mágico. Um quadrado mágico é uma grade quadrada preenchida com números, de forma que cada linha, cada coluna e as duas diagonais somam o mesmo número. Esta é a aparência do quadrado mágico do Lo Shu. Ele tem três linhas e três colunas, e se você somar os números em qualquer linha, coluna ou diagonal, sempre obterá & # 13 15.

Aqui está uma construção parcial de um quadrado mágico 5 por 5. Começando do 1, preenchi os números até 10. Não há espaço a nordeste do 1, então coloquei o 2 na linha inferior, seguido pelo 3. Novamente, porque o 3 está na borda, o 4 vai para o lado oposto. O 6 deve ir para a cela onde está o 1, mas como essa cela está ocupada, coloquei o 6 imediatamente abaixo do 5 e o # 13 e continuei até 10. Tente completar o quadrado e depois fazer o seu próprio.

Enquanto isso, conhecido como o Método siamês, é provavelmente o método mais conhecido para fazer quadrados mágicos; existem outros métodos. O mestre-escola alemão Johann Faulhaber publicou um método semelhante ao método siamês antes de ser descoberto por De Le Loubere. Outra forma é o Método Lozenge por John & # 13 Horton Conway, um prolífico matemático britânico. Provar que esses métodos funcionam pode ser feito usando álgebra, mas não é fácil!

Quadrados mágicos de ordem uniforme

Embora o método siamês possa ser usado para gerar um quadrado mágico para qualquer número ímpar, não existe um método simples que funcione para todos os quadrados mágicos de ordem par. Felizmente, existe um bom método que podemos usar se a ordem do quadrado for um número par divisível por 4. (Para aqueles que estão interessados, o Método LUX foi inventado por J. H. Conway para lidar com números pares que não são & # 13 divisíveis por 4).

Em vez de dizer "números que são divisíveis por 4", os matemáticos costumam dizer "números da forma 4k". Por exemplo, 12 é da forma 4k, porque você pode substituir k com 3. Usando a mesma ideia, os números que dão um resto de 2 quando você os divide por 4 podem ser chamados de números da forma 4k + 2.

Portanto, comece escolhendo a ordem do quadrado, certificando-se de que está no formato 4k, e numere as células 1 para (4k) 2 começando no canto superior esquerdo e trabalhando ao longo das linhas. Em seguida, divida o quadrado em 4 por 4 subquadrados e marque os números que se encontram nas diagonais principais de cada subquadrado. No exemplo, esses são os números coloridos e a ordem do quadrado é & # 13 4, então o único subquadrado 4 por 4 é o próprio quadrado.

Agora troque o menor número marcado pelo maior número marcado, o segundo menor número marcado pelo segundo maior número marcado e assim por diante. Outra maneira de dizer isso é que se o quadrado mágico tem ordem n, troque os números que somam n 2 + 1. Neste exemplo específico, a ordem é 4, então temos que trocar os números que somam 17: 1 e 16, 4 e 13, & # 13 6 e 11, 7 e 10.

Se você virar este quadrado mágico, ele é idêntico ao desenhado pelo famoso artista alemão Albrecht Dürer. Você pode ver no canto de sua gravura Melencolia.

A Knight's Tale

Como qualquer jogador de xadrez saberá, um quadrado mágico de ordem 8 tem o mesmo número de células que um tabuleiro de xadrez. Essa semelhança significa que podemos criar um tipo especial de quadrado mágico baseado nos movimentos de uma peça de xadrez.

O cavalo é uma peça interessante porque, ao contrário das outras peças, não se move verticalmente, horizontalmente ou diagonalmente ao longo de uma linha reta. Em vez disso, o cavalo se move em forma de L, conforme mostrado no diagrama. Mas é possível para um cavalo que se move dessa maneira visitar todas as casas do tabuleiro exatamente uma vez?

Usando o conceito de passeio do cavaleiro, William Beverley conseguiu produzir um quadrado mágico, conforme mostrado abaixo. As células são numeradas em sequência, conforme o cavaleiro as visita. Embora todas as linhas e colunas totalizem 260, as diagonais principais não, portanto, falando estritamente, é um quadrado semimágico. Na verdade, um quadrado mágico baseado no passeio de um cavaleiro é frequentemente chamado de passeio mágico, então o que Beverley produziu em 1848 é um passeio semimágico!

À primeira vista, parece que o seguinte quadrado mágico de Feisthamel se encaixa no projeto. As linhas, colunas e diagonais somam 260. Infelizmente, é apenas um passeio parcial do cavaleiro, pois há um salto de 32 para 33.

Então, quando é possível transformar a viagem de um cavaleiro em um quadrado mágico? Em 2003, Stertenbrink e Meyrignac finalmente resolveram esse problema computando todas as combinações possíveis. Eles encontraram 140 tours semimágicos, mas nenhum tour mágico. Xeque-mate!

Quadrados latinos

Os quadrados latinos são os verdadeiros ancestrais do Sudoku. Você pode encontrar exemplos de quadrados latinos na literatura árabe com mais de 700 anos. Eles foram descobertos por Euler alguns séculos depois, que os viu como um novo tipo de quadrado mágico, e é graças a ele que os chamamos de quadrados latinos.

Os quadrados latinos são grades preenchidas com números, letras ou símbolos, de forma que nenhum número apareça duas vezes na mesma linha ou coluna. A diferença entre um quadrado mágico e um quadrado latino é o número de símbolos usados. Por exemplo, existem 16 números diferentes em um quadrado mágico de 4 por 4, mas você só precisa de 4 números ou letras diferentes para fazer um quadrado latino de 4 por 4.

Agora, se olharmos para as três caixas inferiores, uma das linhas já tem 6 números. Eu chamei as células vazias de A, B e C (em ordem da esquerda para a direita), e os números que estão faltando são 3, 7 e 8. Se você olhar para a célula C, o único número que pode entrar é 7. Isso ocorre porque a coluna em que C está já contém 3 e 8.

Encontrar A e B agora é muito simples. Já existe um 3 na mesma coluna que B, então B deve ser 8. Isso significa que A deve ser 3. Resolver o resto do quebra-cabeça é um pouco mais complicado, mas vale o esforço.

A mania do Sudoku se espalhou pelo mundo e não mostra sinais de desaceleração. Diversas variações foram desenvolvidas a partir do tema básico, como versões de 16 por 16 e combinações multi-grade (você pode tentar um diferença duplex sudoku no Mais quebra-cabeça). Mas, como acontece com os quadrados mágicos e os quadrados latinos, a popularidade do Sudoku vai depender de se eles podem continuar a oferecer novos desafios.


Design de quadrados latinos

Nesta página, descrevemos os conceitos básicos de projetos de quadrados latinos. Informações adicionais podem ser encontradas nas seguintes páginas da web:

UMA Quadrado Latino design tem dois fatores de incômodo (linhas e cols) e um fator de tratamento, cada um dos quais tem o mesmo número de níveis, denotados r. Não há replicações e sem interações. Se denotarmos os possíveis efeitos do tratamento por letras latinas, então todas as linhas e colunas são permutações dessas letras (sem linhas repetidas e sem colunas repetidas).

Para r = 4 e r = 5, as configurações possíveis são:

Figura 1 - Configurações do quadrado latino

Observe que há muitas configurações possíveis de 4 × 4 ou maiores, embora muitas delas sejam equivalentes no sentido de que uma pode ser obtida de outra trocando uma ou mais linhas e / ou colunas. Na verdade, existem 4 configurações 4 × 4 não equivalentes e 56 configurações 5 × 5 não equivalentes. Acontece que todas as configurações 3 × 3 são equivalentes.

Exemplo 1: Uma fábrica deseja determinar se há uma diferença significativa entre quatro métodos diferentes de fabricação de um componente de avião, com base no número de milímetros da peça da medição padrão. Quatro operadores e quatro máquinas são designados para o estudo. Um projeto de quadrados latinos é usado para considerar os fatores de incômodo dos operadores e das máquinas.

A representação de um projeto de quadrados latinos é mostrada na Figura 2 onde A, B, C e D são os quatro métodos de fabricação e as linhas correspondem aos operadores e as colunas correspondem às máquinas.

Figura 2 - Representação dos quadrados latinos

Para nossos propósitos, usaremos as seguintes representações equivalentes (consulte a Figura 3):

Figura 3 - Design dos quadrados latinos

O modelo linear do design dos quadrados latinos assume a forma:

Uma implementação do design em Excel é mostrada na Figura 4.

Figura 4 - Análise do quadrado latino

The left side of Figure 4 contains the data range in Excel format (equivalent to the left side of Figure 3). The middle part of Figure 4 contains the means of each of the factor levels. Representative formulas used are shown in Figure 5.

Célula Fator Fórmula
L4 Fileira =AVERAGE(H4:K4)
H8 Coluna =AVERAGE(H4:H7)
H11 Tratamento =AVERAGEIF($B$8:$E$11,H10,$B$4:$E$7)

Figure 5 – Formulas for factor means

The right side of Figure 4 contains the ANOVA analysis. The degrees of freedom for all three factors is 3 (cells P4, P5, P6), equal to the number to r – 1, as calculated by =COUNT(B4:B7)-1. dfT = r 2 – 1 = 15, while dfE = (r–1)(r–2) = 6.

Formulas for the sum of squares (WL) terms are shown in Figure 6. The other values in Figure 4 are calculated in the usual way.

Célula Fator Fórmula
O5 Tratamento =DEVSQ(H11:K11)*(P5+1)
O6 Rows =DEVSQ(L4:L7)*(P6+1)
O7 Colunas =DEVSQ(H8:K8)*(P7+1)
O8 Error =O9-SUM(O5:O7)
O9 Total =DEVSQ(H4:K7)

Figure 6 – Formulas for sums of squares

We see from Figure 4 that there is a significant difference between the four methods (p-value = 0.03345 < .04 = α). There is no significant difference between the operators or between the machines, and so blocking on these factors may not have been necessary in this case.

The analysis is similar when the standard (i.e. stacked) input format is used (see Figure 7). Por exemplo. the mean for row 1 (cell G4) can be calculated by the formula

The mean for treatment A (cell I4) can be calculated by using the formula

Figure 7 – Latin Square Analysis for stacked format

Observação: In the usual three-factor design, the minimum sample size would be 4 × 4 × 4 = 64, while in this design we only require a sample size of 4 × 4 = 16.

Observação: Latin Squares can also be used for a three-factor ANOVA when there are no replications, even when the row and column factors are not nuisance factors, but factors of interest.


Isenção de responsabilidade

Registration on or use of this site constitutes acceptance of our User Agreement, Privacy Policy and Cookie Statement, and Your California Privacy Rights (User Agreement updated 1/1/21. Privacy Policy and Cookie Statement updated 5/1/2021).

© 2021 Advance Local Media LLC. All rights reserved (About Us).
The material on this site may not be reproduced, distributed, transmitted, cached or otherwise used, except with the prior written permission of Advance Local.

Community Rules apply to all content you upload or otherwise submit to this site.


Latin Square in C++

In this tutorial, we are going to learn about the Latin square.

The latin square is a matrix (3 x 3) in the form

If you carefully observe the pattern of the above matrix, then you will find out that the last number of the previous row comes as the first element of the next row.

We have to write the program that generates the above matrix for the input n.

Let's see the steps to write the program for the generation of the latin square.

  • Initialise the n with any number you like.
  • Initialise a number with the value n + 1 call it as mid.
  • Write a loop that iterates from 1 to n both inclusive.
    • Assign the value of mid to a temp variable.
    • Write a loop until temp reaches to the value n.
      • Print the temp.
      • Print the value.

      If you run the above code, then you will get the following result.


      Assista o vídeo: Matura podstawowa 2021 - zadanie - pole kwadratu (Dezembro 2021).