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

Condição de existência de quadrados latinos ortogonais

0 votos
61 visitas
perguntada Set 4 em Matemática por pedro zarur (1 ponto)  
editado Set 4 por pedro zarur

Exercício 13 da página 36 do livro "The Art of Computer Programming", de Donald E. Knuth:
Um quadrado de ordem 10x10 pode ser dividido em quatro quartos de ordem 5x5. Um quadrado latino formado pelos dígitos {0,1,...,9} tem k "intrusos" se o seu quarto superior esquerdo tem exatamente k elementos maiores ou iguais a 5. Prove que o quadrado latino não tem um par ortogonal a não ser que ele tenha ao menos 3 intrusos.

Compartilhe

1 Resposta

0 votos
respondida Set 4 por pedro zarur (1 ponto)  
editado Set 26 por pedro zarur

Primeiro, algumas definições:

Um quadrado latino é uma matriz quadrada em que cada elemento aparece uma única vez em cada linha e uma única vez em cada coluna.
Dois quadrados latinos são ditos ortogonais se, quando sobrepostos, cada par de elementos aparece apenas uma vez.

O exercício em questão pode ser encarado como um caso particular da seguinte proposição: Se um quadrado latino de ordem \(4k+2\), formado pelos elementos \({1,2,...,4k+2}\) e constituído por quatro quartos de ordem \(2k+1\), possuir menos de \(k+1\) elementos maiores que \(2k+1\) no seu quarto superior esquerdo, então esse quadrado não possui um par ortogonal. Provemos o caso geral (com \(k = 2\) temos o problema original).

Prova: Consideremos um quadrado latino \(Q\) de ordem \(4k+2\) formado por quatro quadrados menores de ordem \(2k+1\), \(Q_{1}\), \(Q_{2}\), \(Q_{3}\) e \(Q_{4}\):
\[Q=\left[\begin{array}{cc} Q_{1} & Q_{2} \\ Q_{3} & Q_{4} \\ \end{array}\right]\]

Primeiro, demonstraremos que cada elemento de \(Q_{1}\)U \(Q_{4}\) aparece um número par de vezes nessa união. Depois, provaremos que o fato de \(Q_{1}\) ter menos de \(k+1\) elementos maiores que \(2k+1\) implica que o par ortogonal de \(Q\) contradiz a conclusão da primeira parte da demonstração.

1ª parte: se um número aparece \(n\) vezes em \(Q_{1}\) então, para preencher as linhas nas quais ele não aparece em \(Q_{1}\), ele necessariamente aparece \(2k+1-n\) vezes em \(Q_{2}\). Seguindo o mesmo raciocínio para as colunas, temos que esse número aparece \(2k+1-(2k+1-n)\) vezes, ou seja, \(n\) vezes em \(Q_{4}\). Ou seja, cada elemento de \(Q_{1}\)U \(Q_{4}\) aparece \(2n\) vezes, isto é, um número par de vezes nessa união. Logo, a própria estrutura do quadrado latino garante essa propriedade, válida para qualquer quadrado de ordem \(4k+2\).

2ª parte: Consideremos agora que \(Q_{1}\) tem menos de \(k+1\) elementos maiores que \(2k+1\). Ou seja, ele pode ter, no máximo, \(k\) elementos maiores que \(2k+1\).

Seguindo exatamente o mesmo raciocínio da primeira parte da prova, concluímos que no máximo \(2k\) elementos do conjunto \(\{1,...,2k+1\}\) ocorrem em \(Q_{2}\)U \(Q_{3}\) e, no mínimo \(2k+2\) elementos de \(\{1,...,2k+1\}\) ocorrem em \(Q_{1}\)U \(Q_{4}\).

Sendo \(L\) um quadrado latino ortogonal a \(Q\), temos que para cada elemento \(x\) em \(L\), todo par \((x,1), (x,2),... (x, 4k+2)\) deve ocorrer se sobrepusermos os dois quadrados. Por eles serem ortogonais, cada par ocorre apenas uma vez. Consideremos também que, à maneira de \(Q\), \(L\) foi dividido em quatro quartos: \(L_{1}, L_{2}, L_{3}\) e \(L_{4}\).

Assim, temos que, sobrepondo os dois quadrados, um elemento de \(L\) necessariamente se combinaria com \(2k+1\) elementos de \(\{1,...,2k+1\}\) em \(Q_{1}\)U \(Q_{4}\). Mas como há no mínimo \(2k+2\) elementos de \(\{1,...,2k+1\}\) em \(Q_{1}\)U \(Q_{4}\), sobraria um elemento do conjunto a ser combinado com algum outro elemento de \(L\). Logo, temos que dois elementos de \(L\) aparecem um número ímpar de vezes em \(L_{1}\)U \(L_{4}\), o que contradiz a propriedade provada na primeira parte da demonstração.

Portanto, concluímos que esse suposto quadrado latino ortogonal a \(Q\) não existe caso \(Q_{1}\) tenha menos de \(k+1\) elementos maiores que \(2k+1\).

comentou Set 14 por Thiago Trafane (21 pontos)  
Pedro, em primeiro lugar, parabéns pela sua resposta! Quanto aos meus comentários:

1) Me parece claro que se um elemento aparece \(n\) vezes em \(Q_1\), então ele aparece no máximo \(2k+1-n\) vezes em \(Q_2\). Contudo, não é óbvio para mim que isso vale com igualdade. Talvez valesse desenvolver melhor o raciocínio.

2) Na demonstração da segunda parte, você faz a seguinte afirmação: "\(2k\)  elementos do conjunto \( \{1,...,2k+1\} \) ocorrem fora de \(Q_1 \cup Q_4\)". O que você quer dizer com fora? Em \(Q_2\) e \(Q_3\)? Ademais, logo em seguida, você afirma que "no mínimo \(2k+2\) elementos de \( \{1,...,2k+1\} \) ocorrem em \(Q_1 \cup Q_4\)". Por que?

3) No fim da demonstração da segunda parte, você afirma que "Mas como há no mínimo \(2k+2\) elementos de \( \{1,...,2k+1\} \) em \(Q_1 \cup Q_4\), sobraria um elemento do conjunto a ser combinado com algum outro elemento de \(L\). Logo, teríamos que dois elementos de \(L\) aparecem um número ímpar de vezes em \(Q_1 \cup Q_4\), o que contradiz a conclusão da primeira parte da demonstração". Sinceramente, não ficou claro para mim o que você está fazendo aqui. Por que você está combinando um elemento qualquer de \(L\) com os elementos de \(Q_1 \cup Q_4\)?

4) O professor pede em qualquer exercício uma implementação computacional do problema, mesmo quando isso não é pedido no enunciado. Logo, ficou faltando essa parte.
comentou Set 15 por pedro zarur (1 ponto)  
editado Set 15 por pedro zarur
Fala Thiago, tudo bem? Obrigado pelas considerações! Vou respondê-las aqui nesse comentário e assim que puder edito a resposta para melhorá-la.

1) A própria estrutura do quadrado latino garante essa igualdade. Cada elemento aparece uma única vez por linha e uma única vez por coluna. Logo, se um elemento aparece \(n\) vezes em \(Q_1\), então ele necessariamente aparece \(2k - 1 - n\) vezes em \(Q_2\) para preencher as linhas nas quais ele não apareceu em \(Q_1\). O raciocínio análogo aplica-se aos demais sub-quadrados.

2) Exatamente, com "fora de  \(Q_1\)U\(Q_4\)" eu quis dizer "em \(Q_2\)U\(Q_3\)". De fato não ficou claro. Agora, o fato de no mínimo \(2k+2\) elementos de \(\{1,...,2k+1\}\) ocorrerem em  \(Q_1\)U\(Q_4\) é consequência da aplicação do raciocínio do primeiro tópico desse comentário.

Temos, por hipótese, que \(Q_1\) tem no máximo \(k\) elementos maiores que \(2k+1\). Ou seja, \(Q_1\) tem no mínimo \(k+1\) elementos de \(\{1,...,2k+1\}\) . Isso implica que \(Q_2\) e \(Q_3\) tem, cada um, no mínimo \(2k + 1 - (k + 1) = k\) elementos de \(\{1,...,2k+1\}\). Concluímos então, pelo mesmo raciocínio, que \(Q_4\) tem, no mínimo, \(2k+1 - k = k+1\) elementos de \(\{1,...,2k+1\}\). Logo,  \(Q_1\)U\(Q_4\) tem no mínimo \((k+1) + (k+1) = 2k+2\) elementos de \(\{1,...,2k+1\}\).

3) Eu combinei os elementos de \(L\) com elementos de \(Q\) pois é assim que verificamos se os quadrados são de fato ortogonais. Assim, formamos um novo quadrado com pares de elementos (um de \(Q\) e um de \(L\)).

É uma propriedade dos quadrados latinos que para todo \(x \in L\), todo par combinado com cada elemento de \(Q\) deve ocorrer. Já demonstramos que existem no mínimo \(2k+2\) elementos de \(\{1,...,2k+1\}\) em  \(Q_1\)U\(Q_4\). Assim, um elemento \(x \in L\) necessariamente se combinará com esses elementos \(1,..., 2k+1\). Mas sobrou um elemento repetido desse conjunto em  \(Q_1\)U\(Q_4\). Logo, um outro elemento de \(L\) deve se combinar com ele.

Considere que \(L\), à maneira de \(Q\), foi dividido em \(L_1, L_2, L_3\) e \(L_4\). Logo, provamos que pelo menos dois elementos de \(L_1\)U\(L_4\) aparecem um número ímpar de vezes nessa união. Mas isso contradiz o que provou-se na primeira parte da demonstração. E assim concluímos a prova.

4) Em relação a isso, já estou pensando em algo. Mas como é uma demonstração matemática é meio tricky implantar computacionalmente, não? Aceito sugestões kkkk

É isso, espero que tenha entendido :)
comentou Out 1 por Thiago Trafane (21 pontos)  
Pedro, obrigado pela resposta! Acredito que, de modo geral, tenha ficado bem mais claro agora. Se você incorporar esses comentários à sua resposta original, penso que ficará muito mais fácil para o leitor entender.

Sobre os seus últimos comentários, apenas algumas observações:

1) Onde você escreveu \(2k−1−n\), acho que seria \(2k+1−n\), como você colocou na resposta original.

3) Essa parte ainda não está totalmente clara para mim. Em primeiro lugar, quando você mostrou que existem no mínimo \(2k+2\) elementos de \( \{1,...,2k+1\} \) em \(Q_1 \cup Q_4\), isso não quer dizer que sejam elementos distintos. De fato, pelo que você mostrou na parte 1, eles não são todos distintos. Logo, não me parece correto afirmar que “sobrou um elemento repetido desse conjunto”. Sobraram mais elementos repetidos, não? Sei que se sobraram vários, sobrou um, mas me pareceu que você está considerando que sobrou exatamente um, não? Em segundo lugar, mesmo assumindo que seu argumento inicial está correto, não entendi como você chegou à conclusão que "pelos menos dois elementos de \(L_1 \cup L_4 \) aparecem um número ímpar de vezes nessa união".

4) Eu fiz um exercício criando um programa backtracking para gerar todos os quadrados latinos reduzidos de ordem \(n\) (http://prorum.com/?qa=6243/escreva-programa-backtracking-determinar-quadrados-algoritmo&show=6244#a6244). Você poderia tentar criar um programa análogo para gerar quadrados latinos ortogonais.
...