Fixed Points of the Josephus Function via Fractional Base Expansions

Questo articolo stabilisce una connessione tra la sequenza dei punti fissi della funzione di Josephus $J_3$ e il Teorema Cinese del Resto, identificando un pattern numerico nelle loro espansioni in base frazionaria $3/2$ che permette di derivare una procedura ricorsiva per determinarne le cifre.

L'essenziale

Immagina di essere a una festa molto strana, dove c'è un tavolo rotondo pieno di persone. Questa è la base del Problema di Josephus, un antico rompicapo matematico.

Ecco come funziona il gioco:

1. Tutti sono seduti in cerchio e numerati.
2. Si inizia a contare: "Uno, due... via!" La terza persona viene eliminata dal gioco.
3. Si ricomincia a contare dalla persona successiva, saltando di nuovo due e buttando via la terza.
4. Si continua finché non rimane una sola persona: quella è la sopravvissuta.

Il matematico Josephus (da cui prende il nome) si chiedeva: "Se voglio essere l'unico a rimanere, dove devo sedermi all'inizio?"

La funzione $J_3(n)$ è semplicemente la risposta a questa domanda: per un gruppo di $n$ persone, qual è il numero del posto sicuro?

Il Mistero dei "Punti Fissi"

Gli autori di questo articolo (Yunier e Roy) non si sono limitati a calcolare chi vince ogni volta. Hanno cercato un pattern speciale chiamato punti fissi.

Immagina di avere una lista di numeri. Se prendi un numero da questa lista, applichi la regola del gioco di Josephus, e il risultato è... lo stesso numero di partenza! Questi sono i "punti fissi". È come se il gioco dicesse: "Se sei seduto qui, rimani qui, non vieni mai eliminato e non ti sposti".

Gli autori hanno scoperto che questi numeri speciali non sono casuali; seguono una regola precisa e nascosta.

La Chiave Segreta: La "Torta Frazionaria" (Base 3/2)

Qui entra in gioco la parte più creativa e "strana" della ricerca.

Di solito, quando scriviamo i numeri, usiamo la base 10 (0-9) o la base 2 (solo 0 e 1, come nei computer). Ma questi matematici hanno deciso di scrivere i loro numeri speciali usando una base frazionaria: 3/2.

Pensa alla base 3/2 come a una torta che viene tagliata in modo strano:

• Invece di raddoppiare il valore ogni volta che sposti una cifra a sinistra (come fa il 2 nella base 10 o il 10 nella base 2), qui il valore cresce di un fattore "un mezzo e mezzo" (1,5).
• Inoltre, invece di usare solo cifre da 0 a 9, in questo sistema speciale usiamo solo le cifre 0, 1 e 2.

L'analogia del "Crescere a Scatti":
Immagina che ogni numero speciale (punto fisso) sia un bambino che cresce.

• Il primo bambino è piccolo.
• Il secondo bambino è un po' più grande.
• Il terzo è ancora più grande.

Gli autori hanno scoperto che per passare dal bambino numero $\ell$ al bambino numero $\ell+1$, non devi fare calcoli complicati. Devi solo aggiungere dei mattoncini alla fine della sua "scrittura" in base 3/2.

È come se avessi una stringa di perle (i numeri 0, 1, 2) che rappresenta il numero. Per ottenere il prossimo numero speciale, non devi rifare tutto il calcolo da capo. Basta guardare un piccolo indicatore (chiamato $m_\ell$) e aggiungere una sequenza specifica di perle alla fine:

• Se l'indicatore è 0, aggiungi una perla "1".
• Se è 1, aggiungi "02".
• Se è 2, aggiungi "012".
• E così via.

È come se il numero si "auto-completasse" aggiungendo una coda specifica ogni volta che passa al livello successivo.

Il Collegamento con l'Antica Roma (Teorema Cinese del Resto)

Prima di arrivare alla "torta frazionaria", gli autori hanno usato un vecchio trucco matematico chiamato Teorema Cinese del Resto.

Immagina di avere due orologi che ticchettano a ritmi diversi (uno ogni 3 secondi, uno ogni 2 secondi). Il teorema ti dice come trovare un momento in cui entrambi gli orologi segnano un orario specifico contemporaneamente.
Gli autori hanno mostrato che questi numeri speciali sono come quei momenti magici: sono le uniche soluzioni che soddisfano contemporaneamente due regole matematiche diverse (come due orologi che devono coincidere). Questo li ha aiutati a capire perché i numeri esistono e come sono collegati tra loro.

Perché è importante?

Fino a poco tempo fa, calcolare chi vinceva in un gioco di Josephus con milioni di persone richiedeva calcoli lunghissimi e lenti per i computer.

Questo articolo ci dice:

1. C'è un ordine nascosto: Non è caos, c'è una struttura precisa.
2. Possiamo prevedere il futuro: Se conosci il numero "sopravvissuto" attuale e sai quanti "salti" ci sono stati, puoi scrivere il prossimo numero semplicemente aggiungendo delle cifre alla fine, senza fare calcoli pesanti.
3. Nuovi linguaggi: Usare una base come 3/2 (che sembra assurda) rende i numeri molto più semplici da leggere e capire, proprio come usare una lingua madre rende una storia più facile da raccontare rispetto a tradurla in una lingua straniera.

In sintesi

Gli autori hanno preso un vecchio gioco di eliminazione, ha scoperto che i vincitori speciali seguono una regola di crescita molto ordinata, e ha trovato un modo "strano" (usando la base 3/2) per descrivere questa crescita come se fosse una storia che si scrive aggiungendo una parola alla volta alla fine di una frase.

È un po' come scoprire che, invece di dover contare ogni singolo grano di sabbia sulla spiaggia per sapere quanti ce ne sono, basta guardare la forma delle onde e sapere esattamente quanti grani ci saranno nella prossima onda.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "Fixed Points of the Josephus Function via Fractional Base Expansions" di Yunier Bello-Cruz e Roy Quintero-Contreras, redatta in italiano.

1. Il Problema e il Contesto

Il lavoro si concentra sulle proprietà della funzione di Josephus $J_3$, derivante dal classico problema combinatorio di Josephus. Nel problema standard, $n$ persone sono sedute attorno a un tavolo rotondo; si conta in senso orario, saltando due persone ed eliminando la terza, fino a quando non rimane un solo sopravvissuto. La funzione $J_3(n)$ indica la posizione iniziale del sopravvissuto.

Sebbene esistano formule esplicite per il caso $J_2$ (dove si elimina ogni seconda persona), il calcolo diretto di $J_3(n)$ per $n$ grandi è computazionalmente oneroso. L'obiettivo principale degli autori è caratterizzare la sequenza dei punti fissi di $J_3$, definita come $\{n_p^{(\ell)}\}_{\ell \in \mathbb{N}}$, dove un punto fisso è un intero $n$ tale che $J_3(n) = n$. In particolare, gli autori cercano di stabilire una relazione ricorsiva tra i punti fissi consecutivi, analoga a quella nota per $J_2$ (dove i punti fissi sono potenze di 2 e la loro espansione binaria segue un pattern semplice).

2. Metodologia

Gli autori adottano un approccio ibrido che combina teoria dei numeri e sistemi di numerazione non standard:

• Teorema Cinese del Resto (CRT): Viene stabilita una connessione tra la sequenza dei punti fissi e il Teorema Cinese del Resto. I punti fissi sono rappresentati come soluzioni di sistemi di congruenze lineari con moduli coprimi ($3^p$e$2^q$). Questo permette di derivare identità algebriche che legano un punto fisso al successivo.
• Sistema di Numerazione in Base Frazionaria (3/2): Viene introdotto un sistema di numerazione non standard in base $3/2$. A differenza del sistema standard che utilizza solo le cifre 0 e 1, questo sistema permette l'uso della cifra 2.
  • Un numero intero positivo $N$ è rappresentato come:
    $$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]$$
    dove $d_i \in \{0, 1, 2\}$.
  • Viene proposto un algoritmo a quattro passi per calcolare univocamente le cifre di questa espansione partendo da $N$.

3. Risultati Chiave e Contributi

Il contributo principale del paper è la scoperta di un pattern numerico preciso nelle espansioni in base $3/2$dei punti fissi consecutivi di$J_3$.

A. Connessione con il Teorema Cinese del Resto

Gli autori dimostrano che ogni punto fisso $n_p^{(\ell+1)}$ può essere determinato risolvendo un sistema di congruenze derivato dalla relazione ricorsiva originale:
$$2n_p^{(\ell+1)} + 1 \equiv 0 \pmod{3^{m_\ell}}$$
$$3n_p^{(\ell)} + 2 \equiv 0 \pmod{2^{m_\ell}}$$
dove $m_\ell$ è il numero di "punti estremali puri" (un tipo specifico di punto critico) tra due punti fissi consecutivi. Questo collegamento permette di esprimere i punti fissi tramite combinazioni lineari di Bézout.

B. Il Teorema Principale (Teorema 1)

Il risultato più significativo è la formula ricorsiva per le cifre nell'espansione in base $3/2$. Se$n_p^{(\ell)} = (\hat{d}k \dots \hat{d}0){3/2}$, allora il punto fisso successivo$n_p^{(\ell+1)}$si ottiene appendendo una specifica sequenza di cifre alla destra dell'espansione precedente, determinata dal valore di$m\ell$:

1. Se $m_\ell = 0$: Si appende la cifra 1.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 1)_{3/2}$$
2. Se $m_\ell = 1$: Si appendono le cifre 02.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 0 2)_{3/2}$$
3. Se $m_\ell \ge 2$: Si appende la stringa 0, seguita da $(m_\ell - 1)$ cifre 1, e infine una cifra 2.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \underbrace{0 \underbrace{1 \dots 1}_{m_\ell-1} 2}_{\text{lunghezza } m_\ell+1})_{3/2}$$

Inoltre, il numero totale di cifre nell'espansione di $n_p^{(\ell+1)}$ è esattamente quello di $n_p^{(\ell)}$ più $m_\ell + 1$.

C. Validazione Empirica

Gli autori hanno verificato questa regola calcolando le espansioni in base $3/2$per i primi 20 punti fissi di$J_3$(da$n=1$a$n \approx 3.4 \times 10^8$), confermando che il pattern descritto nel Teorema 1 si mantiene costante.

4. Significato e Implicazioni

• Generalizzazione del caso $J_2$: Questo lavoro estende elegantemente la conoscenza sul caso $J_2$, dove i punti fissi sono semplicemente potenze di 2 (espansione binaria di soli 1). Per $J_3$, la struttura è più complessa ma ugualmente regolare se osservata attraverso la lente della base $3/2$.
• Nuovo Strumento Analitico: L'uso della base frazionaria $3/2$ fornisce una prospettiva "trasparente" per comprendere la struttura discreta e lineare a tratti della funzione di Josephus, che altrimenti appare caotica.
• Apertura di Nuove Direzioni di Ricerca:
  • Il paper suggerisce di investigare se i punti fissi di $J_4$ ammettano una formula ricorsiva in base $4/3$.
  • Si pone la questione se sia possibile calcolare direttamente $J_3(n)$ per un $n$ arbitrario basandosi sulla sua espansione in base $3/2$, analogamente a come avviene per$J_2$ tramite lo spostamento delle cifre binarie.

In conclusione, il documento offre un ponte teorico solido tra la teoria dei numeri (CRT) e la combinatoria, fornendo un metodo algoritmico efficiente per generare i punti fissi della funzione di Josephus $J_3$ senza dover simulare l'intero processo di eliminazione.