Othello

[RomVi]

Bonjour

Voici une petite énigme que j'ai imaginé cet après midi. Par avance je m'excuse si elle est déjà connue sous une autre forme ; je n'ai pas la prétention d'être le 1er à avoir pensé à ce genre de problème...

On a 9 jetons du jeu Othello sur un jeu en 3x3 placés comme sur mon dessin en pièce jointe, les règles de base du jeu ne sont pas prises en compte. Le but est de tous les placer sur la face blanche, mais chaque fois que l'on retourne un jeton tous les jetons contigus (par un coté ou un coin) sont également retournés.

Existe il une possibilité de tous les placer du coté blanc ?
Questions subsidiaires :
- Si oui, en combien de coups minimum
- Existe il une combinaison de départ ne permettant pas d'obtenir le résultat voulu.

A vous de jouer
-----

[invite4917f876]

J'arrive seulement à avoir 3 jetons noirs ! C'est difficile de gagner !

[RomVi]

Merci pour ta participation mohamed02

Tu dois pouvoir arriver à faire mieux que ça, essayes d'alterner un coté et l'autre.

[invite848129ec]

Bonjour,
je suis arrivée en 5 mouvements, un peu par hasard, peut on faire mieux?

[A voir en vidéo sur Futura]

[Resartus]

Bonjour,
Je ne vais pas spoiler ton jeu, mais juste signaler qu'il s'agit d'un puzzle de la catégorie des "lights out puzzles", où on dispose de lampes allumées ou eteintes, et d'interrupteurs qui permutent l'état de plusieurs lampes à la fois. Il faut finir avec "tout éteint".

La résolution mathématique est intéressante (mais d'assez haut niveau), et utilise des calculs avec des matrices mais sur un corps fini : le corps Z/ZZ.
Les interrupteurs sont des transformations linéaires de l'espace vectoriel des n lampes, et selon la dimension de l'espace engendré par ces transformations, soit on peut eteindre toute configuration, soit il y a des configurations qu'on ne peut pas eteindre.... Il y a alors des familles distinctes de configurations, et on peut passer d'une configuration à toute autre de la même famille, mais pas changer de famille. Pour résoudre, il faut être au départ dans la même famille que "tout éteint".

Pour ceux que cela interesse :http://mathworld.wolfram.com/LightsOutPuzzle.html

[RomVi]

En effet le principe est assez proche, je ne connaissais pas ces "lights out puzzles", la seule différence étant que les règles semblent légèrement différentes (retournement des jetons contigus par une arête).
Pour mon problème il existe une méthode de résolution "mathématique" simple, niveau 1ere ou terminale technique.

[CM63]

Bonjour,

Ma méthode est de rechercher des règles d'invariance, ou au contraire de retournement du genre:
- si on retourne les 4 pions des coins, cela laisse invariant tous les autres.

[Deedee81]

Salut,

Ma méthode est de rechercher des règles d'invariance, ou au contraire de retournement du genre:
- si on retourne les 4 pions des coins, cela laisse invariant tous les autres.

C'est ainsi que je l'envisageais (pour simplifier la recherche). Je n'ai malheureusement pas eut le temps de me pencher dessus.
Exemple : chaque retournement retourne le jeton central, il faut donc un nombre total de retournement impair.

[Médiat]

Bonjour,

Une méthode un peu bourrin consiste à écrire des équations dans , par exemple(en numérotant les cases de 1 à 9 en partant du haut à gauche) en notant le retournement de la case , on obtient
La case 1 ne doit pas changer
La case 2 ne doit pas changer
d'où on tire :


etc.

Et du coup je peux affirmer que 5 est le minimum

 Cliquez pour afficher

[Médiat]

Question subsidiaire :
Trouver les configurations de départ telles que la solution soit de jouer une et une seule fois tous les jetons noirs et exclusivement ceux ci (il y en a plusieurs)
Trouver les configurations de départ telles que la solution soit de jouer une et une seule fois tous les jetons blancs et exclusivement ceux ci (je n'en ai pas trouvé jusqu'à présent)

[_Goel_]

Bonsoir,

Je regarde les types de mouvements possibles : ils sont au nombre de 3 :
- On retourne un carré de 4 jetons (en retournant le jeton du coin)
- On retourne un rectangle de 6 jetons (en retournant un jeton entre 2 coins)
- On retourne tous les jetons (en retournant le jeton du centre)

A l'inverse :
- le jeton d'un coin est influencé que par lui-même et les 4 jetons environnants soit 4 jetons
- le jeton entre 2 coins est influencé par 6 jetons
- le jeton du milieu est influencé par tous les autres jetons

on a 2^9 = 512 combinaisons possible
Retourner 2 fois le même jeton est inutile (même si c'est pas d'affilée). Donc on a un max de 9 retournements de jetons (+jetons adjacents) à effectuer pour atteindre n'importe quelle position finale
soit 2^9 = 512 positions finales max atteignables avec une position de départ donnée.

Par effet de symétrie, on ne peut étudier que 8 positions finales à partir d'une position initiale :
- ex : position initiale = tout blanc
- positions à étudier = un L de 3 cases, dont une est le centre, avec toutes les combinaisons possible (3 cases = 8 positions) toutes les autres cases ayant leur jeton qui bouge pas.

Donc déjà on a un maximum théorique de 8 familles de configurations indépendante (être dans une famille nous permet pas d'aller dans une configuration de l'autre famille)

On peut identifier une combinaison ainsi : C1=R1+R2+R5 (Statut de la case 1 si retournement retourner les jetons des cases 1, 2 et 5)
On peut définir le statut final d'un jeton en fonction de la combinaison de retournement : ex : la case 1 (coin supérieur gauche) = f(R1, R2, R4, R5) (Retourner les autres jetons n'influe pas sur la case 1)

Pour cela on peut définir un système d'équation :

Ri & Ci appartiennent à {0,1}

C1 = (-1)^(R1+R2+R4+R5)
C2 = (-1)^(R1+R2+R3+R4+R5+R6)
...
C5 = (-1)^(R1+R2+R3+R4+R5+R6+R7+R8+R9 )
...
C9 = (-1)^(R5+R6+R8+R9)


Si on revient à notre L d'étude (disons C1, C2, C5) on a donc à étudier (et résoudre) les 8 systèmes de 9 équations avec C1, C2, C5 = {0,1} et les Ci restants = 0

On peut transformer le système d'équation de :
C1 = (-1)^(R1+R2+R4+R5)
en
R1+R2+R4+R5 = 2.n1+s1
"ni" est, pour une case i, un entier quelconque compris entre 0 et 2 pour un coin, 0 et 3 pour une case entre 2 coins, et 0 et 4 pour la case centrale
"si" est, pour une case i, le statut s de la case i (1 pour retourné donc noir, 0 pour blanc)

Exemple pour un L avec toutes les cases retournées (noires) :
R1+R2+R4+R5 = 2.n1 +1
R1+R2+R3+R4+R5+R6 = 2.n2 +1
R2+R3+R5+R6 = 2.n3
R1+R2+R4+R5+R7+R8 = 2.n4
R1+R2+R3+R4+R5+R6+R7+R8+R9 = 2.n5 +1
R2+R3+R5+R6+R8+R9 = 2.n6
R4+R5+R7+R8 = 2.n7
R4+R5+R6+R7+R8+R9 = 2.n8
R5+R6+R8+R9 = 2.n9

Bref...
Merci excel...
Toutes les combinaisons de L sont atteignables à partir d'une position donnée, donc ça fait 1 famille.
Donc on a 512 positions différentes, 512 positions atteignables, 512 combinaisons de retournement. donc chaque combinaison de retournement conduit à un une position différente. Ce qui limite à 9 le nombre de retournement maximal (auquel cas tous les jetons sont conservés sauf celui du milieu)

Solution au pb : Retourner les jetons 1, 3, 5, 6 et 7.