Hackenbush¶
Le jeu de Hackenbush est joué par deux joueurs Plein et Pointillé sur un plateau consistant en un ensemble de traits reliés, au moins en un point, à une ligne appelée le sol.
À tour de rôle, Plein efface un trait plein et Pointillé efface un trait en pointillé. Le premier joueur qui ne peut plus effacer de trait, car il n'y en a plus de son type, a perdu.
Quand on efface un trait, tous les traits qui ne sont plus reliés au sol disparaissent.
On aimerait associer à chaque plateau un entier relatif \(p\in \Z\) indiquant si le plateau est favorable pour Plein quand \(p\) est grand et défavorable quand \(p\) est petit.
On commence par identifier facilement des parties nulles : on dit qu'un plateau est nul et vaut \(0\) quand le joueur qui commence à jouer perd nécessairement.
Voici un exemple de plateau nul :
Un plateau qui ne contient que \(p\) traits du joueur Plein aura la valeur \(p\), et un plateau qui ne contient que \(p\) traits du joueur Pointillé aura la valeur \(-p\). Ainsi, on peut voir la valeur comme le nombre de coups d'avance du joueur Plein.
Un plateau de valeur 3 :
Étant donné deux plateaux, on appelle somme des plateaux le plateau obtenu en considérant les deux dessins côte à côte.
La somme des deux plateaux précédents est donc :
Question 1. Si on considère des plateaux simples de valeurs \(p\) et \(q\), montrez que la somme des plateaux est de valeur \(p+q\).