Se ci sono più piccioni che piccionaie, almeno una piccionaia contiene più di un piccione.
1. L’idea fondamentale
Il principio delle piccionaie, detto anche principio dei cassetti o principio di Dirichlet, nasce da un’osservazione semplicissima: se dobbiamo distribuire più oggetti che contenitori, almeno un contenitore riceverà più di un oggetto. La sua forza emerge quando i «piccioni» e le «piccionaie» sono nascosti: persone e mesi, numeri e resti, punti e regioni geometriche, sottoinsiemi e somme, numeri e parti dispari.
- Piccioni = gli oggetti che stiamo distribuendo.
- Piccionaie = le categorie nelle quali li classifichiamo.
2. Forma generale
Se N oggetti vengono distribuiti in k contenitori, almeno un contenitore contiene almeno ⌈N / k⌉, dove ⌈x⌉ indica il più piccolo intero maggiore o uguale a x. Per esempio, distribuendo 25 persone nei 12 mesi dell’anno, almeno un mese contiene almeno 3 persone, perché 25/12 è maggiore di 2.
3. Formula inversa
Quanti oggetti servono per essere certi che almeno una piccionaia contenga r oggetti? Possiamo mettere al massimo r − 1 oggetti in ciascuna delle k piccionaie senza raggiungere r. Il massimo è k(r − 1); l’oggetto successivo forza il risultato: k(r − 1) + 1.
4. Il metodo del caso peggiore
Molti problemi si risolvono immaginando la distribuzione più sfavorevole possibile: si evita il risultato richiesto il più a lungo possibile e poi si aggiunge un ultimo oggetto. In sintesi: massimo possibile senza raggiungere l’obiettivo + 1.
5. Venticinque problemi svolti
Problema 1 - I mesi
In una classe ci sono 13 studenti. Dimostrare che almeno due sono nati nello stesso mese.
Soluzione
Le 13 persone sono i piccioni e i 12 mesi sono le piccionaie. Poiché 13 > 12, almeno un mese contiene almeno due compleanni.
Problema 2 - Tre persone nello stesso mese
Quante persone servono per essere certi che almeno 3 siano nate nello stesso mese?
Soluzione
Possiamo mettere al massimo 2 persone in ciascuno dei 12 mesi: 12 × 2 = 24. La venticinquesima obbliga almeno un mese ad avere 3 persone. Risposta: 25.
Problema 3 - Calzini al buio
In un cassetto ci sono calzini di 5 colori diversi. Quanti bisogna prendere al buio per essere certi di averne almeno due dello stesso colore?
Soluzione
Nel caso peggiore i primi 5 calzini sono tutti di colore diverso. Il sesto deve ripetere uno dei 5 colori. Risposta: 6.
Problema 4 - Quattro calzini dello stesso colore
Ci sono calzini di 6 colori. Quanti bisogna estrarne per essere certi di averne almeno 4 dello stesso colore?
Soluzione
Possiamo estrarne 3 per ciascun colore senza arrivare a 4 uguali: 6 × 3 = 18. Il successivo forza un quarto calzino di qualche colore. Risposta: 19.
Problema 5 - Resti modulo 5
Si scelgono 6 numeri interi qualsiasi. Dimostrare che almeno due hanno lo stesso resto nella divisione per 5.
Soluzione
I possibili resti sono 0, 1, 2, 3, 4: soltanto 5 piccionaie. Con 6 numeri, due devono avere lo stesso resto.
Problema 6 - Differenza multipla di 5
Dimostrare che fra 6 numeri interi esistono sempre due numeri la cui differenza è divisibile per 5.
Soluzione
Dal problema precedente due numeri hanno lo stesso resto modulo 5. Se a = 5q + r e b = 5p + r, allora a − b = 5(q − p): la differenza è multipla di 5.
Problema 7 - Giorni della settimana
In un gruppo di 15 persone, dimostrare che almeno 3 sono nate nello stesso giorno della settimana.
Soluzione
Se ciascuno dei 7 giorni contenesse al massimo 2 persone, avremmo 7 × 2 = 14 persone. La quindicesima forza un giorno a contenerne almeno 3.
Problema 8 - Ultima cifra
Si scelgono 11 numeri naturali. Dimostrare che almeno due terminano con la stessa cifra.
Soluzione
Le possibili ultime cifre sono 0, 1, 2, …, 9: dieci possibilità. Con 11 numeri, almeno due hanno la stessa ultima cifra.
Problema 9 - Differenza multipla di 10
Si scelgono 11 numeri interi. Dimostrare che esistono due numeri la cui differenza è multipla di 10.
Soluzione
Classifichiamo i numeri secondo il resto modulo 10. Esistono 10 classi; con 11 numeri due finiscono nella stessa classe, quindi la loro differenza è divisibile per 10.
Problema 10 - Almeno cinque
In una scuola ci sono 101 studenti distribuiti in 25 classi. Dimostrare che almeno una classe contiene almeno 5 studenti.
Soluzione
Se ogni classe avesse al massimo 4 studenti, il totale sarebbe al massimo 25 × 4 = 100. Poiché gli studenti sono 101, almeno una classe ne contiene almeno 5.
Problema 11 - Due numeri consecutivi
Si scelgono 6 numeri distinti dall’insieme {1,2,…,10}. Dimostrare che almeno due sono consecutivi.
Soluzione
Raggruppiamo i numeri nelle 5 coppie (1,2), (3,4), (5,6), (7,8), (9,10). Scegliendo 6 numeri, almeno due appartengono alla stessa coppia e sono quindi consecutivi.
Problema 12 - Perché con 5 non basta?
Nel problema precedente, 5 numeri sarebbero sufficienti?
Soluzione
No. Il controesempio {1,3,5,7,9} contiene 5 numeri ma nessuna coppia di consecutivi. Quindi 6 è la soglia minima.
Problema 13 - Due numeri con somma 11
Si scelgono 6 numeri distinti tra 1 e 10. Dimostrare che almeno due hanno somma 11.
Soluzione
Creiamo le 5 coppie (1,10), (2,9), (3,8), (4,7), (5,6). Ogni coppia ha somma 11. Scegliendo 6 numeri, almeno una coppia viene scelta completamente. Somma = 11.
Problema 14 - Una differenza piccola
Si scelgono 6 numeri distinti tra 1 e 10. Dimostrare che almeno due differiscono al massimo di 1.
Soluzione
Usiamo le coppie (1,2), (3,4), (5,6), (7,8), (9,10). Con 6 numeri due cadono nella stessa coppia; essendo distinti, differiscono esattamente di 1.
Problema 15 - Numeri da 1 a 100
Si scelgono 51 numeri distinti tra 1 e 100. Dimostrare che almeno due sono consecutivi.
Soluzione
Dividiamo i 100 numeri nelle 50 coppie (1,2), (3,4), …, (99,100). Con 51 scelte, almeno una coppia è interamente scelta.
Problema 16 - Differenza divisibile per 7
Si scelgono 8 numeri interi qualsiasi. Dimostrare che due di essi differiscono per un multiplo di 7.
Soluzione
Ogni intero ha uno dei 7 resti 0,1,2,3,4,5,6 modulo 7. Con 8 numeri, due hanno lo stesso resto; la loro differenza è divisibile per 7.
Problema 17 - Centouno numeri tra 1 e 200
Si prendono 101 numeri interi distinti compresi tra 1 e 200. Dimostrare che almeno due differiscono meno di 2.
Soluzione
Essendo distinti e interi, differire meno di 2 significa differire esattamente di 1. Formiamo le 100 coppie (1,2), (3,4), …, (199,200). Con 101 numeri almeno una coppia è interamente scelta.
Problema 18 - Punti in un quadrato
In un quadrato di lato 2 vengono scelti 5 punti. Dimostrare che almeno due distano non più di √2.
Soluzione
Dividiamo il quadrato in 4 quadrati di lato 1. Due dei 5 punti cadono nello stesso quadratino. La distanza massima è la diagonale: d ≤ √2.
Problema 19 - Dieci punti nel quadrato
In un quadrato di lato 3 vengono scelti 10 punti. Dimostrare che almeno due distano non più di √2.
Soluzione
Dividiamo il quadrato in 9 quadrati di lato 1. Con 10 punti, due cadono nello stesso quadratino e la loro distanza è al massimo la diagonale √2.
Problema 20 - Persone e conoscenze
In una festa ci sono 6 persone. Ogni coppia o si conosce oppure non si conosce. Dimostrare che esistono sempre tre persone che si conoscono tutte fra loro oppure tre persone nessuna delle quali conosce le altre due.
Soluzione
Scegliamo una persona A. Tra le altre 5, almeno 3 sono tutte conoscenti di A oppure almeno 3 sono tutte non conoscenti di A. Nel primo caso, se due di quelle 3 si conoscono formano con A un terzetto di conoscenti; se nessuna coppia si conosce, quelle 3 formano un terzetto di estranei. Il secondo caso è simmetrico. È un piccolo esempio di teoria di Ramsey.
Problema 21 - Stesso numero di amici
A una festa ci sono n ≥ 2 persone. Dimostrare che almeno due hanno lo stesso numero di amici presenti alla festa.
Soluzione
Ogni persona potrebbe avere da 0 a n − 1 amici, ma i valori 0 e n − 1 non possono comparire contemporaneamente: se qualcuno conosce tutti, nessuno può avere 0 amici. Ci sono quindi al massimo n − 1 valori effettivamente possibili per n persone; almeno due condividono lo stesso numero di amici.
Problema 22 - Due sottoinsiemi con la stessa somma
Si scelgono 10 numeri interi positivi non superiori a 100. Dimostrare che esistono due sottoinsiemi diversi con la stessa somma.
Soluzione
Consideriamo le dieci scelte come posizioni distinguibili, anche se due valori coincidessero. Generano 2¹⁰ = 1024 sottoinsiemi di posizioni, compreso quello vuoto. La somma totale è al massimo 1000, perciò le somme possibili sono al massimo 1001, da 0 a 1000. Poiché 1024 > 1001, due sottoinsiemi diversi hanno la stessa somma.
Problema 23 - Somme parziali
Siano a₁,a₂,…,aₙ interi qualsiasi. Dimostrare che esiste un blocco di termini consecutivi la cui somma è divisibile per n.
Soluzione
Consideriamo le n somme parziali S₁=a₁, S₂=a₁+a₂, …, Sₙ=a₁+…+aₙ. Se una è divisibile per n, abbiamo finito. Altrimenti i loro resti sono soltanto 1,…,n − 1: n somme in n − 1 classi. Due somme Sᵢ e Sⱼ hanno lo stesso resto. La differenza Sⱼ − Sᵢ = aᵢ₊₁+…+aⱼ è quindi divisibile per n.
Problema 24 - Divisibilità nascosta
Si scelgono 51 numeri distinti dall’insieme {1,2,…,100}. Dimostrare che tra essi esistono sempre due numeri tali che uno divide l’altro.
Soluzione
Ogni intero positivo si scrive in modo unico come 2^k·m con m dispari. Classifichiamo i numeri secondo la parte dispari m. Tra 1 e 100 ci sono 50 possibili parti dispari. Con 51 numeri, due hanno la stessa parte dispari: 2^a·m e 2^b·m. Se a<b, il secondo è 2^(b−a) volte il primo, quindi il primo divide il secondo.
Problema 25 - Successione crescente o decrescente
Si scelgono 10 numeri distinti e li si scrive in un certo ordine. Dimostrare che esiste sempre una sottosuccessione crescente di almeno 4 numeri oppure una sottosuccessione decrescente di almeno 4 numeri.
Soluzione
Per ogni termine xᵢ associamo Cᵢ, lunghezza della più lunga sottosuccessione crescente che termina in xᵢ, e Dᵢ, analoga lunghezza decrescente. Se non esistessero sottosuccessioni di lunghezza 4, avremmo Cᵢ,Dᵢ ∈ {1,2,3}: solo 9 coppie possibili (Cᵢ,Dᵢ) per 10 termini. Due termini avrebbero la stessa coppia. Ma per due posizioni i<j, se xⱼ>xᵢ aumenta la lunghezza crescente, mentre se xⱼ<xᵢ aumenta quella decrescente. La stessa coppia è impossibile: contraddizione. 3 × 3 = 9 < 10.
6. Che cosa rende difficili questi problemi?
Nei primi esercizi le piccionaie sono evidenti: mesi, colori, classi, giorni. Nei problemi più interessanti devono essere inventate. Possono essere resti di una divisione, coppie di numeri, intervalli, regioni geometriche, parti dispari, somme possibili o coppie di caratteristiche. Il principio matematico resta elementare; la difficoltà vera consiste nello scegliere la classificazione giusta.
7. Strategia generale
- Quali sono i piccioni?
- Quali possono essere le piccionaie?
- Quante piccionaie esistono?
- Qual è il massimo numero di oggetti che posso sistemare senza ottenere il risultato?
- Cosa succede aggiungendo un oggetto?
Domanda chiave: in quale modo posso classificare gli oggetti affinché il principio delle piccionaie diventi inevitabile?