Il principio dei cassetti è uno degli strumenti più usati nei giochi matematici, ma anche nella matematica “seria”. La sua formulazione, almeno per come viene di solito riportata in Italia (anche Wikipedia lo definisce così) è la seguente: “se abbiamo una cassettiera con n cassetti, in qualunque modo ci mettiamo dentro n+1 oggetti possiamo essere certi che almeno un cassetto conterrà almeno due oggetti”.

Dimostrare il principio dei cassetti è così facile che sembra che ci sia qualcosa sotto. Numeriamo gli oggetti da 1 a n+1, prendiamo i primi n e li mettiamo in un cassetto, evitando di metterne due nello stesso cassetto sennò abbiamo perso. Alla fine l’ultimo oggetto rimasto deve andare da qualche parte, ma tutti i cassetti sono occupati.

Uno dei problemi più noti che sfruttano il principio dei cassetti è quello di mostrare come a Roma ci siano due persone con lo stesso numero di capelli. La dimostrazione consiste nello stimare il massimo numero di capelli che può avere in testa una persona, verificare che è minore del numero di abitanti nella capitale, e applicare il principio dei cassetti. Questo è però un classico caso di problema malposto: la soluzione è anche corretta, ma basta passarsi la mano in testa e con ogni probabilità vi rimarrà qualche capello (a meno che non siate calvi…) e quindi non esiste un momento in cui si possa stabile quali siano le due persone co-tricotiche. Ma anche nome e attribuzione del problema fanno una certa confusione!

Peter Gustav Lejeune Dirichlet usò il principio in un suo lavoro del 1842 sulle equazioni di Pell (equazioni quadratiche di cui si cercano le soluzioni intere), e in molte nazioni soprattutto nell’Europa dell’est si parla infatti di principio di Dirichlet oppure di principio dei cassetti di Dirichlet. Non che lui gli avesse dato un nome, ritenendo evidentemente la cosa troppo banale; solo in seguito l’ha chiamato “Schubfach Prinzip” che sta appunto per “principio del cassetto” (singolare). Pat Ballew riporta però un’attestazione precedente – e fin qui nulla di strano, vista l’ovvietà del principio – in un’opera inaspettata: i Portraits littéraires di Charles Augustin Sainte-Beuve, che riporta l’esempio dei capelli e lo fa risalire a Pierre Nicole, giansenista contemporaneo di Pascal che a sua volta l’avrebbe preso da Jean Leurechon.

Nel mondo anglosassone la parola “Schubfach” (o l’equivalente francese “tiroir”) è stata resa con “pigeonhole” perché quello era il nome delle strutture con tanti piccoli spazi dove mettere le buste, che magari avete ancora visto alla reception di un vecchio albergo. Solo che poi chi come noi l’inglese non lo mastica tanto bene ha preso il significato letterale, e adesso si sente parlare del principio della piccionaia. Considerata la quantità di deiezioni dei pennuti, preferisco continuare a parlare di cassetti…

Se volete verificare di aver compreso bene il principio, eccovi tre problemi.

• I 15 cavalieri della tavola rotonda hanno pasteggiato un po’ troppo prima di sedersi a discutere, e quando si sono seduti nessuno di essi era seduto al proprio posto. Dimostrate che è possibile ruotare la tavola in modo che ci siano almeno due persone al posto corretto.
• Se scegliete sei numeri interi tra 1 e 999 ce ne saranno almeno due la cui differenza è un multiplo di 5.
• Avete una bilancia a due piatti e 28 monete, una delle quali è più pesante delle altre. Dimostrate che non è possibile trovare quale sia la moneta più pesante con tre pesate.

Un’ultima cosa. Naturalmente il principio dei cassetti non vale se i cassetti sono infiniti: se abbiamo una fila infinita di cassetti numerati 1, 2, 3, 4, … e prendiamo gli ℵ₀+1 numeri pari con in più 1, possiamo lasciare quanti buchi vogliamo. Ma c’è anche chi ha affermato che il principio è violato nella fisica quantistica, e possiamo avere tre particelle in due scatole senza che nessuna particella contenga più di una particella. Si direbbe ovvio che uno degli autori del paper faccia di cognome Colombo :-). Purtroppo però a quanto pare l’interpretazione data dagli autori di quell’articolo sembra errata…

(immagine da FreeSVG)

La settimana scorsa abbiamo visto come si scrive la base fattoradicale. Un paio dei miei ventun lettori si è chiesto come mai si usa anche la posizione relativa a 0!, che tanto è sempre 0 e quindi non porta informazione. In effetti potete trovare anche la rappresentazione senza questa cifra; ma ho preferito lasciarla per poter ampliare il conto ai numeri frazionari. L’estensione ha comunque qualche problema, perché (-1)!, (-2)! e così via non sono definiti; quello che si fa in pratica è usare gli inversi dei fattoriali, 1/1, 1/2, 1/6, 1/24, …, 1/n!, …; chiaramente anche la prima cifra dopo la virgola è sempre zero, e quindi se avete proprio bisogno di spazio potete toglierla insieme alla cifra immediatamente a sinistra. Basta che avvisiate. Già che ci sono, aggiungo un’altra notazione: come potete immaginare, numeri molto grandi (o numeri frazionari molto lunghi) possono usare cifre maggiori di 10. Per evitare di inventare simboli, si possono usare i numeri in base 10 e separare le “cifre” con un “:”; pertanto 2441010_! si può anche scrivere come 2:4:4:1:0:1:0_!.

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 Lehrer; 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 base fattoradicale; un modo indubbiamente fantasioso, come vedremo. La base fattoradicale è un sistema a base mista: le posizioni da destra a sinistra corrispondono ai multipli dei successivi numeri fattoriali, con la regola aggiuntiva ma logica che non è possibile che nella posizione $n$ da destra non si possa usare un coefficiente maggiore di $n$; a differenza delle usuali basi numeriche si può però usare $n$. (Ricordo che $n! = 1 \cdot 2 \cdot \ldots \cdot n$; per convenzione 0! = 1, ma nel nostro caso tutti i numeri naturali in base fattoradicale finiscono per 0). Pertanto $2441010_{!} = 2(6!)+4(5!)+4(4!)+1(3!)+0(2!)+1(1!)+0(0!)$, il che in effetti non è molto semplice da leggere. Come in genere si scrive $2023_{10}$ per dire che il numero è in base 10, per la base fattoradicale si usa un punto esclamativo come pedice.

Non è difficile dimostrare che ogni numero naturale si può scrivere in un solo modo in base fattoradicale; il trucco è notare che quando il coefficiente relativo alla posizione $n$ arriva a $n+1$ abbiamo esattamente $(n+1)!$ e quindi possiamo fare il riporto esattamente come nelle basi di numerazione usuali; l’unica differenza è che il riporto cambia a ogni nuova posizione, invece che arrivare allo stesso valore. Non è nemmeno troppo difficile convertire un numero dalla base 10, o se per questo da qualunque base fissa, alla base fattoradicale. La cifra più a destra, come dicevo sopra, è sempre 0; poi si comincia a dividere il numero per 2, 3, 4… e il resto della divisione è la cifra da aggiungere man mano a sinistra. Abbiamo così
$$
\begin{array}{c c c}
(2023/1 & = 2023) & 0 \\\hline
2023/2 & = 1011 & 1 \\\hline
1011/3 & = 337 & 0 \\\hline
337/4 & = 84 & 1 \\\hline
84/5 & = 16 & 4 \\\hline
16/6 & = 2 & 4 \\\hline
2/7 & = 0 & 2
\end{array}
$$

Ma a che serve scrivere un numero in fattoradicale, considerando che come dice xkcd se superi la posizione corrispondente a 9! devi inventarti dei nuovi simboli? Per esempio per un trucco di magia matematica, come racconta Tom Edgar. Mischiate un mazzo di carte, chiedete a un membro del pubblico di prendere un mazzetto di 24 carte e sceglierne una mentre non guardate, e di mischiare di nuovo il mazzatto. A questo punto vi girate verso il pubblico e chiedete a una seconda persona di dire qual è il numero che preferisce tra 1 e 24. Prendete il mazzetto e fate due file di 12 carte alternando da una fila all’altra, e chiedete alla prima persona in quale fila si trova la carta da lui scelta. Mettete una fila sopra l’altra e fate stavolta tre file di 8 carte, chiedendo sempre dove si trova la carta scelta; infine fate quattro file di sei carte e chiedete ancora una volta dove si trova la carta scelta. Prendete le carte, rimettetele insieme e cominciate a girarle: la carta prescelta dalla prima persona sarà esattamente nella posizione corrispondente al numero detto dalla seconda persona!

Come è possibile? Potete facilmente immaginare che il trucco sia legato alla base fattoradicale. In effetti i numeri da 0 a 23 possono essere scritti con al massimo quattro cifre fattoradicali, dove l’ultima è sempre 0 e possiamo toglierla. Se ora per esempio il secondo membro del pubblico ha scelto il numero 14, togliamo 1 e otteniamo 13, cioè $2010_{!}$. Tolto lo zero di destra, le cifre da destra a sinistra sono 1, 0, 2; sommiamo a ciascuna 1 e otteniamo 2, 1, 3. Questo vuol dire che dopo la prima fase il mazzetto con la carta scelta deve essere messo in seconda posizione, dopo la seconda fase il nuovo mazzetto deve stare in prima posizione e dopo la terza fase in terza posizione. Abbiamo in pratica scritto il numero prescelto in base fattoradicale, e se contiamo a una a una le carte lo troviamo. Con un po’ di allenamento e di memoria per calcolare a mente la conversione in base fattoradicale il gioco riesce facilmente: e non avere un numero prefissato di file a ogni passo rende più difficile scoprire il trucco.

Ma c’è qualche proprietà più utile dei numeri in base fattoradicale? Lo vedremo la prossima volta! (no, quello non è un simbolo di fattoriale)

(immagine di xkcd, CC-BY-NC 2.5)

Ultimo aggiornamento: 2024-12-17 16:40