Inscription / Connexion Nouveau Sujet
Quelle bonne Combinaison ?
Bonjour,
Il s'agit de mon 1er post, j'espère donc être au bon endroit!
Depuis 3 ans, j'ai le même problème au mois d'Octobre. Et je n'ai toujours pas trouvé LA solution. C'est un problème du "quotidien" mais je pense qu'il peut être résolu grâce aux Maths!
Mon problème donc:
J'organise un speed meeting (un peu comme le speed dating mais professionnel). Le principe : un certain nombre de personnes se rencontrent. Disons 72 pour l'exemple (mais 81 serait l'idéal pour moi). Ils peuvent donc être organisés de la manière suivante : 8 tables de 9 ou 9 tables de 8 bien sûr. (ou 9 tables de 9 si 81). La difficulté : chaque participant doit rencontrer tout le monde UNE et UNE seule fois.
J'ai donc organisé ça sous forme d'une matrice. Pour 81 personnes, ma matrice a 81 lignes et 9 colonnes. Une ligne représente un candidat, une colonne représente une rotation et dans chaque case le numéro de la table où se trouve le participant.
Exp: Ligne 48 : 2-4-6-8-1-3-5-7-9 => Le candidat 48 se trouve à la table 4 lors de la 2e rotation.
Ligne 75: 1-4-3-5-7-2-9-6-8 => Les candidats 48 et 71 ne se croisent qu'une seule fois : lors de la rotation 2 et autour de la table 4.
Je n'ai pas un niveau super élevé en Maths (je me suis arrêté en 2e année à la fac). Mais, si je me souviens bien : il doit s'agir d'un problème de combinaisons. Ces dernières devant être toutes différentes. Si on fait une combinaison de 9 parmi 9, on doit arriver à plus de 300.000.
Mais parmi ces 300.000 combien peut-il en exister pour résoudre ce problème? Et quelles sont-elles?
Pouvez-vous m'aidez à trouver la réponse ou sur la manière de trouver la réponse (algorithme,...)?
Mais Aidez-moi SVP!
PS: J'ai déjà une solution pour 42 pers. qui fonctionne avec 7tables de 6 personnes et 8 rotations. (Mais la dernière rotation s'organise en 6tables de 7 personnes) Je peux vous la fournir si besoin.
Maxime.
Bonjour,
Ce problème est régulièrement abordé, et connu sous le non de tournoi toutes rondes:
Pour le résoudre, on peux utiliser la méthode du ruban:
et ici, les tables toutes faites:
Bonjour,
Les 2 solutions proposées sont intéressantes, mais je ne pense pas qu'elles répondent à la problématique.
En effet dans le cas de ces "tournois", les participants se rencontrent en 1 contre 1. Or dans mon cas, si on prend l'exemple de 81 participants et de 9 tables, chaque candidat rencontre 8 autres candidats par table et par rotation. De ce fait, il est beaucoup plus "facile" de se croiser plusieurs fois.
Merci pour votre aide.
Bonjour,
On trouve des problèmes de ce genre sous le nom de problème des écolières (de Kirkman) etc
avec des généralisations à des groupements de plus de 2 (triplets de Steiner et de Kirkman, problèmes de "social golfer" etc)
trouver de la littérature là dessus en français n'est pas simple.
une intro là
(pour approfondir, peut-tre suivre les liens et références)
je suis tombé là dessus (en anglais) :
qui semble extrêmement complet (mais je n'ai pas tout lu)
ça a l'air bien "joufflu" : c'est une thèse.
dans la pratique on se limite à des groupes de 4 sinon ça devient de plus en plus ardu (le problème est NP-complet)
mais rien ne devrait empêcher de chercher avec des groupes de 8 ou 9 si on dispose de temps machine pour faire tourner les algorithmes !!
des simplifications "fortuites" permettent de tomber "à la main" sur des solutions dans certains cas particuliers
il peut ne pas y avoir de solution (Cf le problème des 36 officiers)
les groupements par 2 et par 3 se font "à la main" (écolières de Lucas et de Kirkman) sans difficulté, à part la patience. (voir "récréations mathématiques" tome II de E.Lucas)
Cliquez pour afficher
Bonjour,
Merci pour toutes ces infos.
Effectivement, il semblerait que la solution se trouve ici.
Il ne reste "plus" qu'à m'y mettre!
A vérifier...
Pour un cas où le nombre de participants N est un carré parfait : N = n*n
On organise les rencontres en n tables de n...
Le nombre de rencontres est : R = CN,2 = N(N-1)/2 = n²(n²-1)/2
Le nombre de rencontres par jour est : r = n.Cn,2 = n.n(n-1)/2
Le nombre de journées est donc : J = R/r = n+1
Exemple, pour N=81, il y aura donc J=10 journées.
Piste :
1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2
1 3 3 3 3 3 3 3 3 3
1 4 4 4 4 4 4 4 4 4
...
1 9 9 9 9 9 9 9 9 9
2 1 9 8 7 6 5 4 3 2
2 2 1 9 8 7 6 5 4 3
2 3 2 1 9 8 7 6 5 4
2 4 3 2 1 9 8 7 6 5
...
2 9 8 7 6 5 4 3 2 1
3 1 9 8 7 6 5 4 3 2
3 2 1 9 8 7 6 5 4 3
3 3 2 1 9 8 7 6 5 4
3 4 3 2 1 9 8 7 6 5
...
3 9 8 7 6 5 4 3 2 1
.
.
.
9 1 9 8 7 6 5 4 3 2
9 2 1 9 8 7 6 5 4 3
9 3 2 1 9 8 7 6 5 4
9 4 3 2 1 9 8 7 6 5
...
9 9 8 7 6 5 4 3 2 1
Je n'ai pas tout vérifié...
... mais ça a l'air de marcher
.Une solution géométrique : 81, c'est le nombre d'éléments du plan affine sur le corps à 9 éléments.
Si on fixe une direction de droite, alors il y a neuf droites du plan ayant cette direction et chaque droite a neuf éléments.
Il y a dix directions de droites (le J=10 de Le Dino).
Deux points distincts du plan donnent une et une seule direction de droite.
Donc tout va bien.
Concrètement, le corps est le corps engendré sur
par
vérifiant
. Voici la table de ses éléments (côté gauche c'est fait pour multiplier, côté droit c'est fait pour additionner).
Les 10 jours sont indexés par les éléments de
et
.
Les 9 tables sont indexées par les éléments de
Chacun des 81 participants est représenté par un couple d'éléments de .
Au jour n° , la table n°
est composée des
pour
.
Au jour n° , la table n°
est composée des
pour
.
Une sortie calculée en SAGE. Ca revient sans doute plus ou moins à la liste de LeDino).
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 1]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 1]
[4, 4, 4, 4, 4, 4, 4, 4, 4, 1]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 1]
[6, 6, 6, 6, 6, 6, 6, 6, 6, 1]
[7, 7, 7, 7, 7, 7, 7, 7, 7, 1]
[8, 8, 8, 8, 8, 8, 8, 8, 8, 1]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 1]
[1, 7, 8, 9, 2, 3, 4, 5, 6, 2]
[2, 5, 7, 3, 6, 4, 9, 8, 1, 2]
[3, 1, 6, 8, 4, 7, 5, 2, 9, 2]
[4, 2, 1, 7, 9, 5, 8, 6, 3, 2]
[5, 4, 3, 1, 8, 2, 6, 9, 7, 2]
[6, 8, 5, 4, 1, 9, 3, 7, 2, 2]
[7, 3, 9, 6, 5, 1, 2, 4, 8, 2]
[8, 9, 4, 2, 7, 6, 1, 3, 5, 2]
[9, 6, 2, 5, 3, 8, 7, 1, 4, 2]
[1, 8, 9, 2, 3, 4, 5, 6, 7, 3]
[2, 7, 3, 6, 4, 9, 8, 1, 5, 3]
[3, 6, 8, 4, 7, 5, 2, 9, 1, 3]
[4, 1, 7, 9, 5, 8, 6, 3, 2, 3]
[5, 3, 1, 8, 2, 6, 9, 7, 4, 3]
[6, 5, 4, 1, 9, 3, 7, 2, 8, 3]
[7, 9, 6, 5, 1, 2, 4, 8, 3, 3]
[8, 4, 2, 7, 6, 1, 3, 5, 9, 3]
[9, 2, 5, 3, 8, 7, 1, 4, 6, 3]
[1, 9, 2, 3, 4, 5, 6, 7, 8, 4]
[2, 3, 6, 4, 9, 8, 1, 5, 7, 4]
[3, 8, 4, 7, 5, 2, 9, 1, 6, 4]
[4, 7, 9, 5, 8, 6, 3, 2, 1, 4]
[5, 1, 8, 2, 6, 9, 7, 4, 3, 4]
[6, 4, 1, 9, 3, 7, 2, 8, 5, 4]
[7, 6, 5, 1, 2, 4, 8, 3, 9, 4]
[8, 2, 7, 6, 1, 3, 5, 9, 4, 4]
[9, 5, 3, 8, 7, 1, 4, 6, 2, 4]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 5]
[2, 6, 4, 9, 8, 1, 5, 7, 3, 5]
[3, 4, 7, 5, 2, 9, 1, 6, 8, 5]
[4, 9, 5, 8, 6, 3, 2, 1, 7, 5]
[5, 8, 2, 6, 9, 7, 4, 3, 1, 5]
[6, 1, 9, 3, 7, 2, 8, 5, 4, 5]
[7, 5, 1, 2, 4, 8, 3, 9, 6, 5]
[8, 7, 6, 1, 3, 5, 9, 4, 2, 5]
[9, 3, 8, 7, 1, 4, 6, 2, 5, 5]
[1, 3, 4, 5, 6, 7, 8, 9, 2, 6]
[2, 4, 9, 8, 1, 5, 7, 3, 6, 6]
[3, 7, 5, 2, 9, 1, 6, 8, 4, 6]
[4, 5, 8, 6, 3, 2, 1, 7, 9, 6]
[5, 2, 6, 9, 7, 4, 3, 1, 8, 6]
[6, 9, 3, 7, 2, 8, 5, 4, 1, 6]
[7, 1, 2, 4, 8, 3, 9, 6, 5, 6]
[8, 6, 1, 3, 5, 9, 4, 2, 7, 6]
[9, 8, 7, 1, 4, 6, 2, 5, 3, 6]
[1, 4, 5, 6, 7, 8, 9, 2, 3, 7]
[2, 9, 8, 1, 5, 7, 3, 6, 4, 7]
[3, 5, 2, 9, 1, 6, 8, 4, 7, 7]
[4, 8, 6, 3, 2, 1, 7, 9, 5, 7]
[5, 6, 9, 7, 4, 3, 1, 8, 2, 7]
[6, 3, 7, 2, 8, 5, 4, 1, 9, 7]
[7, 2, 4, 8, 3, 9, 6, 5, 1, 7]
[8, 1, 3, 5, 9, 4, 2, 7, 6, 7]
[9, 7, 1, 4, 6, 2, 5, 3, 8, 7]
[1, 5, 6, 7, 8, 9, 2, 3, 4, 8]
[2, 8, 1, 5, 7, 3, 6, 4, 9, 8]
[3, 2, 9, 1, 6, 8, 4, 7, 5, 8]
[4, 6, 3, 2, 1, 7, 9, 5, 8, 8]
[5, 9, 7, 4, 3, 1, 8, 2, 6, 8]
[6, 7, 2, 8, 5, 4, 1, 9, 3, 8]
[7, 4, 8, 3, 9, 6, 5, 1, 2, 8]
[8, 3, 5, 9, 4, 2, 7, 6, 1, 8]
[9, 1, 4, 6, 2, 5, 3, 8, 7, 8]
[1, 6, 7, 8, 9, 2, 3, 4, 5, 9]
[2, 1, 5, 7, 3, 6, 4, 9, 8, 9]
[3, 9, 1, 6, 8, 4, 7, 5, 2, 9]
[4, 3, 2, 1, 7, 9, 5, 8, 6, 9]
[5, 7, 4, 3, 1, 8, 2, 6, 9, 9]
[6, 2, 8, 5, 4, 1, 9, 3, 7, 9]
[7, 8, 3, 9, 6, 5, 1, 2, 4, 9]
[8, 5, 9, 4, 2, 7, 6, 1, 3, 9]
[9, 4, 6, 2, 5, 3, 8, 7, 1, 9]
J'aurais plus confiance dans la liste de Robot que dans la mienne...
Les 5 premiers individus sont OK avec ma méthode.
Mais par la suite ma proposition ne convient plus...
... elle est trop naïve.
Au fait, non, la liste de LeDino ne va pas du tout : si on regarde la première ligne commençant par 2 et la première ligne commençant par 3, les candidats correspondant se retrouvent à la même table 9 fois sur 10 !
Avec plaisir,
La même méthode marche avec ,
, \mathbb{F}_{11}, \mathbb{F}_{13}, \mathbb{F}_16}.
On peut bien sûr à partir de là trouver des solutions pour d'autres nombres de participants. Par exemple en enlevant 7 participants à partir de la solution pour 49 participants en 8 tours de 7 tables de 7 (construite sur \mathbb{F}_7), on trouve une solution pour 42 particpants avec 7 tours de 7 tables de 6 et un tour de 6 tables de 7.
On peut aussi trazvailler avec des droites dans un espace à trois dimensions ou plus : par exemple, pour 64 participants, 21 tours de 16 tables de 4 de telle sorte que chaque participant rencontre chaque autre participant une et une seule fois.
Bonsoir,
Maxime (ou Cornichon), si tu consultes ce message, je suis intéressée par ton résultat pour 42 personnes. Je dois réaliser les groupes et rotations pour 36 personnes, je n'y parviens pas, et malheureusement je ne comprends pas les explications publiées.
Bonjour,
Le premier conseil serait de voir les sites donnés par weierstrass
On remarque que la meilleure rencontre est la poignée de main:
Si on est deux -->1 poignée , à 3--->3 serrages, à 4--->6 serrages ----à n --->n(n-1)/2.
Donc à 36 il faudra 36x35/2 =630 contacts (heureusement que 18 seront simultanés)
Si on limite à 10 minutes chaque rencontre ,la séquence prendra donc 5h 50.
Reste à organiser les passages.....
Merci,
Le truc c'est que ce ne sont pas des rencontres 1 contre 1. Il s'agit de faire des tables de 6 personnes (ou 5 ou 7, selon ce qu'il y a de plus facile à organiser), où à chaque rotation de table, chacun rencontre de nouvelles personnes. Idéalement donc, personne ne se croise 2 fois, et après 6 ou 7 rotations, tout le monde aura rencontré tout le monde.
j'ai essayé la théorie du ruban...
C'est assez fastidieux car si on veut des tables on doit éliminer tous le doublons...
Exemple table 123456 il ne faudra plus trouver de couples 23 24 25 26 34 35 36 45 45 56 dans une autre table.
Nous avons un certain Littlefox qui va certainement nous pondre un joli Python 
J'espère que quelqu'un trouvera une méthode facile...
En tables de 6 ,j'ai fait les 4 premières ,il faut ensuite combiner en évitant les doublons...
Annuler
connectez vous