Bonjour,
Je cherche à organiser un tournoi de Puerto Rico à 11 joueurs.
J'aimerai structurer les tables de manière à ce que :
* chaque joueur joue 5 fois (une fois dans chaque position : premier, second, troisième, quatrième ou dernier dans l'ordre du tour)
* chaque joueur rencontre chacun des autres participants 2 fois exactement
* 11 parties exactement se déroulent
Je voulais initialement résoudre cette équation à plusieurs inconnus sous Excel avec le solveur mais je baisse les bras après plusieurs tentatives infructueuses.
Est-ce que quelqu'un a déjà vu un tournoi organisé de cette manière ? Connaissez vous une grille toute faite lui correspondant ou une méthode de résolution pour l'obtenir ?
P.S. La question subsidiaire est "est-ce qu'une telle grille est mathématiquement possible ?" à 11 joueurs ou en faudrait-il plus ?
P.S.2. Le problème a déjà une solution pour 13 joueurs à 4 joueurs par table (chaque joueur rencontrant chaque autre une fois et une seule).
Là, brute de pomme, je dirai que ton problème a trop de contraintes... J'y réfléchis dès que j'ai le temps...
Afin de démontrer que je ne fabule pas complétement, voici la version pour 13 parties à 4 joueurs :
1 / 2 / 3 / 4
2 / D / 8 / 6
3 / C / 5 / 8
4 / B / C / D
5 / 6 / 4 / 7
6 / A / 1 / C
7 / 8 / B / 1
8 / 4 / A / 9
9 / 1 / D / 5
A / 5 / 2 / B
B / 9 / 6 / 3
C / 7 / 9 / 2
D / 3 / 7 / A
Actorios dit:Est-ce que quelqu'un a déjà vu un tournoi organisé de cette manière ? Connaissez vous une grille toute faite lui correspondant ou une méthode de résolution pour l'obtenir ?
Non.
Actorios dit:P.S. La question subsidiaire est "est-ce qu'une telle grille est mathématiquement possible ?" à 11 joueurs ou en faudrait-il plus ?
En fait, je pense qu'il faut commencer par là. Je n'ai pas de démonstration rigoureuse, mais il me semble qu'il n'y a pas assez de joueurs, parce que la contrainte "rencontrer tous les autres joueurs 2 fois exactement" est très forte.
Quelques éléments de ma réflexion rapide (potentiellement fausse) : d'abord, on ne se soucie pas de l'ordre dans les tables - c'est une contrainte supplémentaire qui permettra éventuellement de disqualifier certaines solutions apparentes, mais vu que le résultat est sans doute qu'il n'y a pas de solution même sans cette contrainte...
On s'intéresse d'abord au joueur A, dont l'une des parties est ABCDE. Quel est le nombre maximum d'adversaires communs qu'il a entre deux parties ? Ce nombre est 1 au minimum (il ne joue pas toutes ses parties avec des adversaires différents, vu qu'on sait qu'il joue deux fois avec chacun), et 4 au maximum.
Si A joue sa deuxième partie avec 4 adversaires communs, c'est à nouveau ABCDE. Je ne démontre pas que ça ne marche pas - ça me semble évident (j'ai prévenu que ce n'était pas rigoureux - on verra plus tard si c'est nécessaire).
S'il a 3 adversaires communs, sa deuxième partie est ABCDF. Il lui reste à jouer avec E et F (une fois chacun) et G, H, I, J, K (deux fois chacun).
Je ne démontre pas que ça ne marche pas, mais ça se fait (je suppose, à 99,9%) de la même manière que ci-dessous pour 2 adversaires communs, continuez à lire.
S'il a deux adversaires communs, sa deuxième partie est ABCFG. Il lui reste à jouer avec D, E, F, G (une fois chacun) et H, I, J, K (deux fois chacun). Les cas sont les suivants :
- D et E jouent ensemble, F et G aussi : on arrive à ABCDE, ABCFG, ADEHI, AFGJK, AHIJK (cas 1)
- D et E jouent ensemble, mais pas F et G : ABCDE, ABCFG, ADEHI, AFHJK, AGHJK (cas 2)
- D et E jouent ensemble avec F, et G tout seul : ABCDE, ABCFG, ADEFH, AGIJK, AHIJK --> 3 adversaires communs (IJK), ce qui contredit l'hypothèse
- D et F jouent ensemble, E et G aussi : ABCDE, ABCFG, ADFHI, AEGJK, AHIJK (les autres cas donnent 3 adversaires communs) (cas 3)
- D et F jouent ensemble, E et G séparément : ABCDE, ABCFG, ADFHI, AEHJK, AFIJK (cas 4)
On s'intéresse alors aux parties restantes de B. Il a déjà joué ses deux parties avec A et C (ABCDE et ABCFG) , il lui reste à jouer trois parties (une fois avec D, E, F et G et deux fois avec H, I, J, K).
Dans le cas 1, J et K on déjà joué ensemble deux fois - ils ne peuvent donc plus rejouer ensemble. Or on ne peut pas placer deux joueurs deux fois, à des tables différentes à chaque fois, sur 3 tables (il faudrait 4 tables - ou qu'un joueur joue deux fois à la même table). Exit le cas 1.
Pour le cas 2, pareil avec J et K.
Pour le cas 3, pareil avec J et K.
Pour le cas 4, pareil avec J et K.
Donc A ne peut pas avoir au maximum deux adversaires communs à deux parties.
S'il a un seul adversaire commun à chaque fois, sa deuxième partie est ABFGH. Ses trois autres parties doivent donc être avec I, J et K (deux fois chacun) et C, D, E, F, G, H (une fois chacun). C, D et E sont nécessairement sur des tables différentes, sinon on est dans le cas où A a deux adversaires communs à deux de ses parties, ce qui contredit l'hypothèse. Pareil pour F, G et H. Donc on a :
ABCDE, ABFGH, ACFxx, ADGxx et AEHxx
(peu importe si C et F sont ensemble - on les renomme si nécessaire).
Reste à caser deux fois chacun I, J et K dans les x, ce qui donne par exemple :
ABCDE, ABFGH, ACFIJ, ADGIK, AEHJK
Et donc A avait deux adversaires communs entre deux de ses parties (AIJ - ou AIK ou AJK), donc c'est raté.
Bref, j'ai vaguement démontré que ce n'était pas possible. Si tu acceptes que A joue une seule fois avec certains joueurs (mais au minimum une fois, quand même), ça a l'air plus faisable, mais je ne garantis rien...
Si tu changes le nombre de joueurs dans ton tournoi, je ne sais pas non plus si tu obtiens une solution.
William
PS : PR, c'est mieux à 4 qu'à 5, à mon avis.
PPS : Si ce que j'ai écrit est incompréhensible, c'est peut-être parce que je n'ai pas rédigé les paragraphes dans l'ordre de lecture, désolé.
Je pense que ce genre de problème à une solution mais il y a une donnée que tu n'as pas évoqué qui rend le pb complexe (insoluble à mon avis) :
Vu qu'il y a au moins 2 tables en simultanée, un joueur ne peut pas être présent sur les 2 tables au même moment.
Admettons cette répartition de départ, des 5 premières parties :
Table 1Partie 1Partie 2Partie 3
J111110
J22111
J3325
J4436
J5541
Table 2Partie 1Partie 2
J165
J276
J387
J498
J5109
A partir du joueur 3 de la 6ème partie tu ne trouveras personne qui cumule les critères (surtout le fait d'être non présent sur la table 1)
Histoire de respecter un certain équilibre, fait un truc comme ça :
Table 1Partie 1Partie 2Partie 3Partie 4Partie 5
J112345
J2111234
J31011123
J49101112
J58910111
Table 2Partie 1Partie 2Partie 3Partie 4Partie 5Partie 6
J167891011
J25678910
J3456789
J4345678
J5234567
Pour ceux qui aiment les casse-tête, voilà où j'en suis :
Il faut faire rentrer 4, 7, 9, 10, 11 dans la grille en lieu et place des x en réalisant des permutations qui permettent de satisfaire aux contraintes :
* que des chiffres ou lettres différentes par ligne
* chacune des 55 combinaisons 2 à 2 de chiffre / lettre doit apparaître 2 fois et 2 fois seulement.
Il faut forcément déshabiller Paul pour habiller Jacques mais rien n'interdit de penser que l'on puisse aboutir.
ABCDE
12345
12967
141189
1361011
187105
259811
234810
2671011
3579x
368xx
456xx
Ca ressemble fort à un problème d'ordonnancement ton truc, je travaille là dessus sur ma thèse
Je pourrais essayer de formaliser le problème pour le donner à manger à un solveur, mais pas avant la semaine prochaine...
scand1sk dit:Ca ressemble fort à un problème d'ordonnancement ton truc, je travaille là dessus sur ma thèse
Je pourrais essayer de formaliser le problème pour le donner à manger à un solveur, mais pas avant la semaine prochaine...
Ecoute, je suis preneur... Je vais arrêter de me torturer. Une machine travaillera plus efficacement que moi et parviendra à la solution si une telle solution existe. A défaut, on pourra savoir si l'on peut combler plus de trous que je ne l'ai fait.
Merci de ta proposition et merci à William et Richard de s'être penché sur le problème.
Actorios dit:Pour ceux qui aiment les casse-tête, voilà où j'en suis :
Il faut faire rentrer 4, 7, 9, 10, 11 dans la grille en lieu et place des x en réalisant des permutations qui permettent de satisfaire aux contraintes :
* que des chiffres ou lettres différentes par ligne
* chacune des 55 combinaisons 2 à 2 de chiffre / lettre doit apparaître 2 fois et 2 fois seulement.
A partir de ce que tu donnes, ce n'est pas possible.
ABCDE
1361011
2671011
3579x
368xx
456xx
Tu dois caser 10 et 11 parmi les x. Un des deux au moins est donc sur l'une des deux dernières lignes citées (vu qu'il n'y a qu'une seule place en dehors de ces deux lignes). Or chacun des deux a déjà joué deux fois avec 6, et 6 est présent sur les deux lignes.
Donc ton début de solution ne permet pas de résoudre le problème, il faut remonter en arrière.
William (qui reste persuadé que ce n'est pas possible)
Sinon, ça doit pouvoir se résoudre un peu comme un Sudoku en fait
scand1sk dit:Sinon, ça doit pouvoir se résoudre un peu comme un Sudoku en fait
Ca n'en est pas loin, en effet... Mais pas tout à fait.
Ce n'est pas une matrice carrée et il y a la contrainte du "2 rencontres avec chacun en plus"
Wlam dit:Actorios dit:Pour ceux qui aiment les casse-tête, voilà où j'en suis :
Il faut faire rentrer 4, 7, 9, 10, 11 dans la grille en lieu et place des x en réalisant des permutations qui permettent de satisfaire aux contraintes :
* que des chiffres ou lettres différentes par ligne
* chacune des 55 combinaisons 2 à 2 de chiffre / lettre doit apparaître 2 fois et 2 fois seulement.
A partir de ce que tu donnes, ce n'est pas possible.
ABCDE
1361011
2671011
3579x
368xx
456xx
Tu dois caser 10 et 11 parmi les x. Un des deux au moins est donc sur l'une des deux dernières lignes citées (vu qu'il n'y a qu'une seule place en dehors de ces deux lignes). Or chacun des deux a déjà joué deux fois avec 6, et 6 est présent sur les deux lignes.
Donc ton début de solution ne permet pas de résoudre le problème, il faut remonter en arrière.
William (qui reste persuadé que ce n'est pas possible)
Oui, oui, c'est exact, il faut backtracker pour reprendre quelquechose de faisable.
-- Guillaume, qui ne sait pas si c'est impossible mais qui est certain que l'on peut se rapprocher encore un peu plus de l'idéal... Et pourquoi pas l'atteindre (oui, oui, je l'avoue : je suis têtu).
Après 10 minutes de réflexion intense, je me suis dit que c'était un problème tout con de permutations de {1,...,11}, et de dérangements. 5 minutes de plus et j'avais la conviction que des simples permutations circulaires avaient toutes les chances de faire l'affaire.
20 minutes de vérification plus tard, ça donne :
1 B A 8 5
2 1 B 9 6
3 2 1 A 7
4 3 2 B 8
5 4 3 1 9
6 5 4 2 A
7 6 5 3 B
8 7 6 4 1
9 8 7 5 2
A 9 8 6 3
B A 9 7 4
Je te laisse voir l'algorithme de construction.
grolapinos dit:Après 10 minutes de réflexion intense, je me suis dit que c'était un problème tout con de permutations de {1,...,11}, et qu'il suffisait d'en trouver 4 qui changent toutes les positions. 5 minutes de plus et j'avais la conviction que des simples permutations circulaires avaient toutes les chances de faire l'affaire.
20 minutes de vérification plus tard, ça donne :
1 B A 8 5
2 1 B 9 6
3 2 1 A 7
4 3 2 B 8
5 4 3 1 9
6 5 4 2 A
7 6 5 3 B
8 7 6 4 1
9 8 7 5 2
A 9 8 6 3
B A 9 7 4
Je te laisse voir l'algorithme de construction.
Lecture intéressée... Manipulation fébrile pour passer la matrice dans ma feuille Excel de contrôle... Tous les voyants sont au vert !
Gaël : dans mes bras !
Astuce et observation valent mieux que savants calculs et permutation au petit bonheur la chance... Chapeau !
Tu vois, William, il y avait bien une solution ! (je n'étais pas sûr de mon coup, remarque bien)
Je crois que je l'ai aussi mais c'est trop tard !!!!! 
En tout cas j'en ai la tête qui fume encore. 
grolapinos pour ta trouvaille plus rapide que la mienne.
Actorios si tu en as d'autres, reviens par ici 
Au cas où :
ABCDE
BCFGH
CFDIJ
FDGEK
DGIHA
GIEJB
IEHKC
EHJAF
HJKBD
JKACG
KABFI
latrufe31 dit:
En tout cas j'en ai la tête qui fume encore.
ABCDE
BCFGH
CFDIJ
FDGEK
DGIHA
GIEJB
IEHKC
EHJAF
HJKBD
JKACG
KABFI
Bien joué, Fabrice...
Oui, moi aussi, j'ai souffert sur le problème...
A grand renfort de feuille Excel alors qu'il suffisait (entre gros guillemets) d'avoir les yeux en face des trous.
Actorios dit:Tu vois, William, il y avait bien une solution ! (je n'étais pas sûr de mon coup, remarque bien)
On dirait bien... Mais même en relisant mon raisonnement à tête reposée, je n'arrive pas à trouver ce qui ne va pas (dans le cas où il n'y a qu'un adversaire en commun entre deux parties). En plus, ça doit être une erreur évidente...
William
Wlam dit:Actorios dit:Tu vois, William, il y avait bien une solution ! (je n'étais pas sûr de mon coup, remarque bien)
On dirait bien... Mais même en relisant mon raisonnement à tête reposée, je n'arrive pas à trouver ce qui ne va pas (dans le cas où il n'y a qu'un adversaire en commun entre deux parties). En plus, ça doit être une erreur évidente...
William
Je pense que c'est le fait que les matchs n'aient pas lieu simultanément qui t'a mis dans l'erreur. Sur BGG où j'ai également posté la question, j'ai eu la remarque que ce mode de tournoi était inefficace au possible puisque pratiquement aucune partie ne peut se dérouler en parallèle et qu'un tel tournoi demanderait à programmer les parties à l'avance.
C'est en partie vrai, mais ce mode de tournoi équitable et sans crescendo (contrairement au système suisse où l'on affronte des adversaires d'autant plus fort que l'on emporte des parties) convient parfaitement à un tournoi au long cours sur une année tel qu'il se pratique à St Ju en jeux () :
- peu demandant : relativement peu de matchs par joueur
- convivial : l'occasion de jouer avec tout le monde
- étalé dans le temps : un tournoi qui se déroule lentement pour que l'on puisse en apprécier chaque partie (même si l'on n'y participe pas) et qui puisse être qualifié de championnat "annuel"
- relativement court malgré cela : il n'y a que 11 parties à jouer au total
() Oui, là, je vends un peu ma soupe
Bravo à Grolapinos et à latrufe31
Chapeau 
C'est pas mal comme principe de tournoi je trouve ça se prète bien au tournoi dans des club il est vrai...
Y a plus qu'à l'essayer! 
Sinon le système de tounoi à la "suisse" C'est un système ou les parties se font par rang de victoire, (se rencontrent ceux qui ont le même nombre de victoire.)
Nous pour notre tournoi de Puerto on avait fait une moulinette complexe, Avec un premier match de classement (pour déterminer des tête de série.) puis un championnat on sortent les 8 premiers...
En tous cas je garde ce post avec des dispositifs astucieux pour faire jouer :
13 personnes, pour un jeu à 4, avec 4 rencontres par joueur
11 personnes, pour un jeu à 5, avec 5 rencontres par joueur
Chacun jouant à toute les positions de départ...