Il principio dei cassetti - 7. Somme uguali

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: 857
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Il principio dei cassetti - 7. Somme uguali

Messaggio da Admin »

Admin ha scritto:
sab dic 03, 2005 5:09 pm
Dalla sezione "Il principio dei cassetti"

7. Somme uguali

Sia dato un insieme A di 10 numeri interi compresi fra 1 e 100.
All'interno di A si possono trovare due sottoinsiemi non vuoti S, T tali che la somma degli elementi di S è uguale alla somma degli elementi di T.
L'unione di S e T non deve necessariamente essere uguale ad A.
Determiniamo oggetti e cassetti.
In questo problema è immediato notare che gli oggetti sono i sottinsiemi non vuoti, mentre i cassetti sono le possibili somme degli elementi di un sottinsieme.
Sappiamo dal calcolo combinatorio, che il numero dei sottinsiemi distinti, di un insieme di $10$ numeri, è pari a $2^{10}$.
Il problema non tiene conto dei sottinsiemi vuoti, per cui il numero dei sottinsiemi distinti cui far riferimento è $2^{10}-1 = 1023$.
Essi saranno, dunque, i nostri $1023$ oggetti.
Per quanto riguarda le possibili somme, esse vanno dalla somma minima di un sottinsieme, che è ovviamente $1$, alla somma massima possibile che ci è data da:
$100+99+98+\cdots+93+92+91 = 955$
Per cui le possibili somme sono:
$1, 2, 3, \cdots, 955$
Esse saranno i nostri $955$ cassetti.

Dunque, per il principio generale dei cassetti, avendo $1023$ oggetti e $955$ cassetti, vi sarà almeno un cassetto che contiene $\large\left\lceil\frac{1023}{955}\right\rceil\normalsize = 2$ oggetti.
Ossia vi saranno almeno $2$ sottinsiemi che avranno la stessa somma dei loro elementi.

Ora questi due sottinsiemi possono essere sia disgiunti che non disgiunti.
Tuttavia, se i due sottinsiemi sono non disgiunti, è possibile eliminare da essi gli elementi in comune, ottenendo così due nuovi sottinsiemi disgiunti che manterranno comunque sempre la stessa somma dei loro elementi.

Quindi, ricapitolando, in un insieme di $10$ naturali tra $1$ e $100$, si possono sempre trovare due sottinsiemi non vuoti (sia disgiunti che non disgiunti), tali che la somma dei relativi elementi sia la stessa.

SE&O
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Rispondi