Dénombrement

[Envie2Savoir]

Bonjour à tous,

Je lisais un article intéressant sur casse tête à savoir :
https://images.math.cnrs.fr/Un-casse-tete-et-son-groupe.html?lang=fr

Et dans la section : Quelques compléments accessible au milieu de page, arrive la notion du nombre de positions différentes.

Ainsi l'auteur annonce 181 440 positions, ce qui correspond à

Je ne comprends pas pourquoi l'auteur divise par deux le factoriel 9.
Est ce qu'une âme charitable pourrait m'expliquer s'il vous plaît.

Merci d'avance. Bonne soirée.

[lyceen95]

Il y a 9! façons de placer les 9 éléments, mais (je fais confiance à l'auteur), parmi ces 9! dispositions, il y en a seulement la moitié qui permettent de résoudre le puzzle.

[Envie2Savoir]

Merci luceen95 pour ta réponse.

Je fais confiance à l'auteur, il n'y a pas de soucis, mais j'aimerai comprendre !

De plus sa phrase est claire :

Le casse-tête a 181 440 positions différentes [...]

. A aucun moment il ne parle uniquement des positions permettant de résoudre le jeux lors de ce dénombrement. C'est après qu'il évoque le fait qu'on a une chance sur deux ... Donc a la rigueur je comprendrai qu'il fasse 181440 / 2.

Merci, bonne journée.

[lyceen95]

Non, ce 181440, c'est déjà 9! divisé par 2.
181440 /2 n'a aucun rôle dans ce calcul.

En résumé, si on part de la configuration 'finale', on peut faire tous les mélanges qu'on veut, on a 181440=9!/2 dispositions possibles.
Et par contre, si on s'autorise à démonter le jeu, et qu'on pose au hasard les 9 pièces, on a 362880=9! dispositions possibles.

[Ben314]

Salut,
J'ai pas vraiment lu l'article, mais comme ce type de casse tête et sa vision mathématique est plus que classique, je me doute du pourquoi :
Des situations "théoriques", il y en a effectivement 9!, mais en fait, partant de la situation de départ, tu ne peut pas toutes les atteindre. Pour être plus précis, parmi les 9! permutations théoriquement possible, tu ne va pouvoir atteindre que celles qui sont dans le "sous groupe alterné" c'est à dire ayant une "signature" égale à +1.
En fait, le truc évident, c'est que tu ne peut atteindre que des éléments de signature +1 vu que les "mouvement de base" sont des 5-cycles (de signature +1). Et il doit falloir un peut tâtonner (sans doute avec des commutateurs) pour montrer que tout les 3-cycles sont atteignables et donc que tout les éléments du groupe alterné sont atteignable.

Si ça t’intéresse, tu peut chercher des articles de vulgarisation sur ce fameux "groupe alterné" et la notion de "signature" d'une permutation. Par exemple, le jeu sans doute le plus ancien (et qui a fait fureur à son époque vers 1870) dont l'étude utilise ces notion est le Jeu du Taquin

[Ben314]

Je viens de regarder (en diagonale) l'article et je n'ai pas vu de tentative d'explication concernant cette fameuse division par 2. Mais par contre, il y a un lien vers un article de Michel Coste sur le Taquin où tu trouvera une explication simple de ce qu'est le groupe alterné et la signature d'une permutation (donc du pourquoi il n'y a que la moitié des dispositions qu'on peut atteindre dans le cas du jeu décrit par ton article).

[lyceen95]

Oui, idem, j'ai lu en diagonale, et c'était ma conclusion : 'faites moi confiance, parmi les 9! dispositions possibles, on ne peut en atteindre que la moitié par les mouvements autorisés.'

Le 9!, on sait l'expliquer, il ne pose pas de problème.
On se doute bien que par des mouvements autorisés, on risque d'être bloqué. Mais faut-il diviser par 2, par 3, par 4, par 5 ou plus, ça n'a rien d'évident a priori. Et l'expérience qu'il propose est sans doute la meilleure : jouer, et constater qu'effectivement, quand presque tous les éléments sont bien placés, on arrive à atteindre la moitié des positions 'envisageables'.

[Ben314]

De donner un "algorithme de résolution", ça permet de montrer que "au moins toutes ces dispositions là sont faisables", mais lorsqu'on atteint pas l'ensemble de toutes les combinaisons, il faut forcément un argument théorique pour justifier qu'on ne peut pas atteindre les autres (vu que ça pourrait très bien venir du fait que notre algorithme n'est pas optimal . . .)

[Envie2Savoir]

Merci beaucoup pour vos explications. Même si tout n'est pas encore au clair de mon côté (signature, sous groupes, ...) Il faut que je digère les lectures proposées
En ce qui concerne la question initiale, c'est bien compris et je vous remercie tous les deux lyceen95 et Ben314.

Bonnes fin de journée et bonne continuation.