Permutation et Symétrie

[Ben314]

Salut,
Une toute simple (si on s'y prend correctement) énigme (encore tirée du livre de P.H.)

On fixe un entier n et on considère une matrice symétrique nxn tel que chaque ligne (et donc chaque colonne) contienne tout les entiers 1,2,3,...,n dans un certain ordre.

La diagonale de cette matrice peut elle, elle aussi, contenir tout les entiers 1,2,3,...,n ? peut-elle contenir autre chose que tout les entiers de 1..n ?

Par exemple la matrice montre que, pour n=4, la diagonale n'est pas forcé de contenir les nombres 1,2,3,4. Mais existe t'il une matrice 4x4 dont la diagonale contient 1,2,3,4 ?

Comme c'est trés simple, je suggérerais que ceux qui ont la réponse... ne la donne pas pour que tout le monde cherche... :id:

[Finrod]

ok mais c'est pas la matrice d'une permutation.

pour n=2, j'ai

la diagonale est plus une permutation en ton sens là ? je dis une bêtise ?

edit : ou ialors j'ai donné ma réponse parce que j'y croyais pas trop, si c'est juste désolé.

[Ben314]

ok mais c'est pas la matrice d'une permutation.

pour n=2, j'ai

la diagonale est plus une permutation en ton sens là ? je dis une bêtise ?

edit : ou ialors j'ai donné ma réponse parce que j'y croyais pas trop, si c'est juste désolé.

C'est parfaitement bon : on va dire que c'est "un début" de réponse : ton exemple montre que, pour n=2, la diagonale n'est pas forcément une permutation. En constatant que ta matrice 2x2 est au fond la seule qui vérifie les hypothèses, cela montre aussi que pour les matrices 2x2, la diagonale n'est jamais une permutation.

Quand je disais "ne pas donner la soluce", d'abord, vous êtes pas obligé de vous y tenir et cela ne vous empèche pas de donner les pistes que vous suivez...

Résumé : Ta piste = "j'essaye le cas n=2 et j'ai la soluce pour n=2"
Sauf qu'il existe des entiers n un peu plus grand que 2... :zen:

[beagle]

avec ton fameux déplacement de type cavalier d'échecs, tu peux construire cela sur rangées colonnes et les diagonales.Cela ne marche pas avec tous les pas et les ordres.

et avec deux carrés latins orthogonaux tu construits les carrés magiques dits diaboliques qui sont magiques sur toutes les diagonales également.
(pour les ordres impairs)

[ffpower]

A partir des 2 exemples, sans y avoir réfléchi, je dirais que :
( ya forcément une symétrie par rapport a l antidiagonale )

[Ben314]

Essaye un troisième exemple :

[beagle]

m'a gourré hier soir car je ne connaissais pas la définition de matrice symétrique,
mais me trouble dans ton exo ce passage:
"tout les entiers 1,2,3,...,n dans un certain ordre."
Or la première matrice 4x4 que tu donnes n'obéit pas à cette règle.
Donc?

parce que si c'est dans un certain ordre qui reste constant,
la manière de les fabriquer revient bien à ce que j'avais dit hier,
c'est pourquoi je me suis lancé tète baissée sans tenir compte de ton autre condition.

[Ben314]

Mon énoncé est surement "mal ficelé".
Tout d'abord, il est inutile de savoir ce à quoi servent les matrices en math pour cette énigme : il s'agit juste d'un carré nxn contenant des entiers.
Par contre, il faut savoir ce que veut dire symétrique : cela signifie que la i-éme ligne est identique à la ième colonne : par exemple une matrice symétrique 4x4 est obligatoirement de la forme avec une symétrie par rapport à une diagonale HautGauche-BasDroit.
Dans l'énigme, les matrices que l'on considère doivent avoir sur chaque ligne une fois et une seule chacun des nombres 1,2,3,...n dans un ordre quelconque (cet ordre ne peut pas être le même pour deux lignes car, grâce à la symétrie, une colonne ne peut pas contenir deux fois le même chiffre)

Un exemple de taille 5x5 d'une telle matrice est
On constate que, dans cet exemple, la diagonale HautGauche-BasDroit contient une fois et une seule les nombres 1,2,3,4,5.

La question est "est-ce un hasard ?", c'est à dire est-ce le cas pour toutes les matrices 5x5 ? et pour les matrices 6x6 ?

[beagle]

Sur les "matrices" que je connais cela semble toujours possible pour ordre impair, et toujours impossible pour les ordres pairs.

[Ben314]

Tout à fait exact...
As tu la preuve ?

[beagle]

non, j'ai pas la preuve.
Mais la raison qui n'explique rien est celle-ci:
avec les impairs l'axe de symétrie passe par le milieu .
avec les pairs l'axe de symétrie, le milieu n'existe pas.
pour 5 le milieu est 3 qui existe et 2 de chaque coté
pour pair ,6 par exemple, le milieu est entre 3 et 4, il n'existe pas.

or le milieu est la grande diagonale par exemple.

Si quelqu'un peut comprendre des explications comme ça, chapeau.

[ffpower]

Bon, alors après avoir réfléchi maintenant ( ca m'arrive^^ ), voila ce que j'obtiens:
On fixe un k de {1..n}. Soit f de {1..n} dans {1..n} qui a i associe l'entier j tel que k se trouve en (i,j) dans la matrice. Alors la condition de symétrie implique que f est involutive, ce qui implique si n est pair que f a un nombre pair de points fixes. Or le nombre de points fixes de f correpond au nombre d'occurences de k sur la diagonale, ce qui montre donc que l'on ne peut y arriver si n est pair. Reste donc a montrer que c'est possible si n est impair..

[Ben314]

EXACT (on peut aussi faire un raisonement identique sur le fond mais demandant un peu moins de culture...)

[beagle]

Sans culture maths, mais c'est moi ça.
Par rapport à ce que j'avais dit,
les diagonales, petites et grandes du carré,
sont au nombre de 2n-1,
et c'est cela qui permet aux imapirs d'ètre symétrique en utilisant la grande diago et en se répartissant les petites diagos en n et n.
Les pairs ne peuvent faire cela,
ils sont obligés de symétriser à l'intérieur de la grande diago.

Si on reprend ta matrice 5x5, je peux la faire dériver de celles sur lesquelles j'ai joué.Mais je ne peux montrer si la transformation rajoutait un degré de liberté, ou bien si les contraintes restaient.D'après ffpower les contraintes restent.

Pour les impairs il existe une solution triviale qui marche pour tous les impairs.

[lapras]

Jolie ffpower !

[beagle]

démontrer (si c'est vrai de préférence) l'équivalence avoir 1 2 3 4 5 sur grande diagonale oblige à avoir sur autre diagonalité une diagonale entière de 1 ou de 2 ou de 3 ou de 4 ou de 5.
A-t-on l'équivalence avoir 12345 sur une diagonale équivalent avoir une diago opposé de mème chiffre?
exemple:
12345
24531
35214
43152
51423

grande diago série de 1 à 5
dans les diagonales opposées on a une diago avec des 1 uniquement
les petites diagos ont deux bouts pour faire 5, et cela serait diago si on accolait les carrés.

[Ben314]

Bon, comme le post "s'enterre", je donne la (une) soluce (au fond, c'est la même que celle de ffpower mais avec des arguments légèrement plus simples) :
On fixe un k de {1..n} et on compte les k en dehors de la diagonale.
Comme la matrice est symétrique, il y en a autant en dessus qu'en dessous de la diagonale, donc au total un nombre pair. Or, on sait qu'en comptant aussi ceux de la diagonale, on doit en trouver n donc :
1) Si n est pair, il y a un nombre pair de k sur la diagonale donc il ne peut pas y en avoir qu'un seul.
2) Si n est impair, il y a un nombre impair de k sur la diagonale donc au moins un. Cela montre que sur la diagonale, il y a au moins un 1, au moins un 2, ..., au moins un n. Sauf que la diagonale ne contient que n termes, donc il y a forcément un seul 1, un seul 2, ..., un seul n.