Sim (jeu)
Pour les articles homonymes, voir SIM.
Sim est un jeu de papier et crayon pour deux joueurs.
Règle modifier
Six points (sommets) sont dessinés. Chaque point est relié à chaque autre point par une ligne (arête).
Deux joueurs à tour de rôle colorient une arête non encore coloriée, chacun ayant une couleur différente. Chaque joueur essaye d'éviter la création d'un triangle formé uniquement de leur couleur (seuls les triangles dont les sommets coïncident avec les sommets du graphe comptent ; les intersections d'arêtes ne sont pas concernées) : le joueur qui termine un tel triangle perd immédiatement.
Analyse modifier
La théorie de Ramsey peut être utilisée pour montrer qu'aucun jeu de Sim ne peut terminer par un match nul. Plus précisément, puisque le nombre de Ramsey R(3,3)=6, toute bi-coloration du graphe complet sur 6 sommets (K,6), doit contenir un triangle monochromatique, et ne permet donc pas de match nul. Cela peut aussi s'appliquer à n'importe quel super-graphe de K6. Pour une autre preuve qu'il doit forcément y avoir un triangle d'une couleur, voir le Théorème sur les amis et les étrangers.
La recherche par ordinateur a permis de vérifier que le second joueur peut gagner au jeu de Sim avec un jeu parfait, mais le fait de trouver une stratégie parfaite que les humains peuvent facilement mémoriser reste un problème ouvert.
Le jeu de Sim est un exemple de jeu de Ramsey. D'autres jeux de Ramsey sont possibles. Par exemple, les joueurs peuvent être autorisés à colorier plus d'une seule arête au cours de leur tour. Un autre jeu de Ramsey similaire à Sim et lié au nombre de Ramsey R(4,4)=18, et qui à nouveau ne peut pas s'achever par un nul, est joué sur 18 sommets et les 153 arêtes qui les relient. Les deux joueurs doivent éviter d'obtenir un tétraèdre monochromatique (en trois dimensions, une pyramide à quatre faces triangulaires).
Le nombre de Ramsey R(3,3,3)=17 implique que tous les trois-colorations du graphe complet sur 17 sommets doit contenir un triangle monochromatique. Un jeu de Ramsey correspondant utilise des crayons de trois couleurs. Une approche peut avoir trois joueurs qui s'affrontent, tandis qu'une autre serait de permettre à deux joueurs à tour de rôle de sélectionner l'une des trois couleurs pour peindre une arête du graphe, jusqu'à ce qu'un joueur perde en achevant un triangle monochromatique. Trouver des stratégies gagnantes pour ces variantes est probablement hors de portée.
Un rapport technique[1] par Wolfgang Slany est disponible en ligne, avec de nombreuses références à la littérature sur le jeu de Sim, et revient sur l'introduction du jeu par Gustavus J. Simmons[2] en 1969[3], y compris les épreuves et les estimations de la difficulté ainsi que la complexité de calcul du jeu de Sim et d'autres jeux de Ramsey.
Logiciel modifier
Un applet Java auto-améliorative incluant son code source est disponible[4] pour jouer en ligne contre un ordinateur.
Une application, y compris son code source dans le langage de programmation multi-plate-forme visuel Catrobat est disponible[5] pour jouer contre son smartphone.
Références modifier
- Graph Ramsey Games by Wolfgang Slany at arXiv
- Charles-É. Jean, « Sim », Dictionnaire de mathématiques récréatives, sur Récréomath (consulté le )
- Simmons, Gustavus J. "The game of SIM," J. Recreational Mathematics, 2(2), 1969, pp. 66.
- Java applet page, including source code
- App for smartphones, including source code
