Petits problèmes | ||
page précédente | Nicolas Markey |
Soit G=(V,E) un graphe connexe fini non orienté, et tel que E ne contienne pas de boucle d'un état sur lui-même. Sur chaque sommet de ce graphe, on dispose un certain nombre de jetons (et on nomme « configuration » du graphe une disposition de ces jetons).
Une « partie » est une suite de configurations, partant d'une configuration initiale, et telle que le passage d'une configuration à la suivante est régi par le principe suivant :
Il est clair qu'une partie peut être finie (intuitivement, s'il n'y a pas beaucoup de jetons) ou infinie (intuitivement, s'il y a beaucoup de jetons). Le nombre total de jetons est donc constant sur une partie. Notons le j. Notons également n le cardinal de V et m celui de E. Montrer que si une partie est infinie, alors toutes les parties commençant par la même configuration initiale sont infinies. Montrer qu'une partie est infinie si, et seulement si, elle fait intervenir tous les sommets. Montrer les équivalence suivantes :
j > 2m-n | si, et seulement si, | toutes les parties sont infinies, quelle que soit la configuration initiale |
j < m | si, et seulement si, | toutes les parties sont finies, quelle que soit la configuration initiale. |
Énonçons tout d'abord quelques remarques générales sur le déroulement d'une partie :
On trouve dans le livre Avec des nombres et des lignes de Sainte-Laguë (Vuibert) le problème suivant : On raconte que l'historien juif Flavius Josèphe sauva sa vie dans le premier siècle de notre ère de la façon que voici. La ville de Jotapate ayant été prise par les troupes romaines de l'empereur Vespasien, il se réfugia avec 40 de ses coreligionnaires dans une caverne. Ceux-ci, à l'exception de l'un d'entre eux, résolurent de se tuer pour ne pas tomber entre les mains de leurs vainqueurs. Josèphe, ne pouvant les en dissuader et ne voulant pas être entrainé dans un massacre général, imagina, parait-il, de mettre de l'ordre dans cette tuerie. Il fit placer tout le monde en cercle, en mettant habilement le seul de ses compagnons, qui, comme lui, n'était pas décidé à mourrir, au xème rang et se mettant non moins habilement au yème. Ceci fait, on convint, pour lui faire plaisir, de compter les vivants de 3 en 3 et d'égorger chaque fois l'homme qui serait ainsi désigné. Le dernier devait se suicider pour que personne ne survive. Grâce à ces dispositions habiles, Josèphe et son compagnon restèrent les deux dernier et naturellement ne respectèrent pas les conventions établies, grâce à quoi ils purent sauver leur vie. Il n'est pas difficile d'écrire un programme permettant de calculer le choix de x et y qui a permis a Josèphe de sauver sa vie, même en remplaçant 40 et 3 par des entiers n et m quelconques. La question que l'on se pose ici est de savoir s'il existe une expression « analytique » de x et y en fonction de n et m, et sinon comment justifier qu'il est impossible de trouver une telle expression ?