Admin ha scritto:Dalla sezione "Il principio dei cassetti"
32. Cinquecento cassette di mele
Ci sono 500 cassette di mele. Ciascuna cassetta contiene più di x mele.
Si trovi il minimo valore di x tale che si possa essere sicuri che esistano 3 cassette con lo stesso numero di mele.
C'è un evidente errore nella traccia.
Deve essere "... Ciascuna cassetta contiene meno di x mele. ...",
ed inoltre "...Si trovi il massimo valore di x tale che...".
Infatti se ciascuna cassetta contiene più di x mele, vuol dire che può contenerne un numero qualsiasi, anche infinito e quindi il problema non è risolvibile.
Quindi consideriamo la traccia corretta:
Mettiamoci nel caso peggiore;Ci sono 500 cassette di mele. Ciascuna cassetta contiene meno di x mele.
Si trovi il massimo valore di x tale che si possa essere sicuri che esistano 3 cassette con lo stesso numero di mele.
esso si ha, utilizzando il numero minimo di mele in modo che ogni cassetta contenga un numero diverso di mele;
quindi mettiamo:
nella 1° cassetta 0 mele
nella 2° cassetta 1 mela
nella 3° cassetta 2 mele
...
...
nella 499° cassetta 498 mele
nella 500° cassetta 499 mele
Quindi, in questo caso, ciascuna cassetta contiene meno di 500 mele e non possiamo essere sicuri che vi siano almeno 3 cassette con lo stesso numero di mele;
ora, se supponiamo che ciascuna cassetta contenga meno di 499 mele; potremo avere, nel caso peggiore:
nella 1° cassetta 0 mele
nella 2° cassetta 1 mela
nella 3° cassetta 2 mele
...
...
nella 499° cassetta 498 mele
ma nella 500° avremo un numero di mele compreso tra 0 a 498, e quindi sicuramente uguale a quello di un'altra delle 500 cassette.
Per cui con x=499 abbiamo sicuramente 2 cassette con lo stesso numero di mele.
Quindi con x=498 abbiamo sicuramente 3 cassette con lo stesso numero di mele.
Admin