Il principio dei cassetti - 26. Un milione di alberi

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Il principio dei cassetti - 26. Un milione di alberi

Messaggio da Admin »

Admin ha scritto:
sab dic 03, 2005 5:09 pm
Dalla 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.
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.
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
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Rispondi