Giochi matematici #049 — Le formiche sul bastone: quando cadrà l’ultima?

Quando due formiche identiche si incontrano e si voltano, quale differenza si osserva rispetto a due formiche che continuino dritte attraversandosi?

Se ignoriamo le etichette individuali, la posizione delle due formiche, subito prima e subito dopo l’incontro, coincide nei due modelli. Si scambia soltanto l’identità di chi percorre i due rami.

Immagina ora nove «formiche fantasma», ciascuna delle quali ignora le altre e continua nella propria direzione iniziale fino a un estremo.

Per una formica fantasma che comincia a distanza x dall’estremità sinistra, il tempo è x secondi se va a sinistra e 100 − x secondi se va a destra. La domanda riguarda il massimo di questi nove tempi, non la somma.

La risposta: da 50 a 90 secondi

Il tempo più breve possibile è 50 secondi; quello più lungo è 90 secondi. Mostriamo perché questi limiti valgono per tutte le direzioni iniziali e perché entrambi si possono ottenere.

Il trucco delle formiche indistinguibili

Consideriamo due formiche identiche che avanzano una verso l’altra a uguale velocità. Se si urtano e invertono il verso, le loro traiettorie si incontrano e tornano indietro. Ma se, nell’istante dell’urto, ci limitiamo a scambiare le etichette delle due formiche, otteniamo esattamente le traiettorie di due punti che si attraversano senza interagire.

Questa equivalenza continua a valere dopo ogni urto: in ciascun istante l’insieme delle posizioni occupate dalle formiche reali è lo stesso delle posizioni delle nove formiche fantasma. Lo si verifica tra due collisioni, dove i moti sono rettilinei, e al momento della collisione, dove i punti occupano la stessa posizione. Di conseguenza, anche l’istante in cui il bastone diventa vuoto è identico nei due modelli.

La formula per ogni disposizione

Indichiamo con x_i la posizione iniziale della formica i, in centimetri. Definiamo il tempo fantasma t_i = x_i se la sua direzione è sinistra, oppure t_i = 100 − x_i se è destra; con velocità 1 cm/s, i valori sono espressi in secondi.

Il tempo dell’ultima caduta è dunque T = max(t₁, …, t₉). Gli incontri possono cambiare quale formica reale raggiunge un estremo, ma non questo numero.

Perché il minimo è 50

La formica che parte esattamente da 50 cm impiega almeno 50 secondi per raggiungere un’estremità, qualunque verso scelga. Poiché esiste un percorso fantasma di 50 secondi, T ≥ 50 in ogni configurazione.

Possiamo raggiungere questo limite: facciamo partire verso sinistra le formiche ai punti 10, 20, 30 e 40; verso destra quelle a 60, 70, 80 e 90; quella al centro può scegliere una delle due direzioni. Ogni fantasma va all’estremo più vicino; il suo percorso dura al massimo 50 secondi. Quindi T = 50.

Perché il massimo è 90

Per le nove posizioni date, qualsiasi distanza percorsa in una direzione iniziale è al massimo 90 cm: il fantasma posto a 10 cm, andando verso destra, percorre 90 cm; simmetricamente quello a 90 cm, andando verso sinistra, percorre 90 cm. Dunque T ≤ 90.

Basta far partire la formica di posizione 10 verso destra per avere un fantasma che cade dopo esattamente 90 secondi; gli altri non possono impiegare più tempo. Questo dimostra che il massimo è 90 secondi. Non va confuso con il limite generale di 100 secondi valido per un bastone di 100 cm con formiche in posizioni iniziali arbitrarie, anche molto vicine agli estremi.

Una verifica con due formiche

Prendiamo due formiche: A a 20 cm, verso destra; B a 70 cm, verso sinistra. Si incontrano dopo 25 secondi nel punto 45 cm. Rimbalzando, A cade a sinistra al secondo 70 e B a destra al secondo 80. Nel modello fantasma, A prosegue a destra e cade al secondo 80, B prosegue a sinistra e cade al secondo 70. Le identità delle cadute si scambiano, i tempi no.

La scorciatoia si chiama spesso principio dello scambio di identità. Non afferma che le formiche reali passino l’una attraverso l’altra: afferma soltanto che due modelli producono lo stesso insieme di posizioni, quando non ci interessa distinguere individui identici.

Per una lunghezza generica L e una velocità comune v > 0, con posizioni x_i fra 0 e L, il tempo massimo di svuotamento, date le direzioni, è T = (1/v) max_i{x_i se sinistra, L − x_i se destra}. Al variare indipendente dei versi, il minimo è (1/v) max_i min{x_i, L − x_i}, mentre il massimo è (1/v) max_i max{x_i, L − x_i}.

Le ipotesi contano: velocità uguali, inversioni istantanee, nessuna sosta, un solo segmento. Con velocità differenti o comportamenti diversi agli urti, lo scambio di etichette non conserva automaticamente i moti. Si veda anche la spiegazione del problema nelle Math Fun Facts dell’Harvey Mudd College.

Cambiamo bastone: 120 cm, cinque formiche nelle posizioni 20, 40, 60, 80 e 100 cm, tutte a 2 cm/s. Quali sono il minimo e il massimo tempo dell’ultima caduta?

La formica centrale deve percorrere 60 cm in una delle due direzioni, quindi servono almeno 30 secondi; facendo andare ciascuna verso l’estremo più vicino, bastano proprio 30 secondi. Per il massimo scegliamo un fantasma a 20 cm diretto a destra, che percorre 100 cm a 2 cm/s: 50 secondi.

Prova anche a spiegare perché il numero di collisioni non compare in nessuno dei due risultati.

Questa stessa trasformazione si ritrova negli algoritmi: in alcune simulazioni di particelle identiche su una linea, eliminare gli scambi di etichette permette di calcolare un risultato globale senza aggiornare una lunga sequenza di urti.

C’è però un’informazione che il modello fantasma da solo non restituisce: quale formica reale, identificata da un colore o da un nome, cadrà da un dato estremo. Per rispondere a quella domanda è necessario ricostruire gli scambi di identità. Per sapere soltanto quando il bastone sarà vuoto, no.