Tag Archives: principio dei cassetti

Solo con zero e uno

Immagino sia noto a tutti che se un numero ha come fattori primi solo 2 e 5, esiste un suo multiplo che è una potenza di 10. Sapete anche tutti che 111 è un multiplo di 3, e 111.111.111 un multiplo di 9. Combinando quelle proprietà, vediamo anche che 1110 è un multiplo di 6, e magari ricordate anche che 1001 è multiplo di 7, di 11 e di 13, essendo il loro prodotto. A questo punto potrete magari chiedervi se è vero o no che dato un qualunque numero intero ci sia un suo multiplo che contenga solo le cifre 1 e 0. Che ne dite?

La risposta è affermativa, e una possibile dimostrazione sfrutta una proprietà che potrebbe sembrare fuori luogo in questo caso: il principio dei cassetti, quello che afferma che se metto k+1 calzini in k cassetti allora almeno un cassetto conterrà due calzini. (Ne avevo parlato qui sul Post). Dato un numero qualunque n, prendiamo i numeri 1, 11, 111, … fino a quello composto da n+1 cifre 1, e consideriamo il resto della divisione per n di ciascuno di questi numeri. Otterremo n+1 risultati, tutti compresi per definizione tra 0 e n−1, e quindi al più di n valori diversi; per il principio dei cassetti almeno due di tali resti, diciamo quello del numero con p cifre e di quello con q cifre, devono pertanto avere lo stesso valore. Per fissare le idee immaginiamo che p>q e che il resto comune della divisione dei due numeri per n sia r. A questo punto basta prendere i due numeri corrispondenti e sottrarli tra loro: avremo un numero della forma 111…111000…000, con pq 1 e q 0, che per costruzione è multiplo di n. Infatti esso è la differenza di un multiplo di n più r, e di un altro multiplo di n sempre più r; possiamo raccogliere insieme i due multipli ed eliminare gli r.

Chi ha studiato matematica un po’ più avanzata (a livello universitario di base) e conosce la funzione totiente φ(n) (il numero di numeri inferiori a n e primi con esso) e il Piccolo teorema di Fermat nella generalizzazione di Eulero, che afferma che se a è primo con n allora aφ(n) ≡ 1 (mod n) può anche calcolare una stima superiore per il numero minimo di cifre di un tale multiplo. Se n è primo con 10, infatti, sappiamo che 10φ(9n) ≡ 1 (mod 9n), e pertanto (10φ(9n)−1)/9 è composto da φ(9n) cifre 1. Se invece n è della forma 2a5b, a seconda se a è maggiore o minore di b lo possiamo moltiplicare per 5a−b o 2b−a e ottenere una potenza di 10 (se a=b la potenza ce l’abbiamo già). Combinando i due risultati possiamo dire che un limite superiore per il numero di cifre del multiplo è φ(9n)|a−b|.

Il principio dei cassetti

La matematica è difficile? Dipende probabilmente da cosa intendete per “matematica” e da chi siete. Come per ogni attività, c’è chi la trova tanto astrusa da non sapere da dove iniziare e chi invece la sente come una cosa istintiva… a meno naturalmente che non si metta a leggere la dimostrazione dell’Ultimo Teorema di Fermat. Su questo blog il livello matematico è di base, almeno secondo me; immagino che per chi non mi legge sia comunque troppo alto. Ma in matematica non c’è il concetto “one size fits all”!

Detto questo, esistono alcune proprietà matematiche che, almeno nel loro enunciato, sono riconosciute come semplici da praticamente chiunque, ma che portano comunque a conseguenze non banali, che a prima vista possono sembrare complicate da risolvere e fanno quasi paura a chi non è “matematico dentro”. Oggi parlo di una di queste, sperando di mostrarvi come in fin dei conti non esisterà una via regia alla matematica, ma se si prende la strada giusta non si è costretti a scalare una parete di sesto grado. Il teorema, almeno in Italia, è noto come principio dei cassetti.

Continue reading Il principio dei cassetti