4 novembre 2011

6 messages - Retourner à l'article

Le jeu de taquin, du côté de chez Galois

Objet du mois
Cet article est publié simultanément sur le site du Bicentenaire de la naissance d’Evariste Galois (IHP et SMF). Nous remercions en particulier l’auteur d’avoir permis ce partenariat.
Piste bleue
Le 4 novembre 2011, par Michel Coste - 6 commentaires

  • Le jeu de taquin, du côté de chez Galois

    le 4 novembre 2011 à 12:07, par Jacques Lafontaine

    Bravo ! C’est exactement le genre d’article qu’il faut (à mois avis du moins) pour IdM.

    Répondre à ce message

  • Le jeu de taquin, du côté de chez Galois

    le 8 novembre 2011 à 08:52, par François Brunault

    Merci pour ce joli article !

    Après l’avoir lu, je me suis posé la question suivante. Est-il possible, étant donnée une configuration de départ, de calculer le nombre minimal de mouvements nécessaires pour résoudre le puzzle ? Quelle est la configuration « la plus difficile », c’est-à-dire celle qui nécessite le plus de mouvements pour arriver à la solution ?

    L’algorithme usuel, qui consiste à remettre en place successivement chaque ligne (c’est en tout cas ce que je fais !), n’est sans doute pas optimal du point de vue du nombre de coups...

    Répondre à ce message

    • Le jeu de taquin, du côté de chez Galois

      le 10 novembre 2011 à 17:39, par François Brunault

      J’ai trouvé un début de réponse sur la page wikipédia anglaise consacrée au jeu de taquin. Il semble que quelque soit la configuration de départ, il soit possible de résoudre le puzzle en au plus 80 mouvements. En revanche, je ne sais pas quelles sont la ou les configurations qui nécessitent effectivement 80 mouvements.

      Répondre à ce message

  • Le jeu de taquin, du côté de chez Galois

    le 17 novembre 2011 à 23:04, par Michel Coste

    Merci, je ne connaissais pas cette borne de 80. Ca ne me semble pas évident de trouver une configuration dont on puisse montrer qu’elle nécessite bien 80 mouvements.

    Répondre à ce message

    • Le jeu de taquin, du côté de chez Galois

      le 20 janvier 2016 à 18:23, par Ben29

      Bonjour,

      « Le mouvement de droite fait avancer le nombre porté par la case qui bouge de quatre places dans la file. Ceci peut se faire par quatre sauts-de-moutons. »

      Moi j’en compte trois. Pouvez-vous m’éclairer ?

      Répondre à ce message

      • Le jeu de taquin, du côté de chez Galois

        le 22 janvier 2016 à 11:30, par Michel Coste

        Comptons !
        Si je donne un numéro d’ordre aux cases dans la file en suivant le chemin vert :
        1-2-3-4-5-trou-6-7-8-9-10-11-12-13-14-15,
        alors la case 10 gagne bien 4 places en resquillant et en se glissant dans le trou :
        1-2-3-4-5-10-6-7-8-9-trou-11-12-13-14-15.
        Elle est passée devant les n° 9, 8, 7 et 6 : ça fait bien quatre.

        Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.

Actualités des maths