Tente usar alguma espécie de técnica de backtracking. Isso em princípio
tornaria a análise mais limpa pelo menos XD.
E minha teoria da permutação cíclica falhou... :(
Outra coisa seria conferir se todas as matrizes satisfazem estas condições
para a 'borda perfeita'. Eu não duvido disso, mas é necessário formalizar -
algo como criar classes de matrizes...
Em 20 de novembro de 2013 16:24, Bernardo Freitas Paulo da Costa
bernardo...@gmail.com escreveu:
2013/11/20 PeterDirichlet peterdirich...@gmail.com
On 20-10-2013 16:28, marcone augusto araújo borges wrote:
Quantas matrizes 4 x 4 formadas pelos elementos 1,2,3 e 4 possuem
em cada linha e em cada coluna todos elementos distintos?
Vou testar uma ideia.
Sabemos que, se trocarmos 1,2,3,4 por qualquer permutação deles, de
forma consistente, obtemos outra matriz que satisfaz o enunciado.
Por exemplo:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
Substitua 1 por 3 e 3 por 1, mantendo o 2 e o 4:
3 2 1 4
2 3 4 1
1 4 3 2
4 1 2 3
Quando é que duas dessas matrizes seriam iguais? Nunca, pois a primeira
linha já seria diferente. Assim, de uma matriz obteremos outras 4! matrizes.
Assim sendo, eu vou tacitamente aceitar que a primeira linha é '1 2 3
4', e depois multiplicar por 4!.
Mais uma coisa interessante é que podemos permutar as linhas entre si!
Veja a segunda matriz:
1 2 3 4
3 4 1 2
4 3 2 1
2 1 4 3
É óbvio conferir que no caso geral a propriedade se manterá.
Assim, eu posso pensar que a 'borla' da matriz é assim:
1 2 3 4
2 x x x
3 x x x
4 x x x
Basta depois multiplicar por 4! * 3!.
Daqui para diante, me parece que complica um pouquinho...
MAS eu não desconfiaria se a resposta não tiver a ver com permutações
cíclicas, no seguinte sentido:
cada linha é permutação cícilca da primeira.
As quatro matrizes satisfazendo todas as condições (únicos elementos,
fixar os bordos) são:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
2 1 4 3
3 4 2 1
4 3 1 2
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
Eu vou tentar escovar o programa para o caso 5x5, por enquanto ele
calcularia 5 ^ 16 casos...
--
Bernardo Freitas Paulo da Costa
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
--
/**/
神が祝福
Torres
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
