Maths : exercice 28, page 61

28 billes sur un plateau hexagonal de 61 alvéoles, ça fait combien de positions possibles ?
Votre réponse devra s’appuyer sur une démonstration (avec formule et tout, et tout…).
Si besoin je désignerai un volontaire pour passer au tableau 😀

FightClub

 

Publicités

18 réflexions sur “Maths : exercice 28, page 61

  1. supposons que les billes blanches soient numérotées, positionnons les billes blanches, choix pour la première bille : 61, pour la deuxième 60, puis 59 cases restantes puis ….
    60x59x58x57x56x55x54x53x52x51x50x49x48 mais les billes ne sont pas numérotées, peu importe il faut diviser par le nombre de permutations, qui sont au nombre de 14x13x12x11x10x9x8x7x6x5x4x3x2x1 (factorielle 14)
    ça donne environ =22 512 762 077 400
    considérons les cases restantes (il en reste 47) et plaçons les billes noires numérotées : 47 choix pour placer la première, 46 pour a suivante …47x46x45x44x43x42x41x40x39x38x37x36x35x34 mais les billes ne sont pas numérotées, peu importe il faut diviser par les permutations, qui sont au nombre de 14x13x12x11x10x9x8x7x6x5x4x3x2x1 (factorielle 14) ça donne environ ….341 643 774 795
    on fait une jolie multiplication et on trouve
    22 512 762 077 400 x 341 643 774 795 = 7 691 345 000 000 000 000 000 000 ou sept millions de milliards de milliards

    à noter qu’on a pas considéré les positions où les blancs et/ou les noirs n’ont pas 14 billes …

      • Si le calcul de Mogway est correct, on peut le reduire en enlevant :
        les 6 rotations du plateau
        encore 6 autres en miroir
        et on retrouve encore ces 12 positions en changeant les couleurs (noir devient blanc et blanc devient noir)
        On voit bien que ces 24 changement ne donnent pas de nouvelles positions de jeu,
        il suffit donc de diviser le total de Mogway par 24
        ce qui ne fait plus qu’a peine 300 mille milliards de milliards de positions…

        Mais au fait on peut faire combien de variantes equilibrees ?
        Si personne ne resoud cette derniere question ce n’est pas grave, vu que FightClub presente une nouvelle variante par mois, on verra vite la reponse…

        A propos, Mogway, combien de positions differentes as tu recupere avec les parties sur Migs et pourra t on revoir ces parties un jour ?

  2. @saabalone : non, c’est faux, on n’obtient alors qu’une approximation. Pour obtenir le compte exact, il faut tenir des positions qui ont des symétries (et sont donc comptées moins de 12 fois), ce qui n’est pas facile.
    Par ailleurs, échanger Noir et Blanc n’est pas une transformation à comptabiliser, car les deux couleurs ont un rôle différent ; en particulier, ce ne serait pas du tout pareil de jouer en Domination en inversant les couleurs. Le seul cas où l’inversion de couleur ne change pas le jeu, c’est lorsque celle-ci s’obtient par une symétrie et est donc déjà prise en compte.

    Histoire de donner un exemple : les Marguerites classiques sont symétriques par rotation de 180°. Avec le calcul de Mogwai, elles sont chacune comptées 6 fois au lieu de 12.

    Pour être plus précis, Mogwai compte exactement
    – 1 fois : les configurations avec un axe de symétrie, symétriques par rotation de 60° ;
    – 2 fois : les configurations avec un axe de symétrie, symétriques par rotation uniquement de 120° ; les configurations sans axe de symétrie, symétriques par rotation de 60° ;
    – 3 fois : les configurations avec un axe de symétrie, symétriques par rotation uniquement de 180° ;
    – 4 fois : les configurations sans axe de symétrie, symétriques par rotation uniquement de 120° ;
    – 6 fois : les configurations avec un axe de symétrie, non symétriques par rotation ; les configurations sans axe de symétrie, symétriques par rotation uniquement de 180° ;
    – 12 fois : les autres configurations.

  3. @saabalone : non, c’est faux, on n’obtient alors qu’une approximation. Pour obtenir le compte exact, il faut tenir des positions qui ont des symétries (et sont donc comptées moins de 12 fois), ce qui n’est pas facile.
    Par ailleurs, échanger Noir et Blanc n’est pas une transformation à comptabiliser, car les deux couleurs ont un rôle différent ; en particulier, ce ne serait pas du tout pareil de jouer en Domination en inversant les couleurs. Le seul cas où l’inversion de couleur ne change pas le jeu, c’est lorsque celle-ci s’obtient par une symétrie et est donc déjà prise en compte.

    Histoire de donner un exemple : les Marguerites classiques sont symétriques par rotation de 180°. Avec le calcul de Mogwai, elles sont chacune comptées 6 fois au lieu de 12.

    Pour être plus précis, Mogwai compte exactement
    – 1 fois : les configurations avec un axe de symétrie, symétriques par rotation de 60° ;
    – 2 fois : les configurations avec un axe de symétrie, symétriques par rotation uniquement de 120° ; les configurations sans axe de symétrie, symétriques par rotation de 60° ;
    – 3 fois : les configurations avec un axe de symétrie, symétriques par rotation uniquement de 180° ;
    – 4 fois : les configurations sans axe de symétrie, symétriques par rotation uniquement de 120° ;
    – 6 fois : les configurations avec un axe de symétrie, non symétriques par rotation ; les configurations sans axe de symétrie, symétriques par rotation uniquement de 180° ;
    – 12 fois : les autres configurations.

  4. Eob, je savais bien que ma simplification etait un peu simpliste, et tu as certainement raison dans tes precisions sur les symetries meme si je n’ai pas tout saisie.

    Par contre en ce qui concerne le changement de noir en blanc, il suffit juste de changer aussi le trait et on se retrouve bien dans la meme position et la reflexion sera bien la meme pour jouer le cp suivant.

    En fait tout ca pour dire que si en theorie on a qq milliards de milliards de positions, en jeu reel on se retrouve tres souvent dans des memes positions qui ne doivent pas etre si importes qu’il semblerait.
    Et si on pouvait faire une base de donnees de positions et leurs suites, un calculateur trouvant un maximum de similitudes de situations en fonction de la position, des couleurs et du trait pourra plus rapidement donner une reponse optimum voire du « coup qui tue ».

    Sinon, Eob serait il possible d’avoir une version de ton replayer ?

    • Je ne pense pas que ce soit faisable avec les moyens informatiques actuels: le nombre de positions différentes possibles à envisager est beaucoup trop important.
      Pour chacune de ces positions, il faudrait calculer le meilleur coup et le stocker dans une hashtable.
      Donc un temps de calcul des meilleurs coups rédhibitoire et un volume de donnés impossible à stocker.

  5. Oui, désolé, je sais que ça ne change pas l’ordre de grandeur du résultat, je voulais juste justifier la difficulté qu’il y a à faire un compte très précis du nombre de configurations.
    À ce sujet, Peer Sommerlund m’avait interrogé il y a neuf ans sur le nombre de configurations à 4 noires et 1 blanche (en rapport avec les fins de partie, où il ne reste qu’une bille à piéger). Je n’avais pas compris qu’il supposait les noires connectées entre elles (auquel cas il y a 8 025 configurations, ou 10 704 si l’on rajoute certaines configurations un peu déconnectées qui sont nécessaires pour éjecter en un nombre de coups optimal), donc j’avais fastidieusement compté qu’il y en avait 2 482 058.

    On est d’accord pour le trait, mais ça n’altère pas ce que j’ai dit : si le trait est au joueur de couleur C, une configuration comme Domination n’est pas équivalente à sa version aux couleurs inversées. Autrement dit, le trait est une propriété qu’on peut considérer comme codée par la couleur des billes, c’est-à-dire que comme tu le dis, inverser les couleurs revient à inverser le trait. Conclusion, Mogwai compte les configurations (sans symétrie) 12 fois et non 24. Personnellement, je considère que pour toute configuration, Noir a le trait.

    Après, on est là aussi d’accord, dans plein de situations, il y a des billes qui ne sont pas très importantes pour l’évaluation.

    Pour mon replayer, il me faut une adresse de courrier électronique 🙂 et il faut que tu aies Java (ça ne devrait pas poser trop de problèmes). Par contre, récemment, un ami l’a essayé sur Windows 8 et ça n’a pas marché… Si jamais ça fonctionne, on peut y jouer à Offboard, Traboulet, Siam et Push (comme jeux où il faut pousser des lignes de pièces). Et ça utilise beaucoup de RAM parce que c’est un peu mal fait ^^

      • En fait, le programme est suffisamment général pour permettre de lui rajouter (presque) n’importe quel jeu. Évidemment, il est plus adapté pour « abstract board games ».
        Concernant les jeux où il y a des pièces à pousser en ligne (ou en flèche, d’ailleurs), j’ai oublié de citer Aboyne, GIPF, Epaminondas et Volo (je n’ai pas mis ce dernier dans la version que j’ai envoyée, car sur le moment il y avait un bug). De façon générale, c’est le genre de jeu le plus facile à ajouter dans le cadre de ce programme, puisque à la base il n’était fait que pour Abalone et ses semblables (Offboard et Traboulet).

  6. @FightClub : comme son nom le suggère, mon replayer est un programme qui permet de jouer (contre soi-même, actuellement), d’enregistrer une partie (avec variations, commentaires, éditions, etc.), de revoir une partie enregistrée, d’exporter des images, etc.
    Un jour ce sera beaucoup plus user-friendly que maintenant, où la plupart des actions (sauf le jeu, le parcours et les éditions basiques) se font uniquement par commande dans le terminal…

  7. Concernant le nombre de positions possibles avec toutes les billes sur le plateau, j’ai mis deux profs de maths sur le coup et voici la réponse de l’un d’entre eux (brillant joueur de go, au passage) :
    – sans compter les symétries, C(61,14)*C(61-14,14), soit 7 691 345 017 184 661 959 133 000.
    – à symétrie près, ça fait 7 691 345 017 114 144 852 558 800 positions.
    Ce qui confirme le résultat trouvé par Mogwai 🙂
    Donc en plus d’être un jeu « olympique », abalone est aussi un jeu « astronomique » !
    Sidérant, non ? ^^

  8. Oui, ça fait beaucoup ! 🙂
    Mais il manque la partie intéressante de la réponse : d’où sort le résultat final (en tenant compte des symétries) ?

Répondre

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.