{"id":1865,"date":"2026-03-22T12:21:59","date_gmt":"2026-03-22T08:21:59","guid":{"rendered":"https:\/\/iremi.univ-reunion.fr\/?p=1865"},"modified":"2026-04-23T13:17:46","modified_gmt":"2026-04-23T09:17:46","slug":"variation-sur-un-concept-daviezri-fraenkel","status":"publish","type":"post","link":"https:\/\/iremi.univ-reunion.fr\/?p=1865","title":{"rendered":"Variation sur un concept d&rsquo;Aviezri Fraenkel"},"content":{"rendered":"\n<p>Dans cet article, on va s&rsquo;int\u00e9resser \u00e0 des <a href=\"https:\/\/iremi.univ-reunion.fr\/?p=586\">jeux impartiaux<\/a>, dont l&rsquo;arch\u00e9type est le jeu de Nim. Dans ce jeu, on dispose de jetons, dispos\u00e9s en tas comme ici (jeu de Nim \u00e0 deux tas) :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"343\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0305.jpg\" alt=\"\" class=\"wp-image-1867\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0305.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0305-300x143.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Ci-dessous ce jeu sera not\u00e9 (3,2) car il y a un tas de 3 jetons et un tas de 2 jetons. Un coup du jeu de Nim consiste \u00e0 <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>choisir un tas (par exemple celui de droite),<\/li>\n\n\n\n<li>en retirer autant de jetons qu&rsquo;on souhaite (par exemple un seul) :<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"347\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0306.jpg\" alt=\"\" class=\"wp-image-1868\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0306.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0306-300x145.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Celui qui prend le dernier jeton gagne le jeu. Ci-dessus ce sera celui qui a jou\u00e9 en premier, parce qu&rsquo;il dispose maintenant d&rsquo;une strat\u00e9gie gagnante (jouer dans un tas ce que son adversaire vient de jouer dans l&rsquo;autre tas). Mais dans le cas g\u00e9n\u00e9ral, on calcule ce qu&rsquo;on appelle <strong>nombre de Grundy<\/strong> du jeu, et ce nombre (un entier r\u00e9sumant le jeu) se calcule r\u00e9cursivement sur le graphe du jeu. Pour construire ce graphe, on assimilera la position<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"357\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0307.jpg\" alt=\"\" class=\"wp-image-1869\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0307.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0307-300x149.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>avec la position<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"340\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0308.jpg\" alt=\"\" class=\"wp-image-1870\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0308.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/DSC_0308-300x142.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>car l&#8217;emplacement des tas importe peu pour la strat\u00e9gie gagnante, tout ce qu&rsquo;il faut conna\u00eetre, c&rsquo;est la hauteur de chacun des tas. Les deux positions ci-dessus seront toutes deux not\u00e9es (2,1) : on convient de mettre dans l&rsquo;ordre d\u00e9croissant les hauteurs des tas de jetons. De plus, on ne note pas les tas devenus vides. Avec ces conventions le graphe du jeu est :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1-1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:670px\" aria-label=\"Contenu embarqu\u00e9 nim1.\"><\/object><a id=\"wp-block-file--media-7c26a812-12ac-4831-93b3-a428f9bda63a\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1-1.pdf\">nim1<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1-1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-7c26a812-12ac-4831-93b3-a428f9bda63a\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>Le calcul des nombres de Grundy de chaque sommet donne la valeur 1 pour le sommet qui est en haut. Ce nombre de Grundy \u00e9tant diff\u00e9rent de 0, il y a une strat\u00e9gie gagnante consistant \u00e0 viser un sommet dont le nombre de Grundy est nul, et ce sommet est (2,2). L&rsquo;id\u00e9e fondamentale de Fraenkel est d&rsquo;utiliser ce graphe, non pour <strong><em>mod\u00e9liser<\/em><\/strong> le jeu, mais pour <strong><em>jouer<\/em><\/strong>, par le biais d&rsquo;un pion, commun aux deux joueurs, et qu&rsquo;\u00e0 chaque tour de jeu on glisse le long d&rsquo;une fl\u00e8che, jusqu&rsquo;\u00e0 ce que ce ne soit plus possible (parce que le pion est tomb\u00e9 dans un <em>puits<\/em> en bas), auquel cas le dernier \u00e0 avoir boug\u00e9 le pion (le joueur qui a fait tomber le pion dans le puits) a gagn\u00e9 le jeu. Quelques d\u00e9finitions :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>un graphe orient\u00e9 est <strong><em>connexe<\/em><\/strong> s&rsquo;il est d&rsquo;un seul tenant (on ne peut pas le s\u00e9parer en deux morceaux sans enlever un sommet ou un arc),<\/li>\n\n\n\n<li>un <strong><em>cycle<\/em><\/strong> est un chemin permettant d&rsquo;aller d&rsquo;un sommet \u00e0 lui-m\u00eame en suivant des fl\u00e8ches,<\/li>\n\n\n\n<li>un graphe n&rsquo;ayant pas de cycle est un <strong><em>graphe acyclique<\/em><\/strong>,<\/li>\n\n\n\n<li>un sommet o\u00f9 n&rsquo;arrive aucune fl\u00e8che est une <strong><em>source<\/em><\/strong>,<\/li>\n\n\n\n<li>un sommet dont ne part aucune fl\u00e8che est un <strong><em>puits<\/em><\/strong>.<\/li>\n<\/ul>\n\n\n\n<p>Les jeux de Fraenkel se jouent sur des graphes orient\u00e9s connexes et acycliques. De tels graphes ont au moins une source et au moins un puits. Pour savoir o\u00f9 mettre le pion au d\u00e9part, il faut qu&rsquo;ils n&rsquo;y ait qu&rsquo;une source, et le jeu est plus facile \u00e0 jouer s&rsquo;il n&rsquo;y a qu&rsquo;un puits, comme sur ce graphe d&rsquo;enfant (dont le nombre de Grundy est 2) :<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/images-archive.math.cnrs.fr\/freeze\/\/img\/png\/nim0.png\" alt=\"\" \/><\/figure>\n\n\n\n<p>On \u00e9nonce alors le<\/p>\n\n\n\n<p><mark style=\"background-color:#f1eecd\" class=\"has-inline-color\"><strong>Th\u00e9or\u00e8me de Fraenkel<\/strong> : tout jeu impartial est \u00e9quivalent \u00e0 un jeu o\u00f9 on d\u00e9place un pion sur un graphe orient\u00e9 connexe acyclique ayant une source et un puits, le pion \u00e9tant plac\u00e9 au d\u00e9part sur la source et le gagnant \u00e9tant celui qui am\u00e8ne le pion dans le puits.<\/mark><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Atelier de cr\u00e9ation de jeux impartiaux<\/h3>\n\n\n\n<p>Un atelier de cr\u00e9ation de jeux impartiaux revient \u00e0 un atelier de dessins de graphes orient\u00e9s, ce qui sugg\u00e8re ce genre de tournoi :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>chaque enfant se voit remettre du papier et un crayon, et dessine un graphe orient\u00e9,<\/li>\n\n\n\n<li>si le graphe comporte un cycle, il est disqualifi\u00e9,<\/li>\n\n\n\n<li>s&rsquo;il comporte plusieurs sources ou plusieurs puits, il est p\u00e9nalis\u00e9,<\/li>\n\n\n\n<li>les graphes restants sont alors class\u00e9s par nombre de Grundy, et le graphe ayant le plus grand nombre de Grundy est gagnant du tournoi.<\/li>\n<\/ul>\n\n\n\n<p>La r\u00e9compense pour le gagnant est l&rsquo;organisation d&rsquo;un tournoi de jeu impartial sur son graphe. Un outil d&rsquo;aide \u00e0 la conception de graphes orient\u00e9s est disponible <a href=\"https:\/\/alainbusser.github.io\/Nirina974\/digraphs.html\">en ligne sur Nirina974<\/a>. Un b\u00eata-test a permis \u00e0 une enfant de 8 ans de rapidement produire ce graphe dont le nombre de Grundy est 3 :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe5.pdf\" type=\"application\/pdf\" style=\"width:100%;height:410px\" aria-label=\"Contenu embarqu\u00e9 grafe5.\"><\/object><a id=\"wp-block-file--media-97e52dfb-519e-4a72-ac82-89b6305334a3\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe5.pdf\">grafe5<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe5.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-97e52dfb-519e-4a72-ac82-89b6305334a3\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>(le d\u00e9part est en bas \u00e0 gauche). Et voici un graphe cr\u00e9\u00e9 par Aviezri Fraenkel (il a deux puits, colori\u00e9s en vert ; son nombre de Grundy est 0) :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Contenu embarqu\u00e9 fraenkel1.\"><\/object><a id=\"wp-block-file--media-7bddd260-d154-48c3-a03d-74b6827561a8\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel1.pdf\">fraenkel1<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-7bddd260-d154-48c3-a03d-74b6827561a8\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Autres concepts d&rsquo;Aviezri Fraenkel<\/h2>\n\n\n\n<p>Fraenkel s&rsquo;est beaucoup int\u00e9ress\u00e9 au calcul de nombres de Grundy sur certains graphes ayant un ou plusieurs cycles comme<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel2.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Contenu embarqu\u00e9 fraenkel2.\"><\/object><a id=\"wp-block-file--media-6606550a-f27c-4c6e-9e38-a41c6306d575\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel2.pdf\">fraenkel2<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel2.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-6606550a-f27c-4c6e-9e38-a41c6306d575\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>dont le nombre de Grundy est aussi \u00e9gal \u00e0 0.<\/p>\n\n\n\n<p>Conway et Fraenkel ont class\u00e9 les interactions possibles entre pions sur un graphe orient\u00e9 connexe (avec ou sans cycle) :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Les pions peuvent \u00eatre des <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Boson\">bosons<\/a>, auquel cas il n&rsquo;y a pas de limite sup\u00e9rieure au nombre de pions pr\u00e9sents sur un sommet du graphe.<\/li>\n\n\n\n<li>Les pions peuvent s&rsquo;exclure mutuellement comme des <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Fermion\">fermions<\/a>, ce qui occasionne des blocages ; Conway attribue \u00e0 un certain Welter la cr\u00e9ation d&rsquo;un cas particulier de ce genre de jeu, o\u00f9 le graphe est form\u00e9 de sommets align\u00e9s, chacun  \u00e9tant reli\u00e9 \u00e0 tous les sommets qui sont \u00e0 sa gauche.<\/li>\n\n\n\n<li>Les pions peuvent se comporter comme des <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Antimati%C3%A8re\">antiparticules<\/a> : lorsqu&rsquo;un pion arrive sur un sommet d\u00e9j\u00e0 occup\u00e9,  les deux pions sont retir\u00e9s du jeu.<\/li>\n\n\n\n<li>les pions peuvent \u00eatre de deux couleurs, et avoir un comportement mixte : un pion ne peut pas aller sur un sommet o\u00f9 se trouve un pion de la m\u00eame couleur, mais peut occuper un sommet o\u00f9 se trouve un pion de l&rsquo;autre couleur, auquel cas il va le <a href=\"https:\/\/en.wikipedia.org\/wiki\/Clobber\">clobber<\/a>, c&rsquo;est-\u00e0-dire qu&rsquo;il prend sa place en le retirant du graphe, comme aux \u00e9checs.<\/li>\n<\/ul>\n\n\n\n<p>Dans ce dernier cas, Fraenkel a con\u00e7u un jeu impartial :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel4.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Contenu embarqu\u00e9 fraenkel4.\"><\/object><a id=\"wp-block-file--media-5f818da0-172e-400c-91b7-c6aecaf895bf\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel4.pdf\">fraenkel4<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel4.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-5f818da0-172e-400c-91b7-c6aecaf895bf\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>et m\u00eame un jeu partisan (chaque joueur ayant ses propres 7 pions) sur un graphe pas enti\u00e8rement orient\u00e9 :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel5.pdf\" type=\"application\/pdf\" style=\"width:100%;height:800px\" aria-label=\"Contenu embarqu\u00e9 fraenkel5.\"><\/object><a id=\"wp-block-file--media-3ba5268a-597c-4e2c-af0c-5144e8d555d2\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel5.pdf\">fraenkel5<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2015\/11\/fraenkel5.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-3ba5268a-597c-4e2c-af0c-5144e8d555d2\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>Ce jeu a \u00e9t\u00e9 commercialis\u00e9 dans les ann\u00e9es 1970 sous le nom de <em>on the line<\/em>, puis dans les ann\u00e9es 2000 sous le nom de <em>arrows<\/em>. Dans ce dernier cas, le plateau de jeu \u00e9tait en bois, avec des creux pour les pions, lesquels \u00e9taient des billes, transparentes pour un joueur, et m\u00e9talliques pour l&rsquo;autre joueur. Sur le site <a href=\"https:\/\/mathpickle.com\/\">https:\/\/mathpickle.com\/<\/a> (consacr\u00e9 \u00e0 l&rsquo;enseignement des maths par la ludologie), <a href=\"https:\/\/mathpickle.com\/project\/arrows\/\">des jeux similaires<\/a> ont \u00e9t\u00e9 propos\u00e9s sur des graphes plus simples :<\/p>\n\n\n\n<p><a href=\"https:\/\/mathpickle.com\/wp-content\/uploads\/2015\/08\/Arrows-Game.pdf\">https:\/\/mathpickle.com\/wp-content\/uploads\/2015\/08\/Arrows-Game.pdf<\/a><\/p>\n\n\n\n<p>Certains de ces graphes semblent permettre d&rsquo;introduire la notion de parit\u00e9 (apparemment en cycle 2).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Variation sur un th\u00e8me de Fraenkel<\/h2>\n\n\n\n<p>Revenons un peu en arri\u00e8re, l\u00e0 o\u00f9 Fraenkel sugg\u00e8re de mettre plusieurs pions sur un graphe orient\u00e9 connexe acyclique, le mode d&rsquo;interaction des pions faisant partie de la r\u00e8gle du jeu. La <a href=\"https:\/\/iremi.univ-reunion.fr\/?p=625\">carte des cartes<\/a> donne envie d&rsquo;explorer cette variante :<\/p>\n\n\n\n<p><mark style=\"background-color:#c1f8f8\" class=\"has-inline-color\">Avant de jouer, on place un pion sur l&rsquo;unique source de chaque composante connexe d&rsquo;un graphe orient\u00e9 acyclique. Un tour de jeu consiste \u00e0 choisir un des pions qui n&rsquo;est pas encore bloqu\u00e9, puis le bouger suivant une fl\u00e8che. Le premier qui ne peut plus bouger a perdu le jeu.<\/mark><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Les composantes connexes<\/h3>\n\n\n\n<p>En vrai, avant de jouer, on construit les composantes connexes du graphe, par exemple en les puisant d&rsquo;une collection \u00e9tablie lors de l&rsquo;activit\u00e9 d\u00e9crite dans la partie <em>atelier de cr\u00e9ation de jeux impartiaux<\/em> plus haut, ou comme mod\u00e8les de jeux impartiaux connus comme par exemple le jeu de <a href=\"https:\/\/iremi.univ-reunion.fr\/?p=689\">Sowing<\/a> impartial (graphes simplifiables en mettant ensemble tous les puits et en tenant compte des sym\u00e9tries) :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4a.pdf\" type=\"application\/pdf\" style=\"width:100%;height:320px\" aria-label=\"Contenu embarqu\u00e9 is4a.\"><\/object><a id=\"wp-block-file--media-031f7425-2990-4458-bf93-a3e05c59c9a9\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4a.pdf\">is4a<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4a.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-031f7425-2990-4458-bf93-a3e05c59c9a9\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4b.pdf\" type=\"application\/pdf\" style=\"width:100%;height:330px\" aria-label=\"Contenu embarqu\u00e9 is4b.\"><\/object><a id=\"wp-block-file--media-11263703-53a9-4750-9e57-f037bb2833f8\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4b.pdf\">is4b<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is4b.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-11263703-53a9-4750-9e57-f037bb2833f8\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is6d.pdf\" type=\"application\/pdf\" style=\"width:100%;height:270px\" aria-label=\"Contenu embarqu\u00e9 is6d.\"><\/object><a id=\"wp-block-file--media-9f6349dd-2861-4024-ad4b-25e9fda4898e\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is6d.pdf\">is6d<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/is6d.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-9f6349dd-2861-4024-ad4b-25e9fda4898e\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/deuxplusun.pdf\" type=\"application\/pdf\" style=\"width:100%;height:200px\" aria-label=\"Contenu embarqu\u00e9 deuxplusun.\"><\/object><a id=\"wp-block-file--media-c287e1ca-d7e6-4387-a027-f1f95c691fca\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/deuxplusun.pdf\">deuxplusun<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/deuxplusun.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-c287e1ca-d7e6-4387-a027-f1f95c691fca\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>ou alors des graphes orient\u00e9s connexes acycliques cr\u00e9\u00e9s sans chercher \u00e0 mod\u00e9liser un autre jeu impartial, juste en dessinant le graphe, comme par exemple le graphe d&rsquo;enfant vu en d\u00e9but d&rsquo;article, que voici rendu en Python :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe4.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Contenu embarqu\u00e9 grafe4.\"><\/object><a id=\"wp-block-file--media-82568fd4-efa6-46d8-b513-3218c9f250c0\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe4.pdf\">grafe4<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/grafe4.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-82568fd4-efa6-46d8-b513-3218c9f250c0\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>ou, enfin, des graphes qui ont \u00e9t\u00e9 cr\u00e9\u00e9s sp\u00e9cialement pour cette activit\u00e9 <em>cartes des cartes impartiales<\/em> :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2023\/02\/cartesg1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:810px\" aria-label=\"Contenu embarqu\u00e9 cartesg1.\"><\/object><a id=\"wp-block-file--media-df70200a-dd96-4017-bd51-6cc62194ba2b\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2023\/02\/cartesg1.pdf\">cartesg1<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2023\/02\/cartesg1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-df70200a-dd96-4017-bd51-6cc62194ba2b\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>Le jeu est \u00e0 deux joueurs :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>les deux joueurs choisissent des graphes orient\u00e9s connexes acycliques ayant une source et un puits parmi la collection (iles choisissent des cartes dans le jeu de cartes),<\/li>\n\n\n\n<li>puis posent ces cartes sur la carte des cartes (la table : ils construisent le plateau de jeu avant de jouer),<\/li>\n\n\n\n<li>puis posent un pion \u00e0 chaque d\u00e9part d&rsquo;une carte,<\/li>\n\n\n\n<li>et, enfin, jouent : chacun son tour, d\u00e9place un des pions en lui faisant suivre une fl\u00e8che.<\/li>\n\n\n\n<li>Le premier qui ne peut plus bouger (parce que tous les pions sont dans des puits) a perdu. <\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Application au jeu de Nim<\/h3>\n\n\n\n<p>On rappelle que pour le jeu de Nim \u00e0 deux tas (3,2), le graphe poss\u00e8de 9 sommets :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:720px\" aria-label=\"Contenu embarqu\u00e9 nim1.\"><\/object><a id=\"wp-block-file--media-74af198c-65e8-4015-a7d0-421737721534\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1.pdf\">nim1<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-74af198c-65e8-4015-a7d0-421737721534\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>Mais la version \u00e0 deux composantes connexes n&rsquo;en a plus que 7 (par contre il y a deux pions) :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim32.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Contenu embarqu\u00e9 nim32.\"><\/object><a id=\"wp-block-file--media-b9aa6a90-9494-48af-90ae-713b4e0dff74\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim32.pdf\">nim32<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim32.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-b9aa6a90-9494-48af-90ae-713b4e0dff74\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>et on peut simplifier encore : comme la composante connexe de gauche a un nombre de Grundy \u00e9gal \u00e0 3 (c&rsquo;est un tas de 3 jetons) et celle de droite a un nombre de Grundy \u00e9gal \u00e0 2 (c&rsquo;est un tas de 2 jetons), le jeu est, d&rsquo;apr\u00e8s les th\u00e9or\u00e8mes de Sprague-Grundy et de Fraenkel, LE jeu de nombre de Grundy 1 (Nim-somme de 3 et 2), c&rsquo;est-\u00e0-dire ce jeu (\u00e0 seul pion pour le coup) :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim4.pdf\" type=\"application\/pdf\" style=\"width:100%;height:390px\" aria-label=\"Contenu embarqu\u00e9 nim4.\"><\/object><a id=\"wp-block-file--media-c2fd80f8-967a-4d21-82e9-44ef66a06514\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim4.pdf\">nim4<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/nim4.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-c2fd80f8-967a-4d21-82e9-44ef66a06514\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Comment jouer\/faire jouer<\/h2>\n\n\n\n<p>Comme il s&rsquo;agit de jeux \u00e0 deux joueurs, chaque table de jeu occupe deux joueurs. Mais en plus il y a une table centrale o\u00f9 se trouvent pos\u00e9es des cartes, dont chacune porte un graphe orient\u00e9 connexe acyclique avec une source et un puits. Les joueurs d&rsquo;une table de jeu commencent par choisir quelques cartes de la table centrale (en essayant de ne pas frustrer les joueurs d&rsquo;autres tables) puis les posent sur leur table de jeu, en mettant un pion au d\u00e9part de chaque carte.<\/p>\n\n\n\n<p>Puis ils jouent au jeu qu&rsquo;ils ont cr\u00e9\u00e9, c&rsquo;est-\u00e0-dire que chacun son tour bouge un pion le long d&rsquo;une fl\u00e8che. Lorsque le jeu est termin\u00e9 (plus aucun pion ne peut bouger, donc celui qui devait jouer a perdu), ils notent les nombres de Grundy des cartes choisies et leur Nim-somme.<\/p>\n\n\n\n<p>Ensuite ils pr\u00e9parent un autre jeu, en choisissant parmi ces op\u00e9rations :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>enlever une carte jug\u00e9e inint\u00e9ressante,<\/li>\n\n\n\n<li>ajouter une carte qui semblait manquer,<\/li>\n\n\n\n<li>\u00e9changer une carte peu int\u00e9ressante contre une carte plus int\u00e9ressante (comme au poker) au niveau de la table centrale. <\/li>\n<\/ul>\n\n\n\n<p>Apr\u00e8s quelques tours de ce m\u00e9tajeu, on compare les jeux les plus int\u00e9ressants, et les nombres de Grundy obtenus. La version sans nombres de Grundy est plus simple mais fait appel au jugement humain pour ranger les jeux construits par qualit\u00e9 subjective.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lors du s\u00e9minaire IREMI du 22 avril 2026<\/h2>\n\n\n\n<p>Voici des jeux jug\u00e9s int\u00e9ressants par leurs cr\u00e9ateurs :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"540\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_142556.jpg\" alt=\"\" class=\"wp-image-2081\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_142556.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_142556-300x225.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Les nombres de Grundy des 5 termes de cette somme sont :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><\/td><td>4<\/td><td><\/td><td>3<\/td><td><\/td><\/tr><tr><td>3<\/td><td><\/td><td>3<\/td><td><\/td><td>2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>et le nombre de Grundy des 5 cartes est 4+3+3+3+2 = 5.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"606\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143112.jpg\" alt=\"\" class=\"wp-image-2082\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143112.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143112-300x253.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Les nombres de Grundy des 4 cartes sont :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>1<\/td><td>0<\/td><\/tr><tr><td>3<\/td><td>3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>dont la nim-somme est 1+0+3+3 = 1.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"358\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143437.jpg\" alt=\"\" class=\"wp-image-2083\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143437.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143437-300x149.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Les nombres de Grundy sont :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>2<\/td><td>4<\/td><td>1<\/td><\/tr><tr><td><\/td><td>3<\/td><td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Le nombre de Grundy du tout est donc 2+4+1+3 = 4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"161\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143628.jpg\" alt=\"\" class=\"wp-image-2084\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143628.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_143628-300x67.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Les nombres de Grundy sont :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>1<\/td><td>2<\/td><td>3<\/td><td>2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>dont la somme est 1+2+3+2 = 2.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"720\" height=\"390\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_144626.jpg\" alt=\"\" class=\"wp-image-2085\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_144626.jpg 720w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2026\/03\/20260422_144626-300x163.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/figure>\n\n\n\n<p>Les nombres de Grundy sont :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><\/td><td>0<\/td><td>3<\/td><\/tr><tr><td>1<\/td><td>3<\/td><td>3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>dont la somme n&rsquo;est \u00e9gale qu&rsquo;\u00e0 0+3+1+3+3 = 2, mais trois des cartes (diff\u00e9rentes entre elles) valent 3, donc deux d&rsquo;entre elles s&rsquo;annulent mutuellement, sans qu&rsquo;il soit ais\u00e9 de voir comment.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dans cet article, on va s&rsquo;int\u00e9resser \u00e0 des jeux impartiaux, dont l&rsquo;arch\u00e9type est le jeu de Nim. Dans ce jeu, on dispose de jetons, dispos\u00e9s en tas comme ici (jeu de Nim \u00e0 deux tas) : Ci-dessous ce jeu sera not\u00e9 (3,2) car il y a un tas de 3 jetons et un tas de [&hellip;]<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[28,29,30,79,32,48,70,35,17],"coauthors":[54],"class_list":["post-1865","post","type-post","status-publish","format-standard","hentry","category-jeux-mathematiques","tag-cycle-1","tag-cycle-2","tag-cycle-3","tag-graphes","tag-lycee","tag-manipulation","tag-maternelle","tag-nsi","tag-python"],"_links":{"self":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/1865","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1865"}],"version-history":[{"count":20,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/1865\/revisions"}],"predecessor-version":[{"id":2088,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/1865\/revisions\/2088"}],"wp:attachment":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1865"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1865"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1865"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcoauthors&post=1865"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}