Petit problème de combinatoire
Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

Petit problème de combinatoire



  1. #1
    RomVi

    Petit problème de combinatoire


    ------

    Bonjour à tous

    Aujourd'hui une collègue m'a posé une colle : Son fils prépare un weekend d'intégration. Il va former 10 équipes qui s'affronteront en 1 contre 1 sur 5 jeux différents.
    - Toutes les équipes doivent se rencontrer, il y aura donc 9 rencontres.
    - Les 5 jeux sont joués en simultanés et il n'est pas possible de faire 2 rencontres au même moment sur le même jeu.
    Le but est d'essayer de répartir au mieux, pour éviter qu'une équipe joue au même jeu trop souvent.

    J'ai réussi a faire un planning ou chaque équipe rencontre les 9 autres, mais en ce qui concerne la répartition des jeux je pensais que chaque équipe jouerai à chaque jeu 1 ou 2 fois, mais je ne suis pas parvenu à cet objectif, au mieux, en tâtonnant, les équipes jouent chaque jeu 1, 2 ou 3 fois.
    Est-ce seulement possible ?

    Je suppose qu'il existe une méthode permettant de bien répartir les jeux, mais je ne l'ai pas trouvée...

    -----

  2. #2
    ansset
    Animateur Mathématiques

    Re : Petit problème de combinatoire

    Bjr
    Citation Envoyé par RomVi Voir le message
    Aujourd'hui une collègue m'a posé une colle : Son fils prépare un weekend d'intégration. Il va former 10 équipes qui s'affronteront en 1 contre 1 sur 5 jeux différents.
    - Toutes les équipes doivent se rencontrer, il y aura donc 9 rencontres.
    - Les 5 jeux sont joués en simultanés et il n'est pas possible de faire 2 rencontres au même moment sur le même jeu.
    je ne suis pas sûr de bien comprendre.
    il y a donc 9 rencontres x 5 jeux donc 45 confrontations ?
    quand il y a rencontre, c'est toute l'équipe X qui rencontre l'équipe Y ?
    pourquoi devrait il y avoir plusieurs rencontres entre X et Y sur un même jeu ? ( si c'est le cas )
    Dernière modification par ansset ; 04/10/2019 à 19h15.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  3. #3
    RomVi

    Re : Petit problème de combinatoire

    En effet en me relisant je me rend compte que je me suis assez mal exprimé...

    Il y a 9 rencontres pour chaque équipe (chaque équipe joue une fois contre tous les autres). En continu on a donc 5 x 2 équipes qui s'affrontent sur 5 jeux différents.
    et au total 5 x 9 = 45 matchs seront disputés. Voici par exemple un planning possible pour ces rencontres (équipes numérotés de 1 à 10) :
    Code:
    1 - 10
    2 - 9
    3 - 8
    4 - 7
    5 - 6
    
    1 - 9
    10 - 8
    2 - 7
    3 - 6
    4 - 5
    
    1 - 8
    9 - 7
    10 - 6
    2 - 5
    3 - 4
    
    1 - 7
    8 - 6
    9 - 5
    10 - 4
    2 - 3
    
    1 - 6
    7 - 5
    8 - 4
    9 - 3
    10 - 2
    
    1 - 5
    6 - 4
    7 - 3
    8 - 2
    9 - 10
    
    1 - 4
    5 - 3
    6 - 2
    7 - 10
    8 - 9
    
    1 - 3
    4 - 2
    5 - 10
    6 - 9
    7 - 8
    
    1 - 2
    3 - 10
    4 - 9
    5 - 8
    6 - 7
    La difficulté est de répartir au mieux les jeux pour que chaque équipe passe au moins 1 fois par chaque jeu, et pas trop souvent sur le même. Intuitivement je pense qu'il est possible de trouver une répartition permettant de jouer soit 1 fois soit 2 fois à chaque jeu, mais je ne sais pas comment le trouver autrement qu'en tâtonnant, et c'est peut être impossible.

  4. #4
    ansset
    Animateur Mathématiques

    Re : Petit problème de combinatoire

    Citation Envoyé par RomVi Voir le message
    Il y a 9 rencontres pour chaque équipe (chaque équipe joue une fois contre tous les autres). En continu on a donc 5 x 2 équipes qui s'affrontent sur 5 jeux différents.
    et au total 5 x 9 = 45 matchs seront disputés.
    y'a un pb de nb de rencontres.
    soit 1 jeu.
    si toutes les équipes se rencontrent sur ce seul jeu, il y a déjà 45 matchs pour que toutes les confrontations aient lieu.
    on peut prendre ton tableau en exemple.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

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

    Re : Petit problème de combinatoire

    Non chaque équipe doit rencontrer toutes les autres et chaque équipe doit passer au moins une fois par chaque jeu, mais il n'est pas nécessaire que toutes les rencontres possibles passent par tous les jeux.

  7. #6
    ansset
    Animateur Mathématiques

    Re : Petit problème de combinatoire

    OK, et que doit on optimiser ?
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  8. #7
    RomVi

    Re : Petit problème de combinatoire

    mon but est de faire passer chaque équipe soit 1 soit 2 fois par jeu (pour éviter trop de répétitions). J'ai construis un tableau mais au mieux les équipes passent 1, 2 ou 3 fois par jeu.

  9. #8
    vgondr98

    Re : Petit problème de combinatoire

    tableauequipe.jpg
    Je crois que c'est bon.

  10. #9
    RomVi

    Re : Petit problème de combinatoire

    Si j'ai bien compris le décompte en bas de colonne à droite le jeu bleu sera pratiqué 8 fois et le jaune 10 fois, donc ça ne fonctionne pas, vu qu'on a 9 rounds pendant lesquels les 5 jeux sont joués simultanément. Il faut forcément 9 parties jouées pour chaque jeu.

  11. #10
    vgondr98

    Re : Petit problème de combinatoire

    tableauequipe.jpg
    Bonjour, j'ai changer la couleur en BD de jaune à bleu, ce qui fait un jeu bleu en plus pour B et un jeu bleu en plus pour D, ainsi qu'un jeu jaune en moins pour B et un jeu jaune en moins pour D.

  12. #11
    RomVi

    Re : Petit problème de combinatoire

    Visiblement ça marche cette fois, il ne reste plus qu'à trouver comment répartir toutes ces parties en 9 rounds contenant chaque fois 5 jeux différents.
    Est-ce que tu utilises un algorithme, ou tu as essayé au hasard ?

  13. #12
    vgondr98

    Re : Petit problème de combinatoire

    J'ai commencé par la ligne A, où il n'y avait quasi aucune contrainte (à part qu'il fallait au maximum 2 jeux identiques pour les 9 rencontres).
    J'ai décompté les couleurs pour les dix équipes.
    Je suis passé à la ligne B, qui était déjà plus contrainte mais c'était simple car les équipes B,C,D,E,F,G,H,I et J n'étaient associés qu'a un seul jeu à ce moment-là.
    J'ai décompté les couleurs pour les dix équipes.
    Je suis passé à la ligne C, qui était encore plus contraint car certaines équipes avaient deux jeux associés de la même couleur.

    Et ainsi de suite..

    A un moment cela à coincé au niveau de la ligne G (il me semble) car je devais mettre la couleur verte entre l'équipe J et G or le J avait déjà deux couleurs vertes.
    Cependant, j'ai pu intervertir les couleurs verte et rouge entre BG et BJ.

    Après comme tu le sais, j'avais un excès de jeux jaunes et un déficit de jeux bleus que j'ai pu résoudre en changeant un jeu jaune par un jeu bleu.

    Ce qui est marrant, c'est que pour que cela marche, il semblerait qu'il faille que le nombre total de partie (45) soit le produit du nombre de jeu (5) par le nombre de rencontres pour une équipe donnée (9).

  14. #13
    RomVi

    Re : Petit problème de combinatoire

    J'ai tenté de ranger les rencontres avec mon tirage plus haut et ça ne colle pas.
    La difficulté est qu'il faut minimiser le nombres de répétition des jeux par équipes, mais il faut aussi que les jeux ne soient pas joués en double lors d'un même round.
    Images attachées Images attachées

  15. #14
    vgondr98

    Re : Petit problème de combinatoire

    tableauequipe.jpg
    J'ai réussi a organiser 6 round mais après cela a coincé car j'avais une même équipe qui participait à 2 jeux lors d'un même round ce qui n'est pas possible.

  16. #15
    LeMulet

    Re : Petit problème de combinatoire

    Une idée peut-être :

    Session 1
    A1F
    B2G
    C3H
    D4I
    E5J

    On fait tourner le "cercle" ABCDEFGHIJ (dans le sens lévogyre ici, mais qu'importe)

    Session 2 :
    F1G
    A2H
    B3I
    C4J
    D5E

    Etc.

    Session 3 :
    G1H
    F2J
    A3I
    B4E
    C5D

    Session 4 :
    H1J
    G2I
    F3E
    A4D
    B5C

    Session 5 :
    J1I
    H2E
    G3D
    F4C
    A5B

    Session 6 :
    I1E
    J2D
    H3C
    G4B
    F5A

    Session 7 :
    E1D
    I2C
    J3B
    H4A
    G5F

    Session 8 :
    D1C
    E2B
    I3A
    J4F
    H5G

    Session 9 :
    C1B
    D2A
    E3F
    I4G
    J5H
    Bonjour, et Merci.

  17. #16
    LeMulet

    Re : Petit problème de combinatoire

    Presque.
    Il y en a qui jouent deux fois contre le même adversaire...
    Bonjour, et Merci.

  18. #17
    vgondr98

    Re : Petit problème de combinatoire

    Je me suis trompe au 4ème où je fait jouer D 2 fois.

  19. #18
    vgondr98

    Re : Petit problème de combinatoire

    tableauequipe.jpg
    Je ne sais pas ce que tu en penses, là j'ai un léger excès de jeu orange.
    Il est peut-être possible de permuter les couleurs dans le dernier round HI DJ CG AE BF pour voir si cet excès disparaît.

  20. #19
    RomVi

    Re : Petit problème de combinatoire

    Ça me semble déjà bien optimisé.
    Je pense qu'il doit exister une méthode pour logique organiser les jeux et les équipes, mais je ne l'ai pas trouvée.

Discussions similaires

  1. Problème combinatoire
    Par Absaloth dans le forum Mathématiques du supérieur
    Réponses: 18
    Dernier message: 30/09/2014, 18h36
  2. Petit problème de combinatoire simple
    Par invite0cea7419 dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 19/03/2007, 17h04
  3. Petit soucis de proba combinatoire
    Par invite88fa9f2c dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 04/10/2006, 23h36
  4. Petit pb. de combinatoire.
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 23/07/2006, 12h29
  5. Problème combinatoire.
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 23/05/2004, 10h08