backup del Post

Numeri fusibili

Immaginate di avere a disposizione un certo numero (grande a piacere, ma finito) di stoppini. Ciascuno stoppino si brucia esattamente in un minuto, ma non brucia necessariamente in modo uniforme, e quindi non potete per esempio dire che quando è arrivato a metà lunghezza è passato mezzo minuto; e – inutile dirlo – non avete nessun orologio a disposizione. È possibile misurare un intervallo di tempo di 30 secondi? e di 45 secondi? Come sempre in questi problemi, si immagina che si possa accendere contemporaneamente un numero qualunque di stoppini; gli unici istanti “misurabili” sono quelli in cui uno stoppino finisce di bruciare. Pertanto si possono misurare due minuti accendendone uno al tempo t=0, e accendendo il secondo al tempo t=1 quando il primo è bruciato; il secondo terminerà di bruciare al tempo t=2.

Per riuscire a dare una risposta a questo quesito, attribuito a Carl Morris, bisogna pensare in modo laterale, e accorgersi che l’unica possibilità che si può avere è accendere uno stoppino contemporaneamente dai due lati: facendo così, lo stoppino si consumerà del tutto una volta passati trenta secondi. Sulle prime non ne ero convinto, visto che come detto lo stoppino non è omogeneo: per convincermene ho dovuto compiere un Gedankenexperiment, sdoppiando lo stoppino e accendendo i due cloni ciascuno su un lato diverso. Il momento in cui la bruciatura arriva allo stesso punto è necessariamente a metà del tempo complessivo, perché altrimenti l’altro stoppino brucerebbe quella parte in un tempo diverso. E per calcolare quarantacinque secondi? Semplice. Oltre ai due lati dello stoppino A, si accende contemporaneamente un altro stoppino B. Quando A è bruciato, B ha ancora mezzo minuto di autonomia; ma se si accende anche l’altro lato lo stoppino si consumerà in 15 secondi, che sommati ai 30 dell’altro stoppino fanno 45 secondi. La figura a destra, presa da questo documento di Jeff Erickson, sintetizza le operazioni da fare per misurare un tempo t=3/4.

Erickson però non si è limitato a risolvere il problema, ma ha pensato di creare una teoria dei numeri fusibili (in inglese, “fuse” può significare stoppino oppure fusibile; però “numeri stoppinici” non mi sembrava una bella cosa). Un numero si dice fusibile se corrisponde a un intervallo di tempo ottenuto usando un numero finito di stoppini che bruciano in 1 unità di tempo. Le regole sono molto rigide. Gli stoppini si possono accendere solo all’istante t=0 oppure nel momento in cui è bruciato uno stoppino, ma se ne possono accendere contemporaneamente quanti se ne vuole; l’intervallo di tempo si misura dal momento di accensione del primo stoppino a quello in cui l’ultimo termina di bruciare; e non si può barare accendendo uno stoppino a metà, oppure spegnendolo e riaccendendolo. È chiaro che il più piccolo numero fusibile maggiore di 0 è 1/2, visto che non possiamo fare altro che accendere uno stoppino ai due estremi; ma poi?

Iniziamo con qualche definizione matematica: se accendiamo un lato di uno stoppino al tempo a e il secondo lato al tempo b, con |a−b|<1, lo stoppino terminerà di bruciare al tempo a~b definito dalla formula (a+b+1)/2, come potete facilmente verificare. Il fatto che i due tempi devono essere a distanza minore di 1 non è un problema: accendendo da un solo lato uno stoppino e aspettando che finisca di bruciare per accenderne un altro possiamo misurare tutti i tempi 0, 1, 2, … e ridurre la differenza tra i due tempi a meno di 1. Bene: abbiamo visto che 0 ~ 0 = 1/2 e che 0 ~ 1/2 = 3/4. È abbastanza facile vedere che 0 ~ 3/4 = 7/8, e andando di questo passo si possono ottenere tutti i numeri della forma (1 – 2^k). Non si raggiunge mai 1, visto che il numero di stoppini che ci servirebbe sarebbe infinito, ma tanto basta usarne 1. Però si può ancora andare avanti! Si ha che 1/2 ~ 1/2 = 1, il che non ci dà nessun nuovo numero fusibile, ma 1/2 ~ 3/4 = 9/8, 1/2 ~ 7/8 = 19/16 e così via, arrivando a un secondo limite pari a 5/4. Ma ci sono ulteriori limiti a livelli sempre più elevati – si può dimostrare che i numeri fusibili sono totalmente ordinati e quindi si possono associare loro i numeri ordinali, ma non divaghiamo – finché il limite del limite del limite… è il numero 2, come si vede nella figura qui sotto presa sempre dal testo di Erickson.

E dopo il 2? Beh, di numeri fusibili ce ne sono davvero tanti. Per darvi un’idea, Erickson ha definito la funzione m(x) come la differenza tra x e il più piccolo numero fusibile strettamente maggiore di x. Se x è negativo, evidentemente m(x) = −x; altrimenti è dato dalla formula ricorsiva m(x) = m(x − m(x −1))/2. Abbiamo che m(0) = 1/2 cioè 2^(−1), come abbiamo visto all’inizio. m(1) = 1/8 cioè 2^(−3), perché possiamo ottenere 9/8; m(2) = 2^(−10) perché si può ottenere 2049/1024. Bene: sappiate che m(3) è uguale a 2^(−1541023937). Quanto a m(4), non si sa quanto sia l’esponente (negativo) a cui è elevato 2, ma dovrebbe essere uno di quei numeri inconcepibili nati solo per essere usati in questi teoremi.

Insomma, da un semplice problemino può uscire tanta matematica. Niente male, vero?

Aggiornamento: (14 luglio) Popinga mi ha segnalato che la funzione m ha una sua entry nell’OEIS. L’unico guaio è che viene indicato questo articolo che afferma (a) che Erickson ha dimenticato alcuni (tanti) numeri fusibili, e fin qui passi; ma soprattutto (b) che l’autore ha una congettura che non riesce a dimostrare per sapere quanti effettivamente sono. Sembra facile…