Page 28 - progetto alice

S. Capparelli, P. Maroscia Alcuni problemi di matematica discreta A questo punto, c’è solo da notare che i valori 0, n – 1, non possono mai presentarsi simultaneamente! Infatti, se tra i partecipanti alla festa c’è una persona che non incontra nessun amico, non può esserci una persona che sia amica di tutti (e viceversa). Siamo giunti così in dirittura di arrivo: da un lato abbiamo n persone e dall’altro abbiamo al più n – 1 valori disponibili per il numero degli amici dei partecipanti alla festa, sicché almeno due di 6 questi valori devono coincidere , e il problema è così risolto. È importante sottolineare che l’osservazione piuttosto semplice, quasi banale, che abbiamo utilizzato per concludere la dimostrazione, costituisce in realtà uno dei principi fondamentali nello studio della matematica discre- ta. Esso va sotto il nome di “Principio delle gabbie dei piccioni” e può essere così enunciato (cfr. Aigner, Ziegler (2006), Maroscia (2002)): “Se n piccioni si distribuiscono in m gabbie e se n è maggiore di m, allora almeno una gabbia conterrà due piccioni (n > m 1).” Per dare un’idea dell’utilità e anche della potenza di tale Principio, segna- liamo un problema non banale che può essere risolto facilmente grazie ad esso (per i dettagli, cfr. Aigner, Ziegler (2006)): “Dimostrare che, presi comunque n + 1 numeri tra i primi 2n numeri na- turali, con n 1 fissato, vi sono sempre almeno due numeri tra gli n + 1 scelti, tali che uno è un multiplo dell’altro.” Per esempio, se tra i primi 10 numeri naturali, scegliamo i numeri: 4, 5, 6, 7, 9, 10 tale proprietà si verifica subito. (Si noti che, se consideriamo solo i 5 nume- ri: 4, 5, 6, 7, 9, il risultato precedente non sarebbe più vero; dunque per la sua validità è necessario prendere n + 1 numeri…). Vedremo più avanti che il Principio delle gabbie dei piccioni ci permetterà di risolvere anche il Problema 6, l’ultimo della lista. Per finire, facciamo vedere che il Problema 2 può essere risolto anche per altra via, ricorrendo a una dimostrazione per assurdo. 6 Basta pensare, per esempio, a quello che succede quando 5 persone devono entrare in una macchina con 4 posti: due di esse devono sistemarsi necessariamente una sull’altra.