Résumé : où faut-il se placer sur un cercle pour échapper à un massacre. Ce problème, inspiré d’un fait authentique, est une introduction à la simulation.
Mots-clés : arithmétique, reste de division euclidienne, congruence, simulation, récurrence.
L’exercice s’inspire du suicide des zélotes à Masada en avril 74. Il mérite quelques explications qui ont été extraites du livre La bible confisquée de Michael Baigent et Richard Leigh publié chez Plon en 1992.
« Perchée sur un éperon rocheux, au sommet d’une montagne escarpée qui domine la rive sud-ouest de la mer Morte, à une quarantaine de kilomètres au sud de Qumran, la forteresse (Masada) devint le dernier bastion de la résistance des rebelles, le symbole même de la rébellion. Masada résistait encore, alors que toutes les autres villes ou places fortes étaient tombées. Jérusalem avait été pris et rasé deux ans après le début de l’insurrection, en 70. Masada resta imprenable jusqu’en 74. Abrités derrière ses murs, neuf cent soixante défenseurs assiégés repoussèrent les assauts répétés d’une armée romaine estimée à quinze mille hommes.
» En dépit de sa résistance acharnée, la situation de Masada, en avril 74, était devenue désepérée. Coupée de tout renfort, entièrement cernée par l’armée romaine, sa garnison n’était plus capable de supporter une attaque décisive. Après avoir bombardé la forteresse à l’aide de lourdes machines de siège, les Romains tracèrent une immense voie d’approche et, la nuit du 15 avril 74, se préparèrent à l’assaut final. Exhortés par Eléazar, commandant de la forteresse, les hommes tuèrent leurs femmes et leurs enfants. Dix hommes furent choisis pour tuer leurs compagnons. Puis ils tirèrent au sort celui d’entre eux qui égorgerait les neuf autres. Lorsqu’il eut accompli sa tâche, il mit le feu aux bâtiments encore debout et se suicida. Neuf cent soixante hommes, femmes et enfants périrent ainsi. Lorsque les Romains se ruèrent à l’entrée de Masada le lendemain matin, ils ne trouvèrent que des cadavres dans un monceau de ruines.
» Deux femmes et cinq enfants réussirent à échapper au massacre en se cachant dans des aqueducs souterrains. Flavius Josèphe rapporte le témoignage de l’une des femmes, interrogée, dit-il, par des officiers romains...
» Josèphe n’est pas toujours fiable, mais il n’y a aucune espèce de raison de douter de son récit. (...) Flavius Josèphe était à même de comprendre la mentalité qui guida le suicide collectif de Masada. Au début de la révolte, il commandait lui-même des révoltés en Galilée. En 67, ses troupes furent assiégées par Vespasien à Jotapata. Quand la place tomba, beaucoup de ses défenseurs se suicidèrent plutôt que d’être emprisonnés. D’autres, comme Flavius Josèphe, s’enfuirent et se cachèrent dans des cavernes. Il raconte qu’il se réfugia dans une grotte où il trouva une quarantaine de fugitifs. Ici, comme à Masada, ils tirèrent au sort, pour savoir dans quel ordre ils allaient s’entre-tuer. Que ce soit ‘l’effet du hasard ou de la providence divine’, Josèphe resta le dernier avec un autre homme qu’il réussit à convaincre de demeurer en vie ; tous deux se rendirent aux Romains. »
Cette histoire a inspiré Ahrens, Herstein, Kaplansky, Graham, Knuth et Patashnik. La formulation définitive donnée ci-après est tirée du livre, Concrete Mathematics de Graham, Knuth et Patashnik publié chez Addison Wesley en 1989.
Préférant le suicide à la capture, les rebelles juifs cachés dans une grotte décidèrent de former un cercle et, en le parcourant, de tuer chaque troisième personne restante jusqu’à ce qu’il n’y ait plus personne. Mais Flavius Josèphe et un co-conspirateur inconnu ne voulaient pas de ce suicide insensé ; ainsi il détermina rapidement où il devait se placer (ainsi que son ami) sur le cercle vicieux. L’exercice consiste donc à trouver une formule générale pour résoudre ce problème (avec n personnes, k - 1 personnes restantes).
Commencez par des cas simples et construisez un tableau pour des valeurs de n = 1,2,3,… en prenant k = 2 (toutes les deuxièmes personnes).
Ecrivez un programme informatique pour calculer les valeurs recherchées J(n) dans tous les cas. Ceci permettra d’obtenir plus aisément le résultat pour de grands n et pour des valeurs différentes de k.
Essayez de trouver une formule de récurrence permettant de calculer J(n) pour des valeurs de n paires et impaires dans le cas où k = 2.
La solution actuellement proposée est donnée par les fichiers MatLab : zelotes.m et zelotesDemo.m