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

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

0 votos
31 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 10 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 ele necessariamente aparece \(2k+1-n\) vezes em \(Q_{2}\) e \(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. Essa propriedade obviamente é válida para qualquer quadrado latino ortogonal 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 o mesmo raciocínio da primeira parte da prova, concluímos que no máximo \(2k\) elementos do conjunto \(\{1,...,2k+1\}\) ocorrem fora de \(Q_{1}\)U \(Q_{4}\) 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, 2k+1)\) deve ocorrer se sobrepusermos os dois quadrados. Por eles serem ortogonais, cada par ocorre apenas uma vez.

Assim, temos que um elemento de \(L\) poderia ser combinado 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, teríamos que dois elementos de \(L\) aparecem um número ímpar de vezes em \(Q_{1}\)U \(Q_{4}\), o que contradiz a conclusão da 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 :)
...