Bonjour,

Ce problème m'a fait pensé à un autre que j'ai vu il y a trois ou quatre ans à un congrès Maths en Jeans. C'était la même démarche d'élimination mais par suicide. C'était le problème de Flavius Josephe

On peut numéroter les "participants" de 1 à 1000 en commençant par celui qui reçoit le revolver en premier.
1 tue 2 et passe à 3 qui tue 4, ... , 997 tue 998 et passe à 999 qui tue 1000 et repasse à 1.
Au bout de ce premier tour il ne reste que les impairs. (ils sont 500)
1 tue donc 3 et passe à 5 qui tue 7, etc.

1 reçoit à nouveau le révolver à la fin du deuxième tour car cela laisse les multiples de 4 + 1   et 1001 en est un. (il y a 250 survivants)

De même à la fin du troisième tour qui ne laisse vivants que les multiples de 8 +1.(125 survivants)

Par contre, mauvaise nouvelle pour lui, 1 disparait  à la fin du quatrième tour  car 1001 n'est pas un multiple de 16 +1 ou car 125 n'est pas pair.
Le 125e  qui est 993 va l'occire.
Il reste 62 survivants pour la suite.

Et la suite a été vérifiée au tableur.

Au cinquième tour c'est donc 17 qui sera le premier et le 993 finira sous la balle du 977 car il restait un nombre pair de survivants.
A la fin de ce 5e  tour  il reste 31 survivants : 17, 49 , ... 977 (des 32k+17)

Au 6e tour, 17 élimine 49, ...et comme il restait un nombre impair de survivants, 977 qui était le 31e eliminera 17 qui ne dépassera donc pas le 6e tour.

Au 7e tour  qui regroupe les 15 nombres de la forme 64k+81 , 81 sera éliminé par le 15e, 977 avant de démarrer le 8e tour.

Au 8e tour il nous reste 7 nombres : 209, 337, ...,  977 et le schéma se répète car 7 est impair

Au 9e tour il reste 3 survivants 465,721 et 977


Et là c'est fini :
465 tue 721 et donne le révolver à 977 qui le tue à son tour.
977 reste seul.

Monsieur ash, qu'est-ce qu'on dit à esereth ?


Edit :
J'y reviens avec un petit programme en python qui peut afficher l'état des troupes à la fin de chaque tour:

tableau=[i for i in range(1001)]
tableau = tableau[1:] # il y a tous les nombres de 1 à 1000
n=1000                # il y a 1000 vivants
print tableau
while n>1:            # tant qu'il y a plus d'un vivant
      tableaubis=[tableau[k] for k in range (0,n,2)]
      if n%2==1:
         tableaubis = tableaubis[1:]
      tableau=tableaubis      
      n=len(tableau)   
      #print tableau,n
print tableau

Ce problème me plait, j'essaie donc de le rationaliser :
Le survivant sera le premier de la suite quand elle ne comportera plus qu'un élément.
les raisons des suites successives des survivants sont 2,4,..
Le premier de la suite ne change pas si la suite a un nombre pair d'éléments
il est remplacé par le second (= premier + raison) de la suite des survivants sinon.
donc successivement :
premier, raison, nombre de termes
1           4         500
1           8         250
1          16        125
17        32          62
17        64          31
81       128         15
209     256           7
465     512           3
977    1024          1

Et voici le dernier code qui va avec :

prem=1
raison=2
N=1000
while N>1:
   if N%2==1:
      prem=prem+raison
   raison*=2
   N/=2
print prem

C'est promis, je me tais  ... jusqu'au prochain pb qui me plait.

On numérote les positions de 1 à 1000 dans le sens du déroulement du "jeu" en commençant par 1 par celui qui tire le premier coup de feu.

Il se trouve que l'on peut déterminer d'avance qui sera le dernier. Cela est évident car le problème est totalement déterministe. Ce que je veux dire c'est que l'on peut le faire simplement

Si le jeu se fait avec N participants, pour connaître le dernier on écrit N en base 2, on passe le 1 de tête en fin et cela donne le dernier.

Voici un exemple: S'il y a 9 participants numérotés de 1 à 9 comme ci-dessus voici l'ordre des éliminations: 2 4 6 8 1 5 9 7. Reste le 3.
9 s'écrit en binaire 1001, lorsque l'on passe le 1 de devant en dernier, cela donne [latex](0011)_2[/latex]=3.

Avec 5 participants, les éliminations sont: 2 4 1 5. Reste le 3.
5=[latex](101)_2[/latex] -> [latex](011)_2[/latex]=3.

Ceci se démontre pas trop difficilement mais avec un peu d'écriture.

Dans notre cas, il y a 1000 participants.
[latex]1000=(1111101000)_2[/latex].
Le participant restant est celui ayant le numéro [latex](1111010001)_2=977[/latex]. C'est donc celui qui sera placé 976 participants plus loin que celui qui commence dans le sens du parcours.
C'est donc là qu'il faut de placer.

(Pour se placer simplement, le 976ème après celui qui tire en premier dans le sens du déroulement est aussi la 24ème place dans le sens inverse du déroulement, soit donc laisser 23 personnes entre le premier et lui).

Bonne chance Ash

Bonjour,

La position la plus sûre semble être la 489. C'est donc celle-ci qu eje recommenderai à Ash.

Si j'étais lui, je me placerais en 977ème position en partant du premier qui s'empare du revolver

Une question: Ash veut se tuer ou rester vivant?
Je vais y réfléchir...

Oh, tiens quelqu'un de la seyne ?

Bon si cette énigme avait été dans la section logique, j'aurais bien dit, de ne pas filer une arme à un fou !

Ou alors pour peu que cette arme est suffisamment de balles dans le chargeur de le donner direct à ash pour qu'il liquide les autres !

Sinon, si on donne l'arme à numéro 1 alors je dirais qu'il doit se placer en:
357e place
Pas vraiment sûr de moi, mais bon, faut voir comment j'ai fait ça.

Ben, y en a des gens qui veulent me sauver la peau ! A moins qu'ils disent justement n'importe quoi pour que je me la fasse trouer...

Mais qu'allais-je donc faire dans cette galère ?..

Pour que ce soit correct, il aurait fallu que tu dises que je suis enfermé avec près de 80.000 fous. Ben oui... tu parles bien de d'enfermement sur P2T, non ?

Et bien sur, ni FRiZ ni MthS ne viennent me donner un conseil !!!
HELP ME !

Ceux qui aiment Ash : NickoGecko, esereth, rivas, gwen27, L00ping007, bidipe et nodgim.

Je numérote tout ce beau monde de 1 à 1000.
Le revolver est transmis à "1", qui abat "2" et le passe à "3", qui abat "4" et le passe à 5, etc
Donc, au 1er tour, tous les 2k sont tués.

"999" a donc tué "1000" et le passe à "1", qui abat "3" et le passe à "5", qui abat "7", etc
Donc, au 2ème tour, tous les 4k+3 sont tués

Idem au 3ème tour, tous les 8k+5 sont tués

Au 4ème tour, tous les 16k+9 sont tués

Au 5ème tour, tous les 32k+1 sont tués

Au 6ème tour, tous les 64k+49 sont tués

Au 7ème tour, tous les 128k+17 sont tués

Au 8ème tour, tous les 256k+81 sont tués

etc jusqu'au dernier survivant = 977 = Ash

J'ai fait un modèle sous Excel, donc je garantis pas le résultat, mais il semblerait que, si l'on considère le premier tireur comme le numéro #1, et son voisin de gauche comme le #2, je conseillerais à Ash de prendre la place #977.

Il y a une histoire d'indent de multiples de 2, mais j'ai du mal à modéliser mathématiquement. Mais je suis sûre qu'il y en aura pour me montrer

Je disais donc: seul le 13 reste vivant
(merci Sylvie!)

Bonjour,
Pour ne pas encombrer inutilement ce topic, j'ai effacé ma première réponse qui est incorrecte. D'ailleurs, quel est l'usage sur ce site dans ces cas ?
Numérotons les personnes: n°1 (celle qui recoit le revolver), n°2 (à sa gauche), etc, jusque n°1000 (à sa droite).
Après 1 tour de revolver, il ne restera plus que 500 personnes: n° 2k-1 (avec k variant de 1 à 500);
après 2 tours, 250 personnes: n° 4k-3 (avec k variant de 1 à 250);
après 3 tours, 125 personnes: n° 8k-7 (avec k variant de 1 à 125);
après 4 tours, 62 personnes: n° 16k-15 (k variant de 1 à 62) et c'est encore n°1 qui "ouvre le bal";
après 5 tours, 31 personnes (n°1 a été tué): n° 32k-15 (k variant de 1 à 31) et c'est n°17 qui "ouvre le bal";
après 6 tours, 16 personnes: n° 64k-47 (k variant de 1 à 16) et c'est encore n°17 qui "ouvre le bal";
après 7 tours, 8 personnes (n°17 a été tué): n° 128k-47 (k variant de 1 à 8) et c'est n°81 qui "ouvre le bal";
après 8 tours, 4 personnes (n°81 a été tué): n° 256k-47 (k variant de 1 à 4) et c'est n°209 qui "ouvre le bal";
après 9 tours, 2 personnes (n°209 a été tué): n° 512k-47 (k valant 1 ou 2) et c'est n°977 qui "ouvre le bal".
Il faut donc placer Ash00 au numéro 977.
Bonne soirée.
Frank

Edit: Réponse modifiée sur la dernière étape pour la conformer à un post ultérieur.