Sottoinsiemi di sottoinsiemi

[axpgn]

Sia $C$ l'insieme composto dai numeri naturali da uno a cento compresi.
Sia $A$ un qualsiasi sottoinsieme di $C$ composto esattamente da dieci elementi.

Dimostrare che è sempre possibile determinare due sottoinsiemi di $A$, non vuoti e disgiunti, tali che la somma degli elementi di un sottoinsieme sia pari alla somma degli elementi dell'altro.

Cordialmente, Alex

[orsoulx]

Basta il principio dei cassetti. L'insieme delle parti di $ A $ contiene $ 2^10=1024 $ elementi ($ 1022 $ escludendo l'insieme vuoto e $A$); mentre le somme ottenibili addizionando al più dieci addendi non maggiori di $ 100 $ sono tutte minori di $ 1000 $ (la somma massima è $ 5*191=955 $ se si vuol essere precisi). Esistono allora almeno due sottoinsiemi $ X,Y \subset A $ con uguale somma dei numeri contenuti. Eliminando gli eventuali elementi in comune si ottiene quanto cercato.

Ciao

[axpgn]

Perfetto!