Il principio generale dei cassetti ci dice che se abbiamo $n$ oggetti da inserire in $m$ contenitori, con $n > m$ vi sarà almeno un cassetto contenente almeno $\large\left\lceil\frac{n}{m}\right\rceil$ oggetti.Admin ha scritto: ↑sab dic 03, 2005 5:09 pmDalla sezione "Il principio dei cassetti"
26. Un milione di alberi
In una foresta ci sono un milione di alberi.
Ciascun albero ha non più di 600000 foglie.
Si dimostri che in ogni istante ci sono due alberi nella foresta che hanno lo stesso numero di foglie.
Nel nostro caso gli oggetti sono gli alberi, quindi $n = 1000000$.
I cassetti invece sono tutte le possibili differenti tipologie di alberi (alberi con $0$ foglie, con $1$ foglia, ..., con $600000$ foglie), quindi $m = 600001$.
Pertanto il principio dei cassetti ci dice che vi sarà almeno un cassetto contentente almeno $\large\left\lceil\frac{1000000}{600001}\right\rceil = 2$ oggetti.
Ossia vi saranno almeno $2$ alberi, con la stessa configurazione, e quindi con lo stesso numero di foglie.
Admin