Fais Tourner Fais Tourner

Par ici la monnaie

Probleme

Y'a n personnes assises en cercle autour d'une table basse. On leur distribue n-1 pets (une meme personne peut avoir plusieurs pets en main). A chaque instant chaque personne qui a un pet en main se le garde (faut pas deconner), par contre toute personne qui en a au moins 2 se trouve deborde et en file un a droite et un a gauche (meme si elle en a que 2, c'est ca le drame).

Il faut monter qu'au final il y a n-1 personnes qui ont 1 pet chacun.

Bon alors il existe une solution sur le web dont la demo fait agir les personnes une par une au hasard, du coup c'est pas evident de montrer qu'on arrive au meme etat final. Mais y'a bien plus simple, voici une solution trouvee a jeun lors de l'ecool de juillet 2005.

Solution

Reduction du probleme

Il y a un nombre fini d'etats, donc quitte attendre un peu, on peut considerer qu'on est dans une configuration periodique. Puis on peut raisonner par l'absurde et considerer le plus petit n tel que le resultat est faux. Dans ce cas la, on peut montrer que tout le monde participe a faire tourner des pets (en recoit ou en donne, et en fait vu qu'on est dans une configuration periodique, c'est "en recoit *et* en donne" (pas d'accumulation)). En effet,...

Attach:sphinx.ps solution rédigée par Éric (en remplaçant les pets par des cartes...)