Sono passati più di due mesi da quando, su questo blog, è uscito un mio articolo relativo alle gare di matematica. Nel frattempo, in ambito olimpico (e non solo) sono accadute molte cose. In data 5 marzo si è tenuta la gara a squadre femminile alla quale hanno preso parte circa 160 squadre. L’11 marzo si sono tenuti i giochi di Archimede (la prova era stata fissata per il 18 febbraio, ma quel giorno problemi informatici hanno costretto gli organizzatori a sospendere e rimandare la competizione). Il prossimo 26 marzo è prevista la gara a squadre mista, anch’essa in modalità online come le precedenti gare a causa delle misure di contenimento del Covid-19. In attesa di tornare alla normalità e di poter gareggiare “in presenza”, vi invitiamo ad allenarvi e ad approfondire argomenti e concetti classici della matematica olimpica.

In questo articolo vogliamo analizzare due principi la cui applicazione è alla base di un gran numero di esercizi delle gare: il principio dei cassetti e il principio di inclusione – esclusione.

Il principio dei cassetti, o principio della piccionaia (pigeonhole, in inglese), afferma che dati $n$ oggetti e $k$ cassetti (con $n>k$), allora almeno un cassetto deve contenere più di un oggetto. Per l’esattezza, deve contenere almeno $\lceil \frac{n}{k} \rceil$ oggetti, ove il simbolo $\lceil x \rceil$ indica la parte intera superiore di x (e.g. $\lceil 4,3 \rceil = 5$ e $\lceil 7 \rceil = 7$). Ad esempio, se si hanno 10 piccioni e 9 gabbie, allora almeno una gabbia deve contenere più di un piccione, ed in particolare ne deve contenere almeno 2. Il principio non stabilisce come devono essere distribuiti i piccioni; potrei ad esempio mettere tutti i piccioni nella stessa gabbia e lasciare vuote le rimanenti (il principio sarebbe comunque verificato), oppure sistemare i volatili come nell’immagine seguente (tratta da wikipedia).

Una generalizzazione del principio dei cassetti è la seguente: dati $n$ oggetti e $k\cdot h$ cassetti (per qualche intero positivo $h$), allora almeno un cassetto contiene $h+1$ oggetti. Ad esempio, se ho 26 piccioni e 4 gabbie, essendo $26>4\cdot6$, allora almeno una gabbia contiene 6+1=7 piccioni.

Mostriamo di seguito degli esempi, alcuni di questi abbastanza classici e ben noti in ambito olimpico.

Si stima che la superficie del capo umano portante capelli è di 775 cm2 e che ogni cm2 contiene al massimo 165 capelli. Dimostrare che in una città di 150.000 abitanti vi sono due persone che hanno lo stesso numero di capelli (tratto da “Giochi di aritmetica e problemi interessanti” di Giuseppe Peano).

Soluzione: poiché il massimo numero di capelli che può avere una persona è $775 \cdot 165=127.875<150.000$, allora si deduce la tesi come conseguenza del principio dei cassetti.

N.B.: per una città come Roma, che conta circa 2.788.000 abitanti (al 31 ottobre 2020 – dato ISTAT), esistono almeno 22 persone che hanno lo stesso numero di capelli…

Dimostrare che ad una festa ci sono due persone che hanno lo stesso numero di amici (si supponga che l’amicizia sia reciproca, vale a dire che se A è amico di B, allora anche B è amico di A).

Soluzione: detto $n$ il numero di persone ad una festa, allora ogni partecipante può avere $0, 1, 2, …, n-2$ o $n-1$ amici. Se tutte le persone avessero un numero diverso di amici, allora ce ne sarebbe una con 0 amici e un’altra con $n-1$ amici, il che è impossibile in quanto la persona con $n-1$ amici è amica di tutti (compreso di colui che ha 0 amici).

Variante: dimostrare che ad una festa ci sono almeno due persone che hanno stretto lo stesso numero di mani.

In un baule ci sono 1000 calzini alla rinfusa, di 100 colori diversi (10 per ciascun colore). C’è buio e non si vede nulla. Determinare il minimo numero di calzini che bisogna prendere per essere sicuri di averne almeno 2 dello stesso colore (gara a squadre di Tor Vergata, 2008).

Soluzione: ne vanno presi 101. Prenderne 100 non basta, in quanto potrebbero essere tutti di colore diverso, mentre se ne prendo 101 allora almeno una coppia sarà dello stesso colore.

In un baule ci sono 10 paia di calzini di colori diversi e 10 paia di guanti degli stessi colori dei calzini. C’è buio e non si vede nulla, e non riesco a distinguere calzini e guanti. Quanti oggetti devo tirar fuori per essere sicuro di avere un set coordinato di guanti e calzini?

Soluzione: nel baule ci sono in totale 40 oggetti (10 paia di calzini e 10 paia di guanti). Se tiro fuori 30 oggetti, è possibile che abbia preso 3 oggetti per ciascun colore. Mi basta allora estrarre un ulteriore oggetto per essere certo di avere un set coordinato di guanti e calzini dello stesso colore.

Dimostra che in una scacchiera 8 x 8 non è possibile posizionare 9 torri in modo tale che nessuna possa attaccare le altre.

Soluzione: ricordiamo che una torre può muoversi lungo una qualunque riga o colonna della scacchiera. Per il principio dei cassetti, esiste una riga (o una colonna) con almeno due torri, che quindi possono attaccarsi a vicenda.

Alle elezioni comunali del paese di Vattelapesca, si presentano come aspiranti sindaci tre persone. Sapendo che gli aventi diritto al voto sono 2.380 persone e tutte quante si sono recate a votare, qual è il numero minimo di voti che deve ottenere un candidato per poter sperare di vincere?

Soluzione: per il principio dei cassetti, ci sarà almeno un candidato che avrà ottenuto $\lceil \frac{2380}{3} \rceil = 794$ voti. Tale valore è anche il numero cercato (infatti potrebbe accadere che gli altri due sfidanti hanno ottenuto ciascuno 793 voti, con 793+793+794=2.380).

Consideriamo l’intera popolazione italiana (che approssimiamo per semplicità a 60 milioni di abitanti), divisa fra maschi e femmine, e supponiamo che non ci sia nessuno che abbia 10 o più figli. Dimostrare che esistono almeno 13 persone dello stesso sesso, con lo stesso numero di figli, lo stesso compleanno e le stesse prime due lettere del nome.

Soluzione: si tratta anche questa volta di applicare il principio dei cassetti sapendo che $\lceil \frac{6\cdot 10^{7}}{2\cdot 10 \cdot 26^{2} \cdot 366} \rceil = 13$. Osserviamo che in questo esercizio (e in quelli che seguiranno) si suppone di utilizzare tutte le lettere possibili dell’alfabeto (dunque 26 lettere).

Una pagina ricca di esercizi sul principio dei cassetti è la seguente: http://utenti.quipo.it/base5/combinatoria/cassettiera.htm

Un’altra tecnica piuttosto frequente è quella del complementary counting, cioè si vanno a contare tutti i casi non richiesti (il complementare) per poi sottrarli al numero totale di casi. Ad esempio, se volessi conoscere tutte le parole lunghe 5 lettere con almeno una A, possiamo sottrarre il numero di parole che non contengono la A ($25^{5}$) al numero totale di parole con 5 lettere ($26^{5}$).

Tra le tecniche di conteggio più note troviamo anche il principio di inclusione – esclusione (abbreviato con PIE). Si tratta di un’identità che mette in relazione la cardinalità di un insieme (espresso come l’unione di più insiemi finiti) con le cardinalità delle intersezioni di tali insiemi. Ad esempio, nel caso di due soli insiemi, il PIE afferma che $\left| A \cup B \right| = \left| A \right|+\left| B \right| – \left| A \cap B \right|$. Questo perché se prendo tutti gli elementi di $A$ e tutti gli elementi di $B$, gli elementi comuni ad $A$ e $B$ (cioè gli elementi di $A \cap B$) verrebbero contati due volte. Nel caso di tre insiemi, si ottiene $\left| A \cup B \cup C \right| =\left| A \right| + \left| B \right| + \left| C \right| – \left| A \cap B \right| – \left| A \cap C \right| – \left| B \cap C \right| + \left| A \cap B \cap C \right|$. In generale, dati $n$ insiemi finiti $A_{1}, A_{2},…,A_{n}$, il PIE si esprime come $\left| \bigcup_{i=1}^{n} A_{i} \right| = \sum_{i=1}^n \left| A_{i} \right| – \sum_{1 \le i < j \le n} \left| A_{i} \cap A_{j} \right|+$

$ \sum_{1 \le i < j < k \le n} \left| A_{i} \cap A_{j} \cap A_{k} \right| – … (-1)^{n-1} \left| A_{1} \cap … \cap A_{n} \right|$.

Il principio di inclusione – esclusione compare in contesti diversi come, ad esempio, in geometria (nel calcolo di aree e volumi), in probabilità e in combinatoria. Nel caso di due o tre insiemi, è facilmente visualizzabile mediante i diagrammi di Eulero – Venn, come mostrato nelle figure sottostanti:

Di seguito riportiamo alcuni esercizi che fanno uso del PIE.

Nel bar davanti al Palazzo del Turismo di Cesenatico, durante la pausa delle conferenze del venerdì mattino, entrano in tutto 50 docenti. Di questi, 33 ordinano un caffè, 15 un cornetto e 8 prendono sia il caffè che il cornetto. In quanti non hanno preso nulla?

Soluzione: ci sono $33+15-8=40$ docenti che hanno preso un caffè e/o un cornetto. Quindi a non ordinare nulla sono solo $50-40=10$ docenti.

Sia $A$ l’insieme dei multipli di 6 compresi tra 110 e 350 e sia $B$ l’insieme dei multipli di 4 compresi anch’essi fra 110 e 350. Quanti sono i numeri presenti in $A \cup B$? E quanto vale la somma di tali numeri?

Soluzione: il primo e ultimo termine di $A$ sono 114 e 348 (rispettivamente il più piccolo e il più grande multiplo di 6 compresi nell’intervallo considerato). Dunque $\left| A \right| = \frac{348-(114-6)}{6}=40$. Il primo e l’ultimo termine di $B$ sono 112 e 348, da cui $\left| B \right| = \frac{348-(112-4)}{4}=60$. Infine gli elementi che appartengono sia ad $A$ che a $B$ sono gli elementi multipli del $m.c.m. (6,4)=12$, e nell’intervallo considerato il più piccolo e il più grande sono rispettivamente 120 e 348, da cui $\left| A \cap B \right| = \frac{348-(120-12)}{12}=20$. Ne consegue che $\left| A \cup B \right| = 40+60-20=80$. Per rispondere alla seconda domanda, bisogna tenere presente che la somma di tutti i numeri multipli di 6 è pari a $\frac{(114+348) \cdot 40}{2}=9240$, la somma di tutti i numeri multipli di 4 è pari a $\frac{(112+348) \cdot 60}{2}=13800$ e la somma di tutti i multipli di 12 è pari a $\frac{(120+348) \cdot 20}{2}=4680$. Ne consegue che la somma richiesta è pari a $9240+13800-4680=18360$.

N.B.: per il calcolo della somma degli elementi di $A$, di $B$ e di $A \cap B$ si è fatto uso della relazione $S = \frac{(a_1 + a_n) \cdot n}{2}$, facilmente dimostrabile nell’ambito dello studio delle progressioni aritmetiche (si veda ad esempio qui).

Quante parole di 3 lettere non contengono la stessa lettera due volte di seguito?

Soluzione: il numero totale di parole di 3 lettere è pari a $26^3$. Contiamo in quanti modi le parole hanno almeno due lettere di seguito. Potrebbe accadere che le due lettere uguali occupano la prima e seconda posizione, per un totale di $26^2$ modi (infatti la prima coppia di lettere la posso scegliere in 26 modi, la terza lettera nuovamente in 26 modi); stesso conto nel caso in cui la coppia di lettere uguali occupano la seconda e terza posizione. Invece le parole in cui tutte e 3 le lettere sono uguali sono $26$. Dunque la risposta cercata è data da $26^3 -26^2-26^2+26=16.250$.

N.B.: in questo e nei successivi esercizi si è fatto uso di quello che l’amico Paolo Toni (cfr. “Dov’è il cuore della Matematica”, pag. 18) chiama Principio fondamentale del contare (PFDC), identificandolo come il “cuore” del calcolo combinatorio: “Se una procedura (un evento) si può realizzare/verificare in $n_1$ modi diversi, una seconda in $n_2$, una terza in $n_3$, e così via, allora il numero di sequenze/catene/righe/colonne di procedure (eventi) nell’ordine indicato sarà $n_1 \cdot n_2 \cdot n_3 \cdot … $”.

Quante stringhe formate da 4 lettere e 4 cifre godono della proprietà di avere la parte letteraria palindroma o la parte numerica palindroma (o entrambe le parti palindrome)?

Soluzione: affinché le prime 4 lettere rappresentino una parola palindroma, è sufficiente fissare le prime due (in $26 \cdot 26 = 26^2$ modi), in quanto la terza e quarta lettera sono vincolate ad assumere rispettivamente il valore della seconda e della prima lettera. In totale le stringhe aventi la parte letterale palindroma sono $26^2 \cdot 10^4$. Ragionando in modo analogo, le stringhe che possiedono la parte numerica palindroma sono $26^4 \cdot 10^2$ mentre le stringhe che hanno sia la parte letterale che quella numerica palindroma sono $26^2 \cdot 10^2$. Ne consegue che la quantità cercata è pari a $26^2 \cdot 10^4 + 26^4 \cdot 10^2-26^2 \cdot 10^2=26^2 \cdot 10^2 \cdot (10^2 + 26^2 -1) = 52.390.000$.

In quanti modi posso formare due squadre avendo a disposizione 10 giocatori, sapendo che non è necessario che tutti debbano giocare ma comunque ogni squadra deve essere formata da almeno un giocatore (ad esempio, numerando i giocatori da 1 a 10, potrei mettere i giocatori 1, 3, 5, 7 e 9 nella prima squadra, i giocatori 2 e 10 nella seconda e non far giocare i giocatori numero 4, 6 e 8)?

Soluzione: ciascun giocatore può o giocare nella prima squadra, o giocare nella seconda squadra, oppure non giocare, dunque ho $3^{10}$ diversi modi di assegnarli. La prima squadra resta senza giocatori in $2^{10}$ modi e lo stesso vale per la seconda squadra, mentre c’è un solo modo per lasciare entrambe le squadre vuote (vale a dire, non facendo giocare nessuno). Ne consegue che la risposta cercata è pari a $3^{10}-2 \cdot 2^{10} +1$.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.