Jump to content
  • 0
Enigme2Labo

Le Problème Josephus

Question

Bonjour à tous, 

Dans la série des énigmes mathématique, je suis tombé sur un super petit problème, bien connu des mathématiciens. L'avantage c'est qu'il n'y a pas besoin d'avoir des connaissances avancées en mathématique, mais qu'une approche intuitive pas à pas suffise !

Le Problème Josephus 

Un groupe de N personnes sont en cercle, et se lancent une balle selon les règles suivantes : 
* Une personne envoi la balle à son voisin le plus proche, dans le sens horaire. 
* La personne qui attrape la balle est éliminée. 

* La personne suivante dans le sens horaire récupère la balle et l'envoie à son tour.  
* La dernière personne dans le cercle gagne le jeu. 
-> Cf dessin pour illustration. 

Le problème : pouvez-vous prédire où vous placer dans le cercle pour gagner à tous les coups ? 

Coup de pouce : 
Je vous suggère une approche itérative ou vous essayez avec des cercles de différentes tailles, et établissez des règles. 
Ensuite vous pouvez essayer de démontrer les règles. 

Merci à ceux qui connaissent déjà la solution de s'abstenir ! A vous de jouer ^^. 

Josephus problem.jpg

Edited by Enigme2Labo

Share this post


Link to post
Share on other sites

4 answers to this question

Recommended Posts

  • 0
Révélation

Initialement, il y a n personnes et le ballon est porté par le numéro 1.

Je représente la chose comme ceci, avec le porteur du ballon entouré de deux étoiles :

{ *1* 2 3 4 ... n }

Selon que le nombre de participants n est pair ou impair, il va se passer des choses différentes.

Si n est pair :

    On a fait un tour complet en éliminant les numéros pairs et le ballon revient sur 1.
    On obtient : { *1* 3 5 ... n-3 n-1 }
    On renumérote :
    { *1* 2 3 ... n/2-1 n/2 }
    On est passé de n participants à n/2 participants.
    La renumérotation prend le numéro i et le remplace par (i+1)/2.
    Remarque : la renumérotation laisse inchangé le numéro de 1.

 

Si n est impair :
    On a fait un tour complet en éliminant les numéros pairs et le ballon arrive sur n.
    { 1 3 5 7 9 ... n-2 *n* }
    Puis n envoie le ballon à 1 qui est éliminé.
    On se retrouve alors dans cette situation :
    { *3* 5 7 9 ... n-2 n }
    On renumérote :
    { *1* 2 3 ... (n-3)/2 (n-1)/2 }
    On est passé de n participants à (n-1)/2 participants.
    La renumérotation prend le numéro i et le remplace par (i-1)/2. En effet, 3 a été renommé 1.

 

Dans tous les cas, après renumérotation, le ballon est porté par le numéro 1.

A la fin, c'est ce numéro 1 qui gagne.

 

Remarque : Si le nombre initial de personnes est une puissance de 2, alors le vainqueur est le numéro 1 initial.

 

En résumé, pour répondre à l'énigme, il s'agit donc de retrouver le numéro initial qui correspond au numéro 1 final.

 

Pour trouver ce numéro, on va prendre le problème à l'envers.

 

On suppose que le ballon a fait plusieurs tours et qu'on a déjà éliminé un certain nombre de participants.

Il reste n personnes.

 

{ *1* 2 3 4 ... n }

 

Question : à quoi la suite ressemblait-elle au tour précédent ?

 

Au tour précédent, il y avait soit 2n personnes, soit 2n+1 personnes.

 

S'il y avait 2n personnes, la situation était { *1* 2 3 ... 2n-1 2n } et *1* est resté *1*.
S'il y avait 2n+1 personnes, la situation était { 1 2 *3* ... 2n 2n+1 } et *1* était *3* au tour précédent.

 

On voit que connaissant le rang i d'une personne dans la liste, il est facile de retrouver son rang au tour précédent.

 

Si n est pair, au tour précédent ce rang était 2i-1 (1 est le 1 du tour précédent).
Si n est impair, au tour précédent ce rang était 2i+1 (1 est le 3 du tour précédent).

 

Maintenant on cherche le rang qu'avait la personne gagnante au premier tour.

 

Au dernier tour, le rang gagnant est connu, c'est 1.


On part de 1 et on multiplie par 2i-1 ou par 2i+1 selon la parité de la taille de la liste au tour précédent.

Une manière de connaître la parité à chaque tour est d'écrire le nombre initial de participants en base 2.

 

Recette de cuisine :
    * Écrire le nombre initial de participants en base 2.
    * Passer en revue les 0 et les 1 en commençant par les puissances les plus grandes.
    * Multiplier par 2 et ajouter +1 ou -1 selon qu'on est sur un 0 ou sur un 1.

 

Exemple avec 2022 participants :
Représentation binaire de 2022 : 111 1110 0110

Calcul :

 

0 * 2 +1 = 1  <-- Au dernier tour, c'est 1 qui gagne.
1 * 2 +1 = 3
3 * 2 +1 = 7
7 * 2 +1 = 15
15 * 2 +1 = 31
31 * 2 +1 = 63
63 * 2 -1 = 125
125 * 2 -1 = 249
249 * 2 +1 = 499
499 * 2 +1 = 999
999 * 2 -1 = 1997

 

Le gagnant est le numéro 1997.

 

Avec cette méthode, je peux trouver où me placer pour gagner à tous les coups.

 

 

  • Bien joué ! 1

Share this post


Link to post
Share on other sites
  • 0

Freddy, superbe ! Démonstration complétement différente de ce à quoi je m'attendais, mais ça marche ! 👌

J'ai une méthode légèrement différente pour la recette de cuisine, qui évite de passer en base deux, et évite l'itération successive de ta recette, mais qui demande d'être calé en puissance de 2. Quelqu'un veut tenter de la trouver ? 

PS: Freddy, je laisse un peu si d'autres veulent chercher, puis je validerai ta réponse. 

Edited by Enigme2Labo

Share this post


Link to post
Share on other sites
  • 0

Merci @Enigme2Labo

 

Révélation

Je n'ai pas de véritable démonstration mais des calculs basés sur des choses facilement observables.

 

On a vu que :

2022 -> 111 1110 0110 -> 1997

 

Maintenant regardons pour 2023 :

 

2023 -> 111 1110 0111

 

Le 0 final est remplacé par un 1.
Le calcul est le même que pour 2022 sauf qu'à la fin -1 est remplacé par +1.
On va donc obtenir 1999 au lieu de 1997.

 

2022 -> 111 1110 0110 -> 1997

2023 -> 111 1110 0111 -> 1999

 

On a vu aussi que pour les puissances de 2, le gagnant est le n°1.

En effet, 0*2+1 donne 1 et ensuite on égrène des 0 : 1*2-1 = 1. On reste bloqué sur 1.

 

Pour 2^n + 1, ça donne 3 (2 de plus que 2^n).

Pour 2^n - 1, en binaire on n'a que des 1. Donc on va répéter l'action *2+1 autant de fois que nécessaire.

 

Suite de "*2+1" : 0 1 3 7 15 31 63 127 255 ...

Cela ressemble furieusement aux puissances de 2, moins 1.

 

Après avoir fait le calcul à la main pour 5, 15, 19, 25, etc, j'ai pu construire un tableau qui fait apparaître une belle régularité des résultats.

 

4 -> 100 -> 1
5 -> 101 -> 3
7 -> 111 -> 7

 

8 -> 1000 -> 1
9 -> 1001 -> 3
15 -> 1111 -> 15

 

16 -> 10000 -> 1
17 -> 10001 -> 3
18 -> 10010 -> 5
19 -> 10011 -> 7
20 -> 10100 -> 9
25 -> 11001 -> 19
31 -> 11111 -> 31

 

32 -> 100000 -> 1
33 -> 100001 -> 3
63 -> 111111 -> 63

 

64 -> 1000000 -> 1
65 -> 1000001 -> 3
127 -> 1111111 -> 127

 

128 -> 10000000 -> 1
129 -> 10000001 -> 3
130 -> 10000010 -> 5
255 -> 11111111 -> 255

 

256 -> 100000000 -> 1
257 -> 100000001 -> 3
511 -> 111111111 -> 511

 

512 -> 1000000000 -> 1
513 -> 1000000001 -> 3
1023 -> 1111111111 -> 1023

 

1024 -> 10000000000 -> 1
1025 -> 10000000001 -> 3
2022 -> 101010101 -> 1997
2023 -> 101010101 -> 1999
2047 -> 11111111111 -> 2047

2048 -> 100000000000 -> 1
 

En notant puissance_inferieure(x) la plus grande puissance de 2 plus petite ou égale à x, on peut tenter une formule :

 

1 + 2 * (x - puissance_inferieure(x))

 

Reprenons.

 

Pour 2022, la puissance de 2 qui précède est 1024.

On applique la formule : 1 + 2 * (2022 - 1024) = 1 + 2 * 998 = 1997

Ça marche !

 

Supposons maintenant que n = 1 million.

Le gagnant devrait être : 1 + 2 * (10^6 - 2^19) = 951 425.

Étonnant non ?

 

 

  • Bien joué ! 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...

Important Information

En utilisant ce site, vous acceptez notre Privacy Policy et nos Terms of Use
We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.