Il principio dei cassetti - 7. Somme uguali

[Admin]

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