La base fattoradicale (II)

La conversione in base fattoradicale permette anche di numerare in ordine intelligente le permutazioni di n elementi. Qual è per esempio la 2023-ma permutazione di sette elementi? Scriviamo gli elementi come {0,1,2,3,4,5,6} e leggiamo da sinistra a destra 2441010!. La prima cifra è un 2; contiamo fino a due (partendo da zero, qui siamo informatici più che matematici) e tiriamo fuori il numero trovato, che è 2. I nostri elementi restano quindi {0,1,3,4,5,6}. Proseguiamo in questo modo: dalla nuova lista contiamo da 0 a 4, troviamo 5 e lasciamo {0,1,3,4,6}; poi prendiamo 6 e lasciamo {0,1,3,4}, prendiamo 1 e lasciamo {0,3,4}, prendiamo 0 e lasciamo {3,4}, prendiamo 4 e lasciamo {3} e infine prendiamo 3. (Visto che avere la posizione zero può servire?). Mettendo insieme i numeri otteniamo la permutazione {2,5,6,1,0,4,3). L’unicità della rappresentazione fattoradicale ci assicura che in questo modo troveremo tutte e sole le permutazioni possibili.
Un altro esempio di uso dei numeri fattoradicali (stavolta senza la cifra finale) è dato dai codici di Lehmer; come vedete nella pagina di Wikipedia relativa, questi codici tanto per cambiare codificano le permutazioni di n elementi, ma questa volta lo fanno per mezzo delle inversioni, cioè gli scambi di due elementi. Se date un’occhiata alla tabella, le colonne le r consistono proprio nei numeri fattoradicali scritti da destra a sinistra, e la somma delle “cifre” è proprio il numero di inversioni necessarie per partire dalla permutazione di base {1,2,3,4} per arrivare a quella voluta.
Evelyn Lamb afferma che questo può servire anche per il problema dei bagni chimici ai festival musicali britannici, come da video di Numberphile; a me non sembra, ma tant’è. Ad ogni modo, buon divertimento!
(figura di Tilman Piesk da Wikimedia Commons, CC-BY-SA 3.0)

Se vi dicessi che ho scritto l’anno 2023 in una certa base e mi è venuto fuori 2441010, mentre il 2024 si rappresenta come 2441100, riuscireste a indovinare la base? Probabilmente no, a meno che non abbiate visto e studiato la vignetta qui a fianco. Ho infatti scritto i numeri in 


Il paradosso di Banach-Tarski è ben noto a chi ha studiato matematica. Quallo che succede è che è possibile tagliare una sfera in cinque parti secondo una certa regola, traslare questi “pezzi” che sono stati ottenuti, e ricavare due sfere identiche a quella di partenza. Dov’è il trucco? Beh, ce ne sono almeno due. Il primo è che i pezzi ottenuti sono una specie di polvere diffusa: tecnicamente si dice che non sono insiemi misurabili, e quindi non è in realtà fisicamente possibile crearli. Il secondo trucco è che è necessario usare l’assioma della scelta per poter creare questi pezzi; l’assioma della scelta è una di quelle proprietà che sembrano intuitive, ma che sfuggono a ogni tentativo di dimostrazione – non per nulla è un assioma… – e soprattutto possono portare a paradossi, come si vede. Però esistono risultati simili che non richiedono l’assioma della scelta, come vedremo.

Un tipo ha un cestino di mele. Io gli chiedo “qual è il peso medio di una delle tue mele?” e lui risponde “142 virrgola 857 grammi”. Cosa posso inferire da questa frase? Che il mio interlocutore non ha idea di come si arrotondano i risultati, che il cestino contiene 7 mele, o un multiplo di 7, e probabilmente che la bilancia che ha usato non è molto sensibile. Quel numero si ottiene infatti dividendo 1000 per 7 e mantenendo un numero assurdo di cifre, che sono tutto tranne che significative.