4 - THE PIGEONHOLE PRINCIPLE (PHP)
|
Il “Principio dei Cassetti”, detto anche “Principio di Dirichlet” (ma noi useremo invece il termine inglese PIGEONHOLE PRINCIPLE, abbreviato PHP) afferma questo:
“Se n piccioni devono occupare k buchi, e n>k (il numero dei piccioni supera il numero dei buchi), allora almeno uno dei buchi verrà a contenere almeno 2 piccioni”
Nei problemi, i “piccioni” sono oggetti, concreti o astratti (ad es. numeri) mentre i “buchi” sono proprietà che tali oggetti possono possedere.
L’affermazione è del tutto ovvia; comunque: se per assurdo, con n piccioni e k buchi, e n>k, il numero dei piccioni in ogni buco fosse <2, allora il numero totale dei piccioni sarebbe
quindi NON potrebbe essere uguale a n.
|
Qui abbiamo 10 piccioni ( n = 10 ) in 9 buchi ( k = 9 ).
(Pigeons-in-holes.jpg by B. McKay; GNU Free Documentation License) |
|
Esiste anche una VERSIONE GENERALIZZATA del principio, ossia:
“Se n piccioni devono sistemarsi in k buchi, e n>k (il numero dei piccioni supera il numero dei buchi), allora almeno uno dei buchi verrà a
contenere almeno osserviamo che, dovendo il numero dei piccioni essere intero, questo
Per assurdo: supponiamo di avere n piccioni e k buchi, con n>k; se il numero dei piccioni in ogni buco fosse <n/k, allora il numero totale dei piccioni sarebbe
e NON potrebbe quindi essere uguale a n.
|
|
Il principio viene associato al nome di Dirichlet, matematico tedesco che lo adoperò nel 1834
sotto il nome di Schubfachprinzip ("principio dei cassetti").
Parecchi problemi, di effettivo interesse applicativo o di carattere “giocoso”, sono risolubili attraverso il PHP.
Non si tratta in genere di problemi di facile risoluzione:
in effetti, di norma è piuttosto spontaneo riconoscere che la risposta a un dato quesito è in qualche modo legata
al PHP, però non è poi così elementare capire quali siano, in quel particolare contesto, i “piccioni” ed i “buchi”.
Facciamo alcuni esempi.
a) Supponiamo che ciascun punto di un piano sia colorato: o di blu, o di rosso. Dimostrare che
in quel piano deve per forza esistere una coppia di punti a distanza uguale a 1, aventi lo stesso colore.
Dimostrazione
Consideriamo, sul piano in questione, un qualunque triangolo equilatero di lato uguale a 1.
Esso ha tre vertici (piccioni!) mentre i colori disponibili (buchi!) sono soltanto 2.
Pertanto, per il PHP, ci dovranno essere (almeno) due fra i vertici, colorati con lo stesso colore.
Tali due vertici sono i punti di cui si domandava di dimostrare l’esistenza.
b) Fra 6 interi, ce ne sono sempre senz’altro almeno 2 la cui differenza è un multiplo di 5: dimostralo!
Dimostrazione
Consideriamo i resti che si ottengono dividendo per 5 ciascuno di quei 6 interi.
Il resto di una divisione per 5 può valere 0, 1, 2, 3 o 4: non ci sono altre possibilità.
Abbiamo dunque solo 5 buchi (i possibili resti), con 6 piccioni (gli interi considerati).
Ci dovranno perciò essere, per il PHP, almeno due piccioni in uno stesso buco,
ossia almeno due interi che, divisi per 5, danno lo stesso resto.
Bene: la differenza fra quei due interi sarà un multiplo di 5, C.V.D.
|
c) Provare che in qualsiasi poliedro esistono sempre due facce aventi lo stesso numero di lati.
Dimostrazione In un poliedro, ogni faccia “confina” con altre facce: tante facce, quanti sono i lati della faccia iniziale. Se in totale le facce di un poliedro sono n, il numero massimo di facce con cui una data faccia
può confinare è
|
|
|
E allora ciò significa che ogni faccia di un
poliedro con potrà avere 3 lati, 4 lati, … ma fino a un massimo
di Se pensiamo di considerare, per ogni faccia, il numero dei suoi lati, ossia se trattiamo le facce come “piccioni” e i numeri possibili di lati come “buchi”, abbiamo più piccioni che buchi e perciò almeno due facce dovranno avere lo stesso numero di lati, C.V.D.
d) 9 persone siedono in una fila di 12 sedie. Dimostra che nella fila c’è almeno una terna di sedie consecutive occupate.
Dimostrazione Qui si potrebbe anche trovare il modo di utilizzare il PHP, ma è più semplice ragionare PER ASSURDO. Se non ci fosse mai una terna di sedie consecutive occupata, la configurazione in grado di garantire il numero massimo di persone sedute sarebbe 2-vuota-2-vuota-2-vuota-2-vuota oppure vuota-2-vuota-2-vuota-2-vuota-2 per un totale di 8 persone sedute soltanto. Non ci sarebbe posto per la nona persona. E’ perciò assurdo supporre che non si abbiano mai più di 2 posti consecutivi occupati: deve esistere per forza una sequenza di 3 o più posti occupati di seguito, C.V.D.
e) Ci sono 200 cestini di noci. E nessun cestino è vuoto, ma si sa pure che nessuno contiene più di 48 noci. Dimostra che fra questi cestini, ce ne sono almeno 5 con esattamente lo stesso numero di noci.
Dimostrazione Sfrutteremo la forma generalizzata del PHP. I piccioni sono 200, e i buchi sono 48. Esiste perciò almeno un buco in cui vanno a finire almeno 200/48 = 4, … ossia, passando al più piccolo intero non inferiore, almeno 5 piccioni. Vale a dire: ci sono perlomeno 5 cestini che portano lo stesso numero di noci.
I seguenti due quesiti, decisamente più difficili, sono tratti dal meraviglioso sito Prima di sbirciare la soluzione, cimentati per conto tuo. Aspettati, però, una riflessione davvero impegnativa, specie per il secondo!
f) At a party of N people, some pair of people are friends with the same number of people at the party.
Solution 1 A person at the party
can have 0 up to However, if someone
has 0 friends at the party, then no one at the party has and if someone has Hence the number of possibilities for the number of friends the N people at the party have must be less than N. Hence two people at the party have the same number of friends at the party.
Solution 2 Può essere la tua … oppure: valla a cercare sul sito, nel quale trovi anche una terza risoluzione.
g) Suppose each point of the plane is colored red or blue. Show that some rectangle has its vertices all the same color.
Draw three horizontal lines. We'll find a rectangle with vertices on two of these. The other sides are vertical. At the intersection with the three horizontal lines, every vertical line has three candidate points to serve as vertices of the sought rectangle. Three points may be colored with 2 colors in 8 different ways. So, if you choose 9 vertical lines, there are bound to be triplets of points colored in the same manner. Select any two triplets colored in the same way - this gives you vertical sides. In any triplet, at least two points are of the same color. Select two such - this gives you horizontal sides.
|
|
ESERCIZI (alcune risposte e risoluzioni, ma volutamente non tutte, sono al termine della rassegna)
1) Dimostra che fra 400 persone, ce ne sono almeno 2 che festeggiano il compleanno nel medesimo giorno.
2) Al centro di una circonferenza viene piazzato un goniometro a 360°. Si scelgono, sulla circonferenza,
200 punti, corrispondenti ad angoli al centro la cui ampiezza sia di un numero intero di gradi.
Dimostra che, fra questi punti, ce n’è almeno una coppia “agli antipodi”, ossia tale che la loro congiungente
passi per il centro (Indicazione: i “buchi” siano “le coppie di punti agli antipodi” …)
3) Comunque si scelgano 10 punti su di un triangolo equilatero di lato 1, ne esistono sempre almeno 2
la cui distanza è (Indicazione: suddividi il triangolo
equilatero dato in…)
4) Dati 5 interi, ce ne sono almeno 2 la cui differenza è divisibile per 4.
E in generale, dati n
interi, ce ne sono almeno 2 la cui differenza è divisibile per
5) Gli 85 partecipanti ad un pranzo in trattoria possono scegliere fra 4 possibili primi piatti.
Dimostra che almeno in 22 sceglieranno la medesima portata.
6) Nel gioco della tombola, intervengono gli interi da 1 a 90.
Dimostra che, dopo 46 estrazioni, è certo che almeno due dei numeri usciti siano consecutivi.
7) Dimostra che avendo 100 interi, se ne possono sempre scegliere 15 tali che la differenza
fra due qualsiasi di essi sia divisibile per 7 (Manhattan Mathematical Olympiad 2005)
8) Dimostra che a Milano ci sono sempre, istante per istante,
più persone che hanno esattamente lo stesso numero di capelli in testa.
9) Si scelgono a caso 4 interi. La loro somma è 30.
Allora certamente almeno uno dei 4 numeri è non inferiore a … ?
10) Sto recuperando i vecchi albi a fumetti che avevo accatastato in ordine sparso in soffitta.
Ce ne sono in tutto 120, di cui 40 di “Topolino”, 30 di “Tex”, 28 di “Zagor” e 22 di “Alan Ford”.
Ora mi diverto a pescare a caso gli albi per la lettura.
Quanti ne devo estrarre dal mucchio per essere certo che ce ne siano almeno 2 della stessa serie?
11) Se un test poteva fruttare un punteggio intero da 0 a 10, e 48 studenti lo hanno effettuato,
posso esser certo che al minimo k studenti avranno ottenuto il medesimo punteggio. Quanto vale k?
12) Ci sono 35 tavoli circolari e 110 sedie vengono disposte intorno ad essi.
Dimostra che ci sarà almeno un tavolo intorno al quale verranno disposte almeno 4 sedie.
13) Su di una circonferenza di raggio unitario vengono scelti 7 punti.
Dimostra che fra questi punti, ce ne sono almeno 2 a distanza <1.
14) Su di una circonferenza di raggio 3, ci sono 19 archi di lunghezza unitaria.
Siamo certi che almeno 2 fra questi archi siano parzialmente sovrapposti?
15) Dimostra che, se n piccioni occupano k buchi, c’è almeno un buco che contiene non più di n/k piccioni.
|
Da http://www.cut-the-knot.org/do_you_know/pigeon.shtml, che propone parecchi esercizi di questo tipo, alcuni dei quali molto impegnativi:
16) Prove that there exist two powers of 3 whose difference is divisible by 1997.
17) In a tournament where each team meets every other team once, there are always two teams that played the same number of games.
|
Per procurarti altri problemi interessanti, ti basta digitare “Principio dei Cassetti” o “Pigeonhole Principle” su Google.
|
18) DIFFICILE. Vengono scelti a caso 10 interi nell’intervallo da 1 fino a 100. Dimostra che l’insieme di
questi 10 interi deve per forza avere almeno due sottoinsiemi non vuoti, con ugual somma degli elementi.
19) DIFFICILE, estensione dell’esempio g). Se ciascun punto di un piano è colorato, e può esserlo
in rosso, nero, o blu, allora esiste in quel piano un rettangolo i cui vertici sono tutti dello stesso colore.
20) DIFFICILE. 17 parlamentari di una federazione di Stati, nella quale ci sono 3 lingue ufficiali,
interloquiscono fra di loro in modo che ogni coppia di parlamentari dialoga con una e 1 sola di tali lingue.
Dimostra che esistono almeno 3 persone che comunicano fra loro utilizzando la stessa lingua
(riformulazione di un quesito della IMO, International Mathematical Olympiad, 1964)
21) DIFFICILE. In un gruppo di 6 persone, ne esistono sempre (almeno) 3
che si conoscono a due a due, oppure che sono a due a due estranee
(diamo qui per scontato che il “conoscersi” sia sempre simmetrico: se A conosce B, anche B conosce A).
22) DIFFICILE. Dati 52 numeri interi, almeno due di essi sono tali che la loro somma o la loro differenza
è divisibile per 100: dimostra questa affermazione.
23) DIFFICILE, assegnato alla American Mathematical Olympiad 1981.
Supponiamo di avere 27 distinti numeri interi dispari, tutti minori di 100.
Dimostra che fra essi c’è sempre almeno una coppia avente per somma 102.
24) DIFFICILE. Ogni insieme di 17 interi contiene 5 interi la cui somma è divisibile per 5! Dimostralo.
25) DIFFICILE. Dati 101 interi scelti nell’intervallo da 1 a 200, fra di essi ne esistono senz’altro almeno due
tali che uno sia divisore dell’altro.
Da http://yusuf1505.web.ugm.ac.id/kuliahku/
26) 15 children together gathered 100 nuts. Prove that some pair of children gathered the same number of nuts.
27) Prove that among any set of 51 positive integers less than 100, there is a pair whose sum is 100.
ALCUNE RISPOSTE, E RISOLUZIONI DI ESERCIZI DIFFICILI
9) 8 10) 5 11) 5 14) Sì: la circonferenza è lunga … mentre la somma degli archi … 15) Per assurdo
18) Quanti sono i
possibili sottoinsiemi di un insieme di 10 elementi? .
E quelli non vuoti? Evidentemente 1023. Quante sono le diverse somme ottenibili prendendo come addendi
da 1 a 10 interi scelti nell’intervallo da 1 a 100? Beh, la somma più piccola vale 1 (questa viene dall’insieme
unitario
che ha come elemento il più piccolo dei numeri in gioco), e la somma più grande
possibile è invece .
Si hanno dunque 955 possibili somme. Ma gli insiemi sono 1023, quindi si hanno più piccioni che buchi.
Almeno un buco dovrà essere occupato da almeno 2 piccioni, vale a dire:
ci saranno certamente 2 insiemi caratterizzati dalla stessa somma.
20) Prendiamo una qualsiasi delle 17 persone: chiamiamola per fissare le idee P1.
Essa interloquisce, nell’una o nell’altra delle 3 lingue, con 16 persone, e di conseguenza,
per il PHP generalizzato, dovrà comunicare con almeno 6 di queste attraverso l’uso della stessa lingua L1.
Se 2 fra tali 6 persone comunicano fra di loro sempre con L1,
ecco che quelle 2, insieme con P1, formano il gruppo di 3 cercato.
Altrimenti, tutte le 6 persone comunicheranno fra loro in una delle lingue L2 o L3.
Prendiamo una qualunque di tali 6 persone: chiamiamola P2.
P2, quando comunica con le altre 5 persone,
dovrà per forza rivolgersi con la stessa lingua, diciamo L2, ad almeno 3 di esse.
Se 2 fra queste 3 utilizzano sempre L2 per comunicare fra loro,
ecco che insieme a P2 formano il gruppo di 3 cercato.
Altrimenti, le 3 persone comunicheranno attraverso L3, e formeranno esse stesse il famoso gruppo di 3.
Il quale dunque, in qualsiasi caso, esiste, come volevasi dimostrare.
21) Ci semplifichiamo la vita se illustriamo il problema geometricamente. Rappresentiamo le nostre
6 persone con 6 punti; se 2 persone si conoscono le collegheremo con un segmento, altrimenti no.
Si tratta di dimostrare che esiste sempre un insieme di 3 punti che sono
TUTTI collegati fra loro (triangolo) oppure MAI collegati fra loro.
Prendiamo uno qualsiasi dei 6 punti, chiamandolo P per fissare le idee.
Pensiamo ai 5 punti rimanenti: P potrà, con ciascuno di essi, essere collegato oppure no.
2 possibilità, 5 punti: una di queste possibilità si verificherà per almeno 3 dei 5 punti.
Dunque senz’altro il punto P
a) sarà collegato con almeno 3 dei rimanenti
b) oppure non sarà collegato con almeno 3 dei rimanenti.
Supponiamo che si verifichi l’eventualità a). Allora sono possibili 2 sottocasi:
♪ fra i 3 punti, almeno 2 son collegati fra loro
(e allora, insieme con P, formano una terna di punti a due a due collegati)
♫ oppure nessuno dei 3 punti è collegato con gli altri 2 (e abbiamo così una terna di punti non collegati).
Supponiamo invece che si verifichi l’eventualità b). 2 sottocasi:
♪ fra i 3 punti, almeno 2 non sono collegati fra loro
(e allora, insieme con P, formano una terna di punti a due a due non collegati)
♫ oppure ciascuno dei 3 punti è collegato con gli altri 2 (e abbiamo così una terna di punti collegati).
23) I numeri in
questione sono “pescati” dall’insieme .
Possiamo considerare ora
tutte le coppie la cui somma è 102, ossia
e aggiungere a questo
elenco i due insiemi unitari aventi per elementi ciascuno un “orfanello”: e
.
Ecco qui dunque 24+2=26 insiemi. Abbiamo così 26 “buchi” (gli insiemi) e 27 “piccioni” (i numeri iniziali).
Almeno due piccioni devono stare, per il PHP, nello stesso buco, quindi
almeno due fra i nostri numeri devono stare nello stesso insieme e perciò dare per somma 102, C.V.D.
26) Proof by contradiction. Suppose all the children gathered a different number of nuts.
Then the fewest total number
is ,
but this is more than 100, a contradiction.