A distanza di ben nove anni dal precedente approfondimento, rieccoci a parlare delle pile di Gergonne.
Sgombriamo subito il campo da ogni equivoco: il merito di questo ritorno sul tema va sicuramente agli amici “Claudio” e “Chad”, che sono riusciti nell’ardua impresa di vincere la mia ormai patologica svogliatezza nel rimettermi a fare calcoli. :)
Ci eravamo lasciati con l’ipotesi che la formula $L_2$ potesse essere utilizzata per tutti i casi magici.
L’idea era nata confrontando, per alcune configurazioni del gioco, la formula generale derivata dal lavoro di _Harrison et al. 1 2 con una sua versione decisamente più semplice:
\[L_2 = 1+\frac{\sum_{i=1}^{m} k_i n p^{i-1}}{p^m}.\]I risultati ottenuti con il simulatore sembravano confermare l’intuizione. Si trattava però di verifiche su un numero limitato di configurazioni: restava da capire se la formula funzionasse davvero per tutti i casi magici e, soprattutto, perché.
Possiamo ora confermare che è proprio così: nei casi magici la posizione finale della carta è sempre data dalla parte intera di $L_2$.
Ma c’è di più. La formula funziona non soltanto nei casi totalmente magici, ossia nelle configurazioni in cui tutte le possibili sequenze portano a una posizione finale determinata.
Essa è valida anche per le singole sequenze magiche, cioè quelle particolari sequenze di ricomposizioni per le quali la posizione finale della carta non dipende dalla posizione iniziale $x$, anche quando la configurazione nel suo complesso non è magica.
Non si tratta di una semplice approssimazione fortunata, ma di una conseguenza della formula esatta che descrive le ricomposizioni.
Partendo da questa dimostrazione, ricaveremo anche un criterio per riconoscere le sequenze magiche, una condizione per sapere quando lo sono tutte e una formula per contarle in funzione della configurazione.
Ripartiamo dalla formula $L_2$
Manteniamo le notazioni dei due articoli precedenti:
- $n$ è il numero di carte in ciascuna pila;
- $p$ è il numero di pile;
- $m$ è il numero di ricomposizioni;
- $k_i$ è la posizione in cui viene riposta la pila contenente la carta scelta, contando da $0$ a $p-1$ a partire dalla cima del mazzo;
- $x$, con $1\leq x\leq n$, è la posizione iniziale della carta all’interno della pila scelta.
Come nel secondo articolo, consideriamo una sola esecuzione del pattern, ossia $\ell=1$. Dopo le $m$ ricomposizioni effettuiamo un’ulteriore distribuzione e osserviamo la posizione della carta nella pila indicata dallo spettatore.
Per alleggerire i calcoli, poniamo:
\[t=\sum_{i=1}^{m} k_i p^{i-1}=k_1+k_2p+\cdots+k_mp^{m-1}.\]La formula proposta nel precedente articolo diventa allora:
\[L_2=1+\frac{nt}{p^m}.\]La posizione effettiva della carta
Consideriamo una singola ricomposizione. Se la carta si trova in posizione $x$ nella propria pila e questa viene collocata dopo $k$ pile, nella distribuzione successiva la sua nuova posizione all’interno della pila sarà:
\[f_k(x)=1+\left\lfloor\frac{x-1+kn}{p}\right\rfloor.\]Il simbolo $\lfloor z\rfloor$ indica la parte intera inferiore di $z$.
Applicando la trasformazione $m$ volte, con le posizioni $k_1,\ldots,k_m$, si ottiene:
\[f_m(x)=1+\left\lfloor\frac{x-1+nt}{p^m}\right\rfloor. \tag{1}\]Questa è la formula esatta della posizione finale. A differenza di $L_2$, contiene anche $x$, cioè la posizione iniziale che il prestigiatore non conosce.
Dimostrazione della validità di $L_2$ nei casi magici
Vogliamo dimostrare che, per qualsiasi sequenza magica, la posizione finale della carta è sempre data da:
\[f_m(x)=\left\lfloor L_2\right\rfloor.\]Una sequenza è magica quando la posizione finale della carta è indipendente dalla sua posizione iniziale. In termini matematici, questo significa che:
\[f_m(1)=f_m(2)=\cdots=f_m(n).\]Pertanto, se la sequenza è magica, possiamo calcolare la posizione finale utilizzando un qualsiasi valore di $x$, dato che il risultato sarà sempre lo stesso.
Scegliamo allora il valore più semplice, ossia $x=1$.
Sostituendo nella formula esatta (1), otteniamo:
\[f_m(1)=1+\left\lfloor\frac{1-1+nt}{p^m}\right\rfloor.\]Semplificando:
\[f_m(1)=1+\left\lfloor\frac{nt}{p^m}\right\rfloor.\]Ricordando che, per qualsiasi numero reale $a$, vale la proprietà:
\[1+\lfloor a\rfloor=\lfloor1+a\rfloor,\]possiamo scrivere:
\[f_m(1)=\left\lfloor1+\frac{nt}{p^m}\right\rfloor.\]Ma l’espressione all’interno della parte intera è proprio $L_2$. Quindi:
\[f_m(1)=\left\lfloor L_2\right\rfloor.\]Poiché abbiamo ipotizzato che la sequenza sia magica, sappiamo che $f_m(x)=f_m(1)$ per ogni $x$ compreso tra $1$ e $n$.
Otteniamo pertanto:
\[f_m(x)=\left\lfloor L_2\right\rfloor\qquad\forall x\in\{1,\ldots,n\}.\]Abbiamo così dimostrato che la formula $L_2$ fornisce sempre la posizione finale corretta della carta per qualsiasi sequenza magica, indipendentemente dai valori di $n$, $p$, $m$ e dei singoli $k_i$.
È interessante osservare che $L_2$ non rappresenta semplicemente un’approssimazione della posizione finale: la sua parte intera coincide esattamente con la posizione finale calcolata per $x=1$.
Nei casi magici, essendo la posizione finale indipendente da $x$, tale risultato è automaticamente valido per qualsiasi posizione iniziale della carta.
Questo conferma l’intuizione formulata alla fine del precedente approfondimento. Naturalmente, non significa che tutte le sequenze siano magiche: per una sequenza non magica, la posizione finale può ancora dipendere da $x$.
Come riconoscere una sequenza magica
A questo punto sorge spontanea una domanda: possiamo sapere in anticipo se una determinata sequenza è magica, senza eseguire il gioco e senza conoscere $x$?
La risposta è sì, e possiamo ricavarla direttamente dalla formula (1).
Poiché $f_m(x)$ è una funzione non decrescente di $x$, essa è costante per tutti gli $x$ compresi tra $1$ e $n$ se e solo se:
\[f_m(1)=f_m(n).\]Sostituendo nella (1):
\[\left\lfloor\frac{nt}{p^m}\right\rfloor=\left\lfloor\frac{nt+n-1}{p^m}\right\rfloor.\]Poniamo $q=p^m$ e scriviamo la divisione intera di $nt$ per $q$:
\[nt=aq+r,\qquad 0\leq r<q.\]Il valore $r$ è il resto della divisione, che indicheremo con $nt\bmod q$. La precedente uguaglianza diventa:
\[a=a+\left\lfloor\frac{r+n-1}{q}\right\rfloor.\]Perché sia verificata, occorre e basta che:
\[r+n-1<q.\]Trattandosi di numeri interi, otteniamo il nostro primo criterio:
\[(nt\bmod p^m)+n\leq p^m. \tag{2}\]Una sequenza di ricomposizioni è magica se e solo se soddisfa la (2).
Un esempio: 8 carte per pila, 6 pile
Riprendiamo la configurazione $8\times6$, con $n=8$, $p=6$ e $m=2$, già studiata nel secondo articolo.
Consideriamo la sequenza $(k_1,k_2)=(0,2)$. Abbiamo:
\[t=0+2\cdot6=12,\qquad p^m=36.\]Poiché:
\[(8\cdot12)\bmod36=24,\]la condizione (2) diventa:
\[24+8=32\leq36.\]La sequenza è magica e la posizione finale è:
\[\lfloor L_2\rfloor=\left\lfloor1+\frac{8\cdot12}{36}\right\rfloor=3.\]Proviamo invece la sequenza $(k_1,k_2)=(1,2)$:
\[t=1+2\cdot6=13,\qquad (8\cdot13)\bmod36=32.\]Questa volta:
\[32+8=40>36.\]La sequenza non è magica: secondo la posizione iniziale $x$, la carta può terminare in posizione $3$ oppure $4$.
È una distinzione importante rispetto all’analisi del 2017: una configurazione può contenere molte sequenze magiche senza che lo siano tutte.
Quando tutte le sequenze di una configurazione sono magiche
Finora abbiamo esaminato una sequenza alla volta. Ma possiamo anche chiederci quando una configurazione $(n,p,m)$ sia tale da rendere magica qualunque scelta di $k_1,\ldots,k_m$.
In questo caso parleremo di configurazione universalmente magica.
Il risultato è particolarmente semplice:
\[n\mid p^m. \tag{3}\]Il simbolo $\mid$ significa “divide”: dunque $p^m$ deve essere un multiplo di $n$.
Dimostrazione
Poniamo ancora $q=p^m$ e indichiamo con:
\[g=\operatorname{MCD}(n,q)\]il massimo comune divisore tra $n$ e $q$.
Al variare di $t$ tra $0$ e $q-1$, i possibili resti di $nt$ diviso $q$ sono esattamente:
\[0,g,2g,\ldots,q-g.\]Perché tutte le sequenze siano magiche, il criterio (2) deve valere anche per il resto più grande, $q-g$:
\[q-g+n\leq q,\]ossia $n\leq g$. Ma sappiamo anche che $g\leq n$, quindi deve essere $g=n$, che equivale proprio a $n\mid q$.
Ad esempio, nella configurazione $8\times4$ con $m=2$:
\[p^m=4^2=16,\qquad 8\mid16.\]Tutte le $16$ sequenze sono magiche. La posizione finale dipende dalla sequenza scelta, ma non dalla posizione iniziale della carta.
Il conteggio delle sequenze magiche in una configurazione
Arriviamo alla domanda forse più interessante. Quando una configurazione non è universalmente magica, quante delle $p^m$ sequenze possibili funzionano comunque?
Nel precedente articolo avevo affrontato il problema costruendo tabelle con il simulatore. Ma è possibile ottenere direttamente il numero esatto mediante una formula.
Supponiamo anzitutto $n\leq p^m$ e poniamo, come prima:
\[q=p^m,\qquad g=\operatorname{MCD}(n,q).\]Una sequenza è magica quando il resto $r=nt\bmod q$ soddisfa:
\[r\leq q-n.\]Sappiamo che i resti possibili sono i multipli di $g$ compresi tra $0$ e $q-g$, e che ciascun resto compare esattamente $g$ volte al variare di $t$ tra $0$ e $q-1$.
Poiché $g$ divide sia $q$ sia $n$, divide anche $q-n$. I resti ammessi sono quindi:
\[0,g,2g,\ldots,q-n.\]Il loro numero è:
\[\frac{q-n}{g}+1.\]Moltiplicando per $g$, otteniamo il numero $M$ delle sequenze magiche:
\[M=g\left(\frac{q-n}{g}+1\right)=q-n+g.\]Sostituendo le definizioni di $q$ e $g$:
\[M=p^m-n+\operatorname{MCD}(n,p^m). \tag{4}\]Questa formula è valida quando $n\leq p^m$. Se $n>p^m$, nessuna sequenza è magica: il criterio (2) non può essere soddisfatto.
Alcuni casi a confronto
| $n$ | $p$ | $m$ | Sequenze possibili | Magiche | Non magiche |
|---|---|---|---|---|---|
| 8 | 4 | 2 | 16 | 16 | 0 |
| 8 | 6 | 2 | 36 | 32 | 4 |
| 10 | 4 | 2 | 16 | 8 | 8 |
| 13 | 4 | 2 | 16 | 4 | 12 |
| 13 | 4 | 3 | 64 | 52 | 12 |
| 8 | 3 | 2 | 9 | 2 | 7 |
| 10 | 3 | 2 | 9 | 0 | 9 |
Un mazzo completo da 52 carte
Prendiamo un mazzo da $52$ carte e distribuiamolo in $4$ pile da $13$ carte:
\[n=13,\qquad p=4.\]Con due ricomposizioni abbiamo $4^2=16$ sequenze. Siccome $\operatorname{MCD}(13,16)=1$:
\[M=16-13+1=4.\]Con tre ricomposizioni le sequenze possibili diventano $4^3=64$, mentre:
\[M=64-13+1=52.\]Quindi 52 sequenze su 64, pari all’$81{,}25\%$, sono magiche. Le sequenze non magiche restano soltanto $12$, esattamente come nel caso con due ricomposizioni.
Non significa che, scegliendo una sequenza a caso, il prestigiatore possa sempre conoscere la carta: significa che, conoscendo la sequenza utilizzata, nel $81{,}25\%$ dei casi essa determina una posizione finale indipendente dalla posizione iniziale.
Conclusioni
Ripartendo dall’ultima osservazione del mio articolo del 2017, abbiamo dunque potuto chiarire il ruolo della formula $L_2$.
La sua parte intera non è una semplice approssimazione della posizione finale: è esattamente la posizione della carta per ogni sequenza magica, ossia quando la posizione finale non dipende da $x$.
Inoltre, abbiamo ricavato tre risultati che permettono di analizzare una configurazione senza ricorrere alla simulazione di tutte le possibilità:
- Riconoscere una sequenza magica: $(nt\bmod p^m)+n\leq p^m$.
- Riconoscere una configurazione universalmente magica: $n\mid p^m$.
- Contare le sequenze magiche: $M=p^m-n+\operatorname{MCD}(n,p^m)$, per $n\leq p^m$.
Il problema che nel precedente approfondimento affrontavo sperimentalmente, costruendo tabelle e verificando le varie combinazioni al computer, può così essere risolto mediante semplici proprietà della divisione intera e dell’aritmetica modulare.
Riferimenti bibliografici
- Le pile di Gergonne, primo articolo.
- Le pile di Gergonne 2 - Approfondimento, secondo articolo.
-
J. Harrison, T. Brennan, S. Gapinski, The Gergonne p-pile problem and the dynamics of the function x → (x + r)/p, Discrete Applied Mathematics 82 (1998), 103–113. ↩
-
Nel novembre 2026 ho inviato a Elsevier una richiesta formale di correzione del paper di Harrison, Brennan e Gapinski (1998), segnalando un errore negli esponenti presenti nel Lemma 3.1 e nel Teorema 3.2: il termine $p^{m-i}$ dovrebbe essere sostituito con $p^{i-1}$. La segnalazione, già anticipata al prof. Harrison nel 2017, è stata registrata da Elsevier con il riferimento n. 261107-010194. La documentazione della correzione proposta è disponibile qui. ↩