Fixed Points of the Josephus Function via Fractional Base Expansions

Cet article établit un lien entre la suite des points fixes de la fonction de Josephus $J_3$ et le théorème des restes chinois, puis identifie un motif numérique dans leurs expansions en base fractionnaire $3/2$ permettant d'en déduire une procédure récursive pour déterminer leurs chiffres.

L'essentiel

🎭 Le Jeu de la Survie et le Secret des Chiffres

Imaginez un jeu de société très ancien, appelé le problème de Josephus.

Le Scénario :
Vous avez un groupe de personnes assises en rond. On commence à compter : "1, 2, 3 !". La personne sur le "3" est éliminée. On continue en comptant à partir de la personne suivante, on saute deux, on élimine la troisième, et ainsi de suite, jusqu'à ce qu'il ne reste qu'une seule personne. Cette dernière est le survivant.

La question mathématique est simple : Si je veux être le survivant, à quelle position dois-je m'asseoir au départ ?
Pour un petit groupe, c'est facile à calculer. Mais si vous avez 1 million de personnes, le calcul devient un cauchemar pour un ordinateur. C'est là que les auteurs de ce papier, Yunier et Roy, entrent en jeu. Ils étudient une version spécifique de ce jeu (où l'on élimine tous les 3èmes) et cherchent des "points fixes" : des positions magiques qui restent stables ou qui suivent une règle très précise.

🔍 La Grande Découverte : Une Langue Étrange (Base 3/2)

Pour comprendre comment ces positions magiques sont construites, les chercheurs ont eu une idée brillante : changer la façon dont nous comptons.

Habituellement, nous utilisons le système décimal (base 10 : 0, 1, 2... 9) ou le système binaire des ordinateurs (base 2 : 0, 1).
Ici, ils utilisent une "langue" étrange appelée la base 3/2.

L'Analogie de la Monnaie Étrange :
Imaginez que vous avez une monnaie où une pièce vaut 1,50 € (au lieu de 1 €).

• Dans notre monde normal (base 10), pour écrire le nombre 4, vous écrivez "4".
• Dans ce monde étrange (base 3/2), le nombre 4 s'écrit comme une suite de chiffres : 212.

Cela semble bizarre, mais c'est comme si vous utilisiez des pièces de valeurs différentes pour construire vos nombres. Les chercheurs ont découvert que les "positions magiques" (les points fixes) de ce jeu de Josephus ont une structure très particulière quand on les écrit dans cette langue de 1,50 €.

🧩 Le Puzzle des Chiffres (La Règle de Construction)

Voici la partie la plus fascinante, celle qui ressemble à un jeu de Lego :

1. L'Empilement : Si vous prenez le nombre magique du tour précédent (disons le nombre 20) et que vous l'écrivez dans cette base étrange, vous obtenez une suite de chiffres.
2. L'Extension : Pour trouver le nombre magique du tour suivant (le nombre 46), il suffit de prendre la suite précédente et d'ajouter quelques nouveaux chiffres à la fin.
3. La Règle du "Compteur" : Le nombre de chiffres à ajouter dépend d'un petit compteur caché (noté $m_\ell$ dans le papier).
   • Si le compteur est à 0, on ajoute juste un 1.
   • Si le compteur est à 1, on ajoute 02.
   • Si le compteur est à 2, on ajoute 0112.
   • Et ainsi de suite.

L'Analogie du Chameau :
Imaginez que chaque nombre magique est un chameau. Pour passer au chameau suivant, vous ne reconstruisez pas tout l'animal. Vous gardez le corps du chameau précédent et vous lui faites pousser une nouvelle queue. La longueur et la forme de cette nouvelle queue dépendent d'un petit signal (le compteur) que seul le chameau connaît.

🗝️ Le Lien avec les "Restes" (Théorème des Restes Chinois)

Avant de trouver cette règle de Lego, les auteurs ont dû résoudre un casse-tête plus complexe. Ils ont utilisé un outil mathématique très puissant appelé le Théorème des Restes Chinois.

L'Analogie du Cadenas à plusieurs serrures :
Imaginez que chaque nombre magique est une clé qui doit ouvrir deux serrures différentes en même temps.

• La première serrure ne s'ouvre que si le nombre laisse un certain reste quand on le divise par 3, 9, 27, etc.
• La deuxième serrure ne s'ouvre que si le nombre laisse un certain reste quand on le divise par 2, 4, 8, etc.

Les chercheurs ont prouvé que pour trouver le prochain nombre magique, il suffit de trouver le nombre unique qui satisfait ces deux conditions de serrures en même temps. C'est comme trouver le code secret qui ouvre deux portes différentes simultanément.

🚀 Pourquoi est-ce important ?

Avant ce papier, trouver ces nombres magiques demandait de faire des calculs longs et fastidieux, comme essayer de grimper une montagne à chaque fois.

Grâce à cette découverte :

1. On a une recette de cuisine : On peut maintenant "construire" le prochain nombre magique simplement en regardant le précédent et en ajoutant les bons chiffres à la fin. C'est comme suivre une recette de gâteau : prenez la pâte de la veille, ajoutez un peu de sucre, et hop, vous avez le gâteau du lendemain.
2. On comprend la structure : On voit que ces nombres ne sont pas du tout aléatoires. Ils suivent un motif très élégant, comme une mélodie qui se répète en s'agrandissant.

En Résumé

Ce papier nous dit que derrière un jeu de comptage ancien et apparemment chaotique, se cache un ordre parfait. En changeant notre façon de compter (passant de la base 10 à la base 3/2), les chercheurs ont révélé que les "survivants" de ce jeu se construisent comme des chaînes de Lego : on prend la chaîne précédente et on ajoute simplement quelques pièces à la fin selon une règle précise.

C'est une belle preuve que même dans les problèmes les plus complexes, la nature aime les motifs simples et répétitifs, à condition de savoir comment les regarder.

Résumé technique

Voici un résumé technique détaillé du document de recherche intitulé « Fixed Points of the Josephus Function via Fractional Base Expansions » (Points fixes de la fonction de Josephus via les développements en base fractionnaire), rédigé par Yunier Bello-Cruz et Roy Quintero-Contreras.

1. Problématique et Contexte

L'article se concentre sur l'étude des points fixes de la fonction de Josephus $J_3$, notée $J_3(n)$. Ce problème découle du célèbre problème combinatoire de Josephus, où $n$ personnes sont assises en cercle et éliminées par tiers (on saute deux personnes, on élimine la troisième) jusqu'à ce qu'un seul survivant reste. $J_3(n)$ désigne la position initiale du survivant.

L'objectif principal est d'analyser la séquence des points fixes de cette fonction, notée $\{n_p^{(\ell)}\}_{\ell \in \mathbb{N}}$, où un point fixe est un entier $n_p$ tel que $J_3(n_p) = n_p$. Bien que des formules explicites existent pour le cas classique $J_2$ (élimination par deux), la structure de $J_3$ est beaucoup plus complexe. Les auteurs cherchent à établir une relation récursive claire entre les points fixes consécutifs en utilisant des outils de théorie des nombres et des systèmes de numération non standards.

2. Méthodologie

Les auteurs adoptent une approche hybride combinant l'arithmétique modulaire et les systèmes de numération fractionnaires :

• Théorème des Restes Chinois (CRT) : Ils établissent d'abord un lien entre les points fixes consécutifs $n_p^{(\ell)}$ et $n_p^{(\ell+1)}$ en les représentant comme solutions d'un système de congruences linéaires. En exploitant le fait que les modules $3^p$et$2^q$ sont premiers entre eux, ils utilisent le CRT pour caractériser ces points fixes.
• Système de Numération en Base 3/2 : Pour dépasser les limites de la représentation décimale ou binaire, les auteurs introduisent un système de numération en base fractionnaire $3/2$. Contrairement au système standard utilisant uniquement les chiffres${0, 1}$, ils définissent un système permettant les chiffres${0, 1, 2}$.
  • Tout entier positif $N$ est représenté sous la forme :
    $$N = \frac{1}{2} \left[ d_k \left(\frac{3}{2}\right)^k + \dots + d_1 \left(\frac{3}{2}\right)^1 + d_0 \right]$$
    où $d_i \in \{0, 1, 2\}$.
  • Un algorithme itératif est proposé pour calculer ces expansions de manière unique et finie.

3. Contributions Clés et Résultats

Le cœur de l'article réside dans la découverte d'un motif numérique régulier dans les expansions en base $3/2$des points fixes de$J_3$.

A. Connexion avec le Théorème des Restes Chinois

Les auteurs démontrent que chaque point fixe $n_p^{(\ell+1)}$ satisfait un système de congruences dépendant d'un paramètre $m_\ell$, qui représente le nombre de "points extrémaux purs" (pure high extremal points) situés entre deux points fixes consécutifs. Cela permet de relier la structure discrète de la fonction de Josephus à l'identité de Bézout et au CRT.

B. Caractérisation Récursive des Chiffres (Théorème 1)

Le résultat principal est le Théorème 1, qui fournit une procédure récursive pour déterminer l'expansion en base $3/2$du point suivant$n_p^{(\ell+1)}$à partir de celle du point précédent$n_p^{(\ell)}$.

Soit $n_p^{(\ell)} = (\hat{d}_k \dots \hat{d}_0)_{3/2}$. La transition vers $n_p^{(\ell+1)}$ dépend de la valeur de $m_\ell$ :

1. Si $m_\ell = 0$ : On ajoute le chiffre 1 à la droite.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 1)_{3/2}$$
2. Si $m_\ell = 1$ : On ajoute la séquence 02 à la droite.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 0 2)_{3/2}$$
3. Si $m_\ell \ge 2$ : On ajoute la séquence 0, suivie de $(m_\ell - 1)$ fois le chiffre 1, puis le chiffre 2.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \underbrace{0 \underbrace{1 \dots 1}_{m_\ell-1} 2}_{\text{suffixe}})_{3/2}$$

De plus, le nombre total de chiffres de l'expansion de $n_p^{(\ell+1)}$ est égal à celui de $n_p^{(\ell)}$ augmenté de $m_\ell + 1$.

C. Validation Empirique

Les auteurs valident cette théorie en calculant les expansions en base $3/2$des 20 premiers points fixes de$J_3$ (Tableau 3 du document), confirmant que le motif observé correspond parfaitement aux prédictions théoriques.

4. Signification et Perspectives

• Généralisation du cas $J_2$ : Ce travail généralise élégamment le résultat connu pour $J_2$, où les points fixes sont de la forme $2^\ell - 1$(une suite de 1 en binaire). Ici, la base$3/2$ joue un rôle analogue, révélant une structure récursive profonde qui était auparavant masquée.
• Nouvelle Perspective Structurelle : L'utilisation de la base fractionnaire $3/2$offre une méthode transparente pour décrire et générer les points fixes de$J_3$, transformant un problème de récurrence complexe en une simple opération d'ajout de suffixes de chiffres.
• Ouvertures de Recherche :
  • Les auteurs suggèrent d'explorer si cette méthode peut être étendue à $J_4$ (élimination par quart) en utilisant une base $4/3$, bien que la structure de$J_4$ soit plus complexe (deux types de points extrémaux).
  • Une question ouverte reste de savoir si l'on peut calculer directement $J_3(n)$ pour un $n$ quelconque à partir de son expansion en base $3/2$, similaire à la propriété de décalage de bits pour$J_2$.

En conclusion, cet article établit un pont significatif entre la théorie des nombres (CRT, identités de Bézout) et les systèmes de numération non standards, offrant un cadre puissant pour l'analyse des propriétés combinatoires de la fonction de Josephus.