{"id":966,"date":"2012-11-16T05:59:21","date_gmt":"2012-11-16T04:59:21","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=966"},"modified":"2017-01-22T15:55:43","modified_gmt":"2017-01-22T14:55:43","slug":"il-principio-dei-cassetti","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2012\/11\/16\/il-principio-dei-cassetti\/","title":{"rendered":"Il principio dei cassetti"},"content":{"rendered":"

La matematica \u00e8 difficile? Dipende probabilmente da cosa intendete per “matematica” e da chi siete. Come per ogni attivit\u00e0, c’\u00e8 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 \u00e8 di base, almeno secondo me; immagino che per chi non mi legge sia comunque troppo alto. Ma in matematica non c’\u00e8 il concetto “one size fits all”!<\/p>\n

Detto questo, esistono alcune propriet\u00e0 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 \u00e8 “matematico dentro”. Oggi parlo di una di queste, sperando di mostrarvi come in fin dei conti non esister\u00e0 una via regia alla matematica, ma se si prende la strada giusta non si \u00e8 costretti a scalare una parete di sesto grado. Il teorema, almeno in Italia, \u00e8 noto come principio dei cassetti<\/b>.<\/p>\n

Innanzitutto enuncio il teorema, nella forma che ho imparato io.<\/p>\n

Se abbiamo N<\/i>+1 oggetti da mettere in N<\/i> cassetti, allora possiamo essere certi che alla fine ci sar\u00e0 almeno un cassetto che avr\u00e0 almeno due oggetti al suo interno.<\/p><\/blockquote>\n

Qui stiamo facendo matematica, anche se di livello basilare, e pertanto le parole sono importanti, soprattutto quei due “almeno”. Potremmo per esempio avere due cassetti con due oggetti, oppure avere tutti gli oggetti in un unico cassetto: quello che conta \u00e8 che non riusciremo mai, in qualunque modo facciamo la suddivisione, a fare in modo che ciascun cassetto abbia un solo oggetto, oppure non ne abbia nessuno. Vi serve la dimostrazione? Eccovela qua: notate che in un certo senso, anche se \u00e8 per assurdo, \u00e8 costruttiva e pertanto istruttiva. Prendiamo i primi N<\/i> oggetti: ogni volta dobbiamo cercare un cassetto vuoto per inserirli, altrimenti avremmo un cassetto con due oggetti. Il guaio \u00e8 che ce ne rimane in mano ancora uno, e da qualche parte dobbiamo pur metterlo!<\/p>\n

Esiste anche una formulazione un po’ diversa del principio, enunciata da E. W. Dijkstra – non esattamente l’ultimo arrivato nel campo.<\/p>\n

Dato un qualunque insieme non-vuoto di numeri reali, il valore massimo tra essi \u00e8 almeno pari alla media dei valori.<\/p><\/blockquote>\n

(io aggiungerei una postilla “e pu\u00f2 essere uguale se e solo se tutti i valori sono uguali”, ma all’atto pratico ce ne facciamo poco, quindi \u00e8 inutile appesantire l’affermazione).<\/p>\n

Prima di mostrare alcune delle svariate applicazioni del principio dei cassetti – applicazioni rubate da Mind Your Decisions<\/a>, per la cronaca – vi lascio con un po’ di storia. Sembra che il principio sia stato esplicitato per la prima volta nel 1834 da Dirichlet, che lo battezz\u00f2 col nome tedesco di Schubfachprinzip, per l’appunto “principio del cassetto”. Gli inglesi per\u00f2 preferiscono chiamarlo “pigeonhole principle”: ma il pigeonhole non \u00e8 la piccionaia! Magari lo era nel 1577, data di prima attestazione del lemma<\/a>: ma nel diciannovesimo secolo il termine era gi\u00e0 usato nel senso di “cassetta per la posta”, nemmeno poi troppo diverso dalla cassettiera dirichletiana. Solo che si sa, le traduzioni sono sempre un po’ pericolose…<\/p>\n

Ed ecco a voi dieci applicazioni del principio! D’accordo, molte non saranno il massimo dell’utilit\u00e0, ma possono comunque servire in una serata da amici…<\/p>\n

1. A Milano ci sono due persone che hanno lo stesso numero di capelli.<\/em>
\nIl numero di capelli di un essere umano \u00e8 sicuramente inferiore a 500.000. Poich\u00e9 a Milano risiede pi\u00f9 di un milione di persone, anche eliminando i calvi, ne consegue che ce ne devono essere almeno due con lo stesso numero di capelli. Anzi, si pu\u00f2 dire di pi\u00f9: considerando la seconda forma del principio dei cassetti, si pu\u00f2 affermare che esiste almeno un gruppo di tre persone con lo stesso numero di capelli.<\/p>\n

2. Negli USA, tra i tacchini consumati il giorno del Ringraziamento ce ne sono due il cui peso \u00e8 lo stesso al milligrammo.<\/em>
\nUn tacchino pesa in media 7 chili, e il pi\u00f9 grande tacchino mai visto sfiorava i 17 kg. Ci possono essere dunque al pi\u00f9 17 milioni di pesi diversi, calcolati al milligrammo, per i tacchini: ma si stima che negli USA si consumino 46 milioni di tacchini nel giorno del Ringraziamento, quindi sicuramente se ne troveranno due dello stesso peso. (Poi possiamo discutere se ha senso misurare il peso di un tacchino al milligrammo…)<\/p>\n

3. Alla prima della Scala ci saranno almeno due persone con le stesse iniziali.<\/em>
\nCi sono ventisei lettere possibili per il nome e il cognome di una persona, per un totale di 26 × 26 = 676 possibilit\u00e0 complessive. La capienza della Scala<\/a> \u00e8 di 2013 posti, e alla prima si pu\u00f2 immaginare che ci sia il tutto esaurito: sicuramente due persone avranno pertanto le stesse iniziali. (Notate come non sia possibile essere certi che ci siano quattro<\/b> persone con le stesse iniziali, perch\u00e9 2013\/676 \u00e8 leggermente minore di 3. Certo \u00e8 improbabile pensare a frotte di Xavier Jacobelli e nomi simili, e io scommetterei senza problemi sull’esistenza di un quartetto, e se per questo anche di un quintetto, di persone con le stesse iniziali: ma un conto \u00e8 una probabilit\u00e0 altissima, un conto la certezza.)<\/p>\n

4. Scegliendo a caso cinque carte da un mazzo di 52, almeno due devono essere dello stesso seme.<\/em>
\nI semi sono quattro…<\/p>\n

5. Se in un cassetto :-) ci sono 10 calzini neri e 20 blu, e li si prende a caso, ne basta prendere tre per averne due dello stesso colore.<\/em>
\nGli insiemi da considerare sono i calzini neri e quelli blu, quindi due. Una volta arrivati al terzo calzino, entra in gioco il principio dei cassetti.<\/p>\n

6. Scegliendo sei numeri tra 1 e 10, se ne potr\u00e0 sempre trovare due la cui somma \u00e8 11.<\/em>
\nAccoppiamo 1 e 10, 2 e 9, 3 e 8, 4 e 7, 5 e 6. Abbiamo cinque gruppi: se scegliamo sei numeri siamo sicuri che ci sar\u00e0 almeno un gruppo di cui verranno scelti entrambi gli elementi. Ma visto che in ciascun gruppo la somma dei due elementi \u00e8 11, siamo a posto.<\/p>\n

7. Scegliendo a caso cinque punti sulla superficie terrestre, possiamo dividere il pianeta a met\u00e0 in modo che quattro dei punti siano sullo stesso emisfero (Un punto sulla linea di taglio si suppone far parte di entrambi gli emisferi)<\/em>
\nDue punti sulla superficie della sfera determinano un cerchio massimo (occhei, se sono antipodali ci sono infiniti cerchi massimi che passano per essi: prendetene uno qualunque). Facendo un taglio che passi per quel cerchio massimo, rimangono altri tre punti. Sicuramente almeno due devono stare su una delle met\u00e0: aggiungendo i due punti sul cerchio massimo, quella mezza Terra avr\u00e0 i quattro punti richiesti.<\/p>\n

8. In una festa con almeno due persone, ci devono essere almeno due persone che hanno lo stesso numero di amici.<\/em> (Supponiamo che la relazione “essere amico di” sia simmetrica: se A<\/i> \u00e8 amico di B<\/i>, allora B<\/i> \u00e8 amico di A<\/i>.)
\nImmaginiamo che ci siano n<\/i> partecipanti alla festa. Ognuno di essi pu\u00f2 essere amico di un numero di persone variabile tra 0 e n-1<\/i> (no, non si \u00e8 amici di s\u00e9 stessi!). Iniziamo a supporre che ciascuno abbia almeno un amico, e associamogli il numero di amici che ha: ci sono allora n<\/i> persone a cui sono associati i numeri da 1 a n<\/i>−1, e per il principio dei cassetti due di loro devono avere lo stesso numero. Cosa succede se c’\u00e8 un imbucato, cio\u00e8 uno senza amici? Beh, nessuno degli altri allora pu\u00f2 avere n<\/i>−1 amici, visto che non conosce l’imbucato; pertanto alle n<\/i> persone si associano i numeri da 0 a n<\/i>−2, che guarda caso sono di nuovo n<\/i>−1.<\/p>\n

9. Sempre con l’ipotesi di “simmetria della conoscenza”, in un gruppo di sei persone o ci sono tre persone ciascuna delle quali conosce entrambe le altre, oppure tre persone nessuna delle quali conosce le altre.<\/em>
\nIl problema pu\u00f2 essere definito geometricamente nel modo seguente: immaginiamo di avere sei punti e tracciare tutti i possibili segmenti che collegano due punti, colorandoli di rosso (conoscenza) o di blu (estraneit\u00e0). Allora o c’\u00e8 un triangolo coi tre lati rossi, oppure uno coi tre lati blu.
\nPartendo da un punto qualunque, consideriamo i cinque segmenti che partono da lui. Per il principio dei cassetti, ce ne devono essere almeno tre di uno stesso colore: senza perdita di generalit\u00e0, possiamo supporre che questo colore sia il rosso. Prendiamo ora questi tre estremi, e consideriamo il triangolo formato da questi tre punti. Se uno dei lati \u00e8 rosso, abbiamo un triangolo rosso con il punto iniziale; altrimenti abbiamo trovato un triangolo blu.<\/p>\n

10. \u00c8 impossibile inventare un algoritmo di compressione dati senza perdita di informazioni (“lossless”) che funzioni sempre, cio\u00e8 a partire da un qualunque file in ingresso ne produca uno in uscita pi\u00f9 corto.<\/em>
\nConsideriamo i file di lunghezza k<\/i> bit. Il loro numero \u00e8 per definizione 2k<\/i><\/sup>: ma i file di lunghezza tra 1 e k<\/i>−1 sono solo 2k<\/i><\/sup>−1, e pertanto dobbiamo avere due file che vengono “compressi” nello stesso file. Come facciamo allora a decomprimere il file compresso e scegliere il risultato corretto? (Lo stesso ragionamento spiega perch\u00e9 quando si crea una funzione hash occorre considerare la possibilit\u00e0 di collisioni, cio\u00e8 di due elementi con la stessa chiave. Naturalmente una compressione “lossy”, cio\u00e8 con perdita di informazione, \u00e8 possibile; e – forse un po’ meno naturalmente – i file che usiamo di solito sono una parte cos\u00ec piccola del numero totale di file possibili che non \u00e8 strano che zipparli funzioni nella pratica.)<\/p>\n

Dopo tutte queste applicazioni teoriche, vi lascio con la storia dell’albergatore che riusc\u00ec a mettere otto persone in sette stanze, lasciandone una per stanza. L’albergatore inizi\u00f2 a mettere temporaneamente le prime due persone nella stanza 1, proseguendo con la terza nella stanza 2, la quarta nella stanza 3, la quinta nella stanza 4, la sesta nella stanza 5 e la settima nella stanza 6. Finalmente pot\u00e9 tornare nella prima stanza, e chiedere all’ultima persona di lasciare la prima da sola, visto che la stanza 7 era pronta per lui. Semplice, no?<\/p>\n","protected":false},"excerpt":{"rendered":"

Il principio dei cassetti \u00e8 una di quelle propriet\u00e0 matematiche cos\u00ec semplici da apparire banali, ma che sono molto utili nelle dimostrazioni. Ecco alcuni esempi.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[168,170],"class_list":["post-966","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-principio-dei-cassetti","tag-teoremi"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-fA","jetpack-related-posts":[{"id":1424,"url":"https:\/\/xmau.com\/ilpost\/2019\/01\/07\/dal-latinorum-al-maticsipsilon\/","url_meta":{"origin":966,"position":0},"title":"Dal latinorum al maticsipsilon","author":".mau.","date":"07\/01\/2019","format":false,"excerpt":"Con i secoli, il modo per camuffarsi dietro un discorso apparentemente sensato ma in realt\u00e0 fallace \u00e8 cambiato.","rel":"","context":"In \"offuscamento\"","block_context":{"text":"offuscamento","link":"https:\/\/xmau.com\/ilpost\/tag\/offuscamento\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1553,"url":"https:\/\/xmau.com\/ilpost\/2019\/08\/19\/un-giuramento-di-ippocrate-per-i-matematici\/","url_meta":{"origin":966,"position":1},"title":"Un giuramento di Ippocrate per i matematici?","author":".mau.","date":"19\/08\/2019","format":false,"excerpt":"L'idea pu\u00f2 sembrare interessante, ma ho dei forti dubbi.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":966,"position":2},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":188,"url":"https:\/\/xmau.com\/ilpost\/2011\/05\/14\/di-elezioni-e-gelatai\/","url_meta":{"origin":966,"position":3},"title":"Di elezioni e gelatai","author":".mau.","date":"14\/05\/2011","format":false,"excerpt":"Ci sono molte teorie matematiche legate alle votazioni, e che generalmente danno risultati deludenti per gli amanti della democrazia a tutti i costi; ma bisogna sempre stare attenti a verificare le ipotesi dietro questi teoremi!","rel":"","context":"In \"elezioni\"","block_context":{"text":"elezioni","link":"https:\/\/xmau.com\/ilpost\/tag\/elezioni\/"},"img":{"alt_text":"[i gelatai convergono]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2011\/05\/gelatai.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2638,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/16\/risolvere-il-gioco-del-quindici-pillole\/","url_meta":{"origin":966,"position":4},"title":"Risolvere il gioco del quindici [Pillole]","author":".mau.","date":"16\/09\/2013","format":false,"excerpt":"Certo, la matematica mostra che il gioco non \u00e8 risolvibile... ma basta cambiare leggermente le regole per riuscirci!","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"due posizioni del gioco del 15","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/09\/il15.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/09\/il15.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/09\/il15.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2634,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/06\/quanto-e-irragionevolmente-efficace-la-matematica\/","url_meta":{"origin":966,"position":5},"title":"Quanto \u00e8 “irragionevolmente efficace” la matematica?","author":".mau.","date":"06\/09\/2013","format":false,"excerpt":"Ogni tanto la banda dei matematici non-platonisti si risveglia. Solo che il matematico tipico di filosofia ne sa ben poca","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=966"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/966\/revisions"}],"predecessor-version":[{"id":967,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/966\/revisions\/967"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}