pourquoi-le-puzzle-15-est-il-insoluble

Pourquoi le puzzle 15 est-il insoluble ?

Le « puzzle 15 », également connu sous le nom de « problème numérique 15 », n'est pas insoluble, mais plutôt que l'état cible ne peut être atteint à partir de certains états initiaux.

Description du jeu

Le « puzzle 15 » est un jeu de glissement où le plateau de jeu est une grille 4×4 avec 15 glissières numérotées de 1 à 15 et un espace vide. L'objectif du joueur est de déplacer les glissières dans un ordre de gauche à droite, de haut en bas, ce qui donne une séquence ordonnée de 1 à 15, l'espace se trouvant dans le coin inférieur droit.

Cas insolubles

La situation ne peut être légalement déplacée pour atteindre l'état cible si, et seulement si, le nombre de paires inversées dans l'état initial est impair. Une paire inversée est une paire de nombres dans une série qui est qualifiée de paire inversée si leurs positions avant et arrière sont dans l'ordre de grandeur inverse, c'est-à-dire que le nombre qui se trouve devant est supérieur au nombre qui se trouve derrière. Par exemple, dans la série 2, 4, 3, 1, les paires inversées sont (2, 1), (4, 3), (4, 1), (3, 1), pour un total de quatre.

Preuve.

Le déplacement des glissières sur le plateau peut être considéré comme une transformation de l'arrangement de ces glissières. Chaque fois qu'une glissière est déplacée, un espace est en fait échangé avec une glissière voisine. Et cette opération d'échange modifie la parité du logarithme inverse de l'arrangement. Le logarithme inverse de l'état cible est 0, ce qui est pair. Si le logarithme inverse de l'état initial est impair, quel que soit le nombre de fois qu'il est déplacé, son logarithme inverse ne peut pas être changé pour devenir pair, et l'état cible ne peut pas être atteint.

Si vous aimez aussi jouer à Puzzles ball, c'est totalement gratuit et amusant et facile.