Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Un problème de dénombrement



  1. #1
    chedev

    Un problème de dénombrement


    ------

    Bonjour à tous

    Je cherche à générer des grilles pour un jeu que j'ai mis on-line sur internet dans une formule "tournoi".
    Pour vous faire une idée, ce jeu est ici

    Dans le jeu "normal", les grilles sont générées à la volée de façon aléatoire: certaines ont une solution, d'autres pas.

    Dans le mode "tournoi", les grilles sont préparées à l'avance par un générateur-solveur que j'ai fabriqué.
    Il ne retient que des grilles qui ont une solution.
    Et tous les concurrents d'un tournoi jouent les mêmes grilles, ce qui rend la compétition équitable.

    A raison de 20 grilles dans le tournoi actuel (hebdomadaire), il m'en faut 1000 par an.
    Mais j'envisage d'augmenter la fréquence et d'avoir donc besoin d'un stock bien plus grand.

    Ma question:
    La génération d'une grille se faisant en répartissant aléatoirement 4 exemplaires de 30 symboles différents sur une grille de 120 cases (10 x 12), combien y a-t-il de configurations de jeu possibles?

    On pourrait éventuellement affiner la question en considérant comme identiques les grilles de même structure après rotation ou symétrie.

    Mes (très) lointains souvenirs des calculs de probabilités sont bien trop flous pour que j'arrive à résoudre ce problème.

    Pouvez-vous m'y aider?

    Merci d'avance.

    -----

  2. Publicité
  3. #2
    Ledescat

    Re : Un problème de dénombrement

    Bonsoir.

    Il faut déjà choisir 4 cases parmi 120 qui vont recevoir un symbole (si j'ai bien compris).
    Il y a C120,4=120!/(4!116!) possibilités.
    Pour chacun de ces cas, on doit placer sur une de ces 4 cases un des 30 symboles. On a donc 30^4 choix pour 4 cases placées.

    En tout, on a, si j'ai pas trop mal compté, C120,4*30^4=6 653 801 700 000 grilles différentes.

    Cordialement.
    Cogito ergo sum.

  4. #3
    chedev

    Re : Un problème de dénombrement

    Merci Ledescat

    Ma préoccupation étant de savoir si je ne courrais pas trop de risques, en générant 10 à 20 000 grilles, d'avoir des doublons, ton calcul a tout pour me rassurer!

    Mais je ne me suis peut-être pas très bien exprimé en posant mon problème et je pense qu'il doit y avoir beaucoup moins de grilles différentes.

    Je n'ai pas l'esprit assez clair ce soir pour mieux formuler ma question.
    Je ne prendrai donc maintenant qu'une illustration de mon doute:
    Pour une grille donnée, chaque symbole occupe un ensemble de 4 cases.
    Les grilles différentes sont celles où les 30 ensembles de 4 cases qui composent le territoire sont différents.
    Pour une disposition donnée de ces 30 ensembles, peu importe le symbole qu'il y a à l'intérieur de chacun des ensembles.
    Le résultat visuel est bien sûr différent, la problématique pour enlever les symboles par paire est la même.

    Si j'ai été plus clair, peux-tu me confirmer (ou pas) que ton calcul est établi sur les bonnes hypothèses?
    Sinon, j'essayerai de mieux formuler ma question.

    Bonne soirée

  5. #4
    gentelman_net

    Re : Un problème de dénombrement

    Citation Envoyé par Ledescat Voir le message
    Bonsoir.

    Il faut déjà choisir 4 cases parmi 120 qui vont recevoir un symbole (si j'ai bien compris).
    Il y a C120,4=120!/(4!116!) possibilités.
    Pour chacun de ces cas, on doit placer sur une de ces 4 cases un des 30 symboles. On a donc 30^4 choix pour 4 cases placées.

    En tout, on a, si j'ai pas trop mal compté, C120,4*30^4=6 653 801 700 000 grilles différentes.

    Cordialement.
    salut
    je suis d'accord avec toi pour la reponse jusqu'au dernier passage que j'ai bien compris car d'aprés mes petits calculs il fallait multiplier par 30! à la place 30^4
    parceque pour les premiers 4 cases on a le choix entre 30 symboles .
    les deuxièmes 4 ceses on a le choix entre 29 symbles.
    .
    .
    les derniers 4 cases on a 1 symboles.
    en plus j'ai pas bien compris pourquoi tu t'interesse aux 4 cases choisi de toute façon ils auront le même symbole donc on ne peux les distinguer.
    si ce n'est pas comme ça alors j'ai mal compris le jeu.

  6. A voir en vidéo sur Futura
  7. #5
    chedev

    Re : Un problème de dénombrement

    Si la nuit m'a bien porté conseil, voilà comment je reformulerais mon problème:
    De combien de façons peut-on peut-on découper un territoire de 120 cases en 30 parcelles de 4 cases.

    Le fait que l'on remplisse ces parcelles avec des symboles différents ne change en effet rien à l'affaire.

    Du coup, la réponse n'est-elle tout simplement pas C120,4?
    (que j'avoue ne plus savoir comment calculer)

    Et si on considère qu'une solution est identique aux 4 rotations de 90° que l'on peut lui faire subir, ainsi qu'à un retournement, il faut diviser ce résultat par 8.

    Suis-je dans le vrai?

  8. #6
    Médiat

    Re : Un problème de dénombrement

    Je dirais :


    Avec la symétrie H et V on divise par 4 ; la rotation 90 ne marche que pour les carrés ce qui n'est pas le cas de 120.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  9. Publicité
  10. #7
    Ledescat

    Re : Un problème de dénombrement

    Citation Envoyé par gentelman_net Voir le message
    en plus j'ai pas bien compris pourquoi tu t'interesse aux 4 cases choisi de toute façon ils auront le même symbole donc on ne peux les distinguer.
    si ce n'est pas comme ça alors j'ai mal compris le jeu.
    C'est que j'avais compris que la grille de départ était toute blanche, sauf 4 cases dans lesquelles on pouvait choisir parmi 30 symboles, ce qui n'est apparemment pas le cas.
    Cogito ergo sum.

Discussions similaires

  1. Dénombrement
    Par maseru dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 13/01/2008, 18h08
  2. probléme denombrement
    Par magic-men dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 17/11/2007, 17h08
  3. Au secoursss! Problème de dénombrement (sup)
    Par M I L A S dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 07/11/2007, 14h54
  4. problème dénombrement HEC
    Par kayash dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 19/11/2006, 22h13
  5. Problème de dénombrement-probabilités
    Par eljeys dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 24/08/2005, 12h56