[obm-l] Transposicao de Matrizes

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

Ola Pessoal,

Seja P um numero primo e A uma matriz quadrada de ordem P. Vou supor
que as linhas serao numeradas de 0 ate P-1 de cima para baixo e as
colunas tambem de 0 ate P-1 da esquerda para a direita.Facamos A1=A^t
( A1 e a transposta de A ) e consideremos a seguinte equacao de
recorrencia :

A(n+1,i, j) --> elemento da linha "i" e coluna "j" da matriz An+1

A(n+1, i, j ) = A(n, j, mod(i + j, P) )
onde mod(i + j,P) representa o resto da divisao de i + j por P.

Para cada matriz A de ordem P, P primo, usando as equacoes acima,
forme a sequencia :
(A1, A2, ..., Ap)

DEMONSTRE QUE :

1) Se dois elementos estao em uma mesma linha de uma das matrizes Ai
entao eles nao estao em uma mesma linha de qualquer outra matriz Aj
com j diferente de i
2) Acrescente a sequencia (A1,...,Ap) a matriz A, formando
REDE=(A,A1,...,Ap). Mostre que quaisquer dois elementos da matriz A
que nao estao em uma mesma linha estarao em uma mesma linha de alguma
das matrizes A1, ...,Ap

Quem ja estudou Mecanica Quantica vai identificar rapidamente a
inspiracao para o "processo generalizado de transposicao" descrito
acima. Agora, perceba que eu estou descrevendo um algoritmo ( usando
provisoriamente matrizes. Logo, logo vou me livrar delas ) tal que
QUAISQUER DOIS OBJETOS de um conjunto de P^2 objetos ESTARAO
NECESSARIAMENTE JUNTOS ( em uma mesma linha de alguma das matrizes )
UMA UNICA VEZ !

Se voce IMAGINAR que serao sorteados N ( N =< P^2 ) numeros e que cada
linha e um cartao de apostas entao voce pode dizer que este algoritmo
acerta todos os duplos possiveis qualquer que seja os N numeros
sorteados. Eu sei generalizar isso mas nao jogo e nem me interesso por
jogos de azar.

Voce tambem pode IMAGINAR que uma matriz e uma equipe de policiais,
cada linha da matriz constituindo um grupo da equipe. E importante que
os policiais nao se conhecam previamente. Neste caso, quaisquer dois
policiais de uma linha nunca se falaram antes e so tomarao
conhecimento das tarefas no momento da acao, o que impede vazamentos.
Eles tambem jamais trabalharao juntos novamente ...

Mas a verdadeira motivacao esta aqui : qualquer elemento Aij da matriz
A e um FIO cuja COR e definida unicamente pelo numeros "i" e "j".
Assim, nao ha dois fios com a mesma cor. Considerando cada linha como
uma juncao onde os fios se encontram, o conjunto de matrizes
(A,A1,...,Ap) forma uma REDE ou KIPO.

Cada KIPO possivel e UMA UNICA mensagem cifrada. Seja dado um primo P
> 13. Seja K um KIPO de ordem P. Quantas mensagem disjuntas podemos
formar ?

Um Abraco a Todos
Paulo Santa Rita
4,1200,110707

OBS : Eu, Paulo Santa Rita, sou um Matematico, daqueles que chamam de
"Matematico Puro". Quero dizer que nao tenho interesse em Matematica
Aplicada e que portanto nao posso ser responsabilizado por qualquer
aplicacao nociva que algum trabalho meu possa ter. Eu nunca divulguei
antes o Algoritmo Acima ( e suas generalizacoes ) e ele e um trabalho
antigo, feito quando eu ainda era crianca.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================