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 fare 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)

Prendiamo il numero 742. Così ad occhio non ci dice molto; se però costruiamo una successione simil-Fibonacci partendo dalle sue cifre, sommandole e continuando a sommare gli ultimi tre numeri ottenuti ricaviamo

7, 4, 2, 13, 19, 34, 66, 119, 219, 404, 742, 1365, …

Come vedete, a un certo punto della successione otteniamo il numero di partenza. I numeri che hanno questa proprietà si chiamano numeri di Keith, dal nome del matematico Mike Keith che li propose nel 1987. (Per completezza lui li definì “repfigit”, nel senso di “cifre di Fibonacci replicate”)

I numeri di una cifra sono banalmente di Keith, ma non li si considera tali perché sarebbe barare. Il più piccolo numero di Keith in base 10 è così 14 (1, 4, 5, 9, 14), seguito da 19, 28, 47, 61, 75, 197 e appunto 742. Non si sa molto su questi numeri: nemmeno se sono finiti o infiniti in una data base. Keith ha congetturato che se si lavora in base 10 ci siano in media tre numeri di Keith con un numero dato di cifre; ma il valore è molto variabile, visto che ci sono 10 numeri di Keith di 6 cifre e 7 di 27 cifre, ma non ce ne sono con 10 cifre e ce ne sono solo uno di 24 e 25 cifre rispettivamente. Nonostante alcune tecniche permettano di ridurre la quantità di conti da fare, trovarli è molto laborioso, perché essenzialmente richiede un approccio a forza bruta: fino al 2009 si conoscevano solo 95 numeri di Keith, tutti quelli con al più 34 cifre. Ma nel dicembre 2022 il matemago Toon Baeyens dell’università di Gand ne ha trovati altri nove, di 35 e 36 cifre, portando il totale a 104. Il più grande numero di Keith conosciuto è pertanto 880430656963418264331749765271577784.

La figura all’inizio, che mostra i divisori (piccoli) dei primi 94 numeri di Keith, mostra un comportamento un po’ buffo: certi fattori primi proprio non appaiono, mentre gli altri seguono più o meno il comportamento che ci aspetteremmo da un insieme di numeri, che cioè una frazione 1/p di essi fosse divisibile per p. È un caso? secondo me sì, ma non ditelo in giro :-) Purtroppo la teoria dei numeri è piena di proprietà come questa, di cui si può dimostrare ben poco: se siete ottimisti è un segnale di come la struttura dei numeri sia incredibilmente complessa, se siete pessimisti è un segnale di come la struttura dei numeri sia incredibilmente incasinata…

(figura da Numbers Aplenty)

Tutti conosciamo la media aritmetica: presi due numeri, la loro media aritmetica è la metà della loro somma, o se preferite il numero che è alla stessa distanza dai due di partenza: dunque $ M_A(x,y) = \frac{x+y}{2} $ .

Quasi tutti conosciamo la media geometrica: presi due numeri, la loro media geometrica è la radice quadrata del loro prodotto, o se preferite il numero che è il lato di un quadrato della stessa superficie di un rettangolo di lati i due numeri. Dunque $ M_G(x,y) = \sqrt{xy} $. È facile dimostrare che la media geometrica di due numeri positivi è sempre inferiore o uguale alla loro media aritmetica, ed è uguale se e solo se i due numeri sono uguali: per confrontare $ \frac{x+y}{2} $ e $ \sqrt{xy} $ basta prima raddoppiarli e poi elevarli al quadrato.

Alcuni conoscono anche la media armonica: presi due numeri, la loro media armonica è l’inverso della media aritmetica dei loro inversi, o se preferite la velocità media complessiva di due tratti uguali di strada percorsi a due diverse velocità. M_H (x, y) = 2xy/(x+y). La media armonica è ovviamente musicale: se fate la media di due note do a un’ottava di distanza ottenete un fa. Se si conosce il trucco, è facile dimostrare che la media armonica di due numeri positivi è sempre inferiore o uguale alla loro media geometrica, ed è uguale se e solo se i due numeri sono uguali: sappiamo da sopra che $ \frac{1}{x} + \frac{1}{y} \geq \sqrt{\frac{1}{x} \frac{1}{y}} $; se prendiamo gli inversi dei due membri, ricordandoci che la diseguaglianza cambia di verso, otteniamo il risultato.

La figura all’inizio del post dà una dimostrazione “visiva” di queste medie, e trovate anche disegnata la “media quadratica”, che è data da $ \sqrt{\frac{x^2 + y^2){2}}. Se avete studiato ingegneria, questa formula dovrebbe esservi nota, perché è il “valore efficace”. Per la cronaca, la media quadratica di due numeri positivi è sempre maggiore o uguale della media aritmetica, ed è uguale se e solo i due numeri sono uguali; per dimostrarlo si usa la disuguaglianza di Cauchy-Schwarz.

Ma tra le tantissime medie che esistono ce n’è una che probabilmente vi è sconosciuta (lo era anche a me, prima di scrivere questo post): la media eroniana M_E. Essa si ottiene come media pesata di quella aritmetica, presa per due terzi, e di quella geometrica, presa per un terzo. Abbiamo dunque $ M_E = \frac{2}{3}\frac{x+y}{2} + \frac{1}{3}\sqrt{xy} = \frac{1}{3}(x + \sqrt{xy} + y)$. Per costruzione è chiaro che la media eroniana di due numeri positivi è compresa tra quella aritmetica e quella geometrica. Erone è stato probabilmente il più grande geometra del periodo alessandrino; l’importanza di questa media – che si comporta come ogni media che si rispetti, nel senso che è simmetrica e che se applicata a due valori uguali dà quello stesso valore – è che può essere usata per calcolare il volume di un tronco di piramide a base quadrata, che è dato dal prodotto della media eroniana delle basi per l’altezza.

Un aneddoto: come dice la pagina di Wikipedia in inglese, quella formula era nota già agli antichi egizi. Quando ero alle medie, mia avevano fatto costruire un modellino in cartoncino per una conferenza dove veniva fatta un’ipotesi su come gli egizi fossero arrivati alla formula. Insomma, è vero che non la conoscevo con quel nome ma ho avuto a che fare con essa già quasi cinquant’anni fa!

(immagini da Wikimedia Commons: QM_AM_GM_HM_inequality_visual_proof.svg, di CMG Lee, CC-BY-SA4.0, Square_frustum.png, di MarinaVladivostok, CC0 1.0)

Ultimo aggiornamento: 2024-01-06 17:20

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.

Consideriamo il numero complesso x = eⁱ. Sì, è possibile elevare un numero a una potenza immaginaria, e il risultato è ancora un numero complesso, nel nostro caso almeno secondo Wolfram Alpha all’incirca 0,54030 + 0,84147 i. Quello che conta è che però quel numero è trascendente e quindi non è la radice di nessun polinomio a coefficienti interi. (Ok, io non saprei dimostrarlo, ma mi fido che sia così). Bene, prendiamo l’insieme S dei valori dei polinomi a coefficienti interi non negativi (per esempio, 5x³ + 2x + 42) calcolati nel punto x. Ciascuno di questi valori corrisponde a un punto del piano complesso; tutti questi punti devono essere distinti, perché se due di questi polinomi avessero lo stesso valore allora la loro differenza varrebbe zero, il che è assurdo per definizione perché x è trascendente. Dividiamo ora S in due sottoinsiemi A e B, in questo modo: A contiene tutti e soli i polinomi di S che non hanno un termine costante, mentre B contiene tutti gli altri polinomi di S, vale a dire quelli che hanno un termine costante. È chiaro che per costruzione A ∪ b = S. Cosa succede ora se ruotiamo di un radiante (cioè di 1/2π di circonferenza) in senso orario l’insieme A? Eulero ci ha insegnato che questa rotazione è la stessa cosa che moltiplicare per e⁻ⁱ, e l’algebra di scuola ci dice che questo è la stessa cosa che dividere per eⁱ. Quindi otteniamo tutti i polinomi in x a coefficienti positivi, cioè il nostro insieme S. E se invece spostiamo a sinistra di un’unità l’insieme B? Beh, otteniamo di nuovo tutti gli elementi di S, perché i termini costanti in B partono da 1 in su e se togliamo 1 otteniamo tutti i termini costanti da 0 in su. Dunque abbiamo costruito esplicitamente un insieme che può essere diviso in due parti che traslate e ruotate formano due copie dello stesso insieme. Carino, no? Come dice il titolo, questo paradosso è stato trovato da Sierpinski e Mazurkiewicz, due matematici polacchi. Non che S sia un insieme disegnabile: essendo costituito da un’infinità numerabile di punti discreti, la sua misura (generalizzazione del concetto di area che si usa in analisi) è nulla.

Se la cosa vi pare troppo complicata, eccovi un esempio più semplice e galileiano. Prendiamo come insieme N i numeri naturali e dividiamoli in quelli pari P e quelli dispari D. Ora, se dividiamo per 2 gli elementi di P otteniamo N, e se togliamo 1 dagli elementi di D e poi li dividiamo per 2 otteniamo di nuovo N. Tutto questo funziona perché i numeri sono infiniti, naturalmente; ma mentre in questo secondo caso dobbiamo comunque fare un’operazione (quella di divisione) che pare sparigliare nel caso precedente abbiamo solo trasformazioni rigide. Carino, no?

(immagine di xkcd: la vignetta completa è qui.)