Sottoinsiemi isototalizzanti

[Marco]

Ciao. Il Forum sta un po' languendo. Cerchiamo di dargli una scrollata...

---------------------------------------

[Cortona 1990] Dato un insieme S formato da 10 numeri interi distinti compresi tra 1 e 99 estremi esclusi, mostrare che esistono due sottoinsiemi di S disgiunti e non vuoti tali che i rispettivi elementi abbiano uguale somma.

N.B.: questo è il testo originale, tuttavia, mi pare che "estremi esclusi" si possa cancellare e il risultato non è sharp, e allora...

Bonus question: Migliorare l'estremo superiore (al posto di 99), per cui la tesi è ancora vera.

[di questa seconda non ho pensato ad una soluzione]


Buon divertimento. M.

[HumanTorch]

Mi butto, và:
Cardinalità di $ \mathbb{\mathbb{A}}=\mathfrak{C}=10 $
Cardinalità di $ \mathfrak{P}(A) $ (insieme delle parti di A)$ =2^{10}=1024 $
Ciò vuol dire $ 1024 $ possibili somme: la somma massima ottenibile è
$ 90+91+92+..+99<1023 $, quindi le somme di due sottoinsiemi devono essere uguali (pigeonhole): mi spiego meglio: la somma massima ottenibile pari al numero di somme ottenibili: se posso avere al massimo $ 6 $, potrò avere le somme corrispondenti agli interi compresi fra $ 1 $ e $ 6 $. Quindi se posso ottenere solo $ 945 $ somme, ma la cardinalità dell'insieme è $ 1024 $, $ 1023 $ visto che non possiamo avere insieme vuoto, almeno
due sottoinsiemi hanno la stessa somma.

Per il secondo problema, punterei molto sui binomiali, e non mi stupirei se il limite superiore fosse una potenza di $ 2 $, dato che ogni naturale $ <2^j $si può esprimere come somma di potenze di $ 2 $ con esponente naturale $ <j $ e che è proprio $ j $ il minor numero di elementi necessario a ottenere ..vabbè, ci penso dopo.

[Marco]

Oddio, il messaggio è chiaro solo fino a "mi [s]piego meglio". Poi la spiegazione è molto più incasinata del messaggio originale.

In ogni caso, l'idea del principio dei cassetti è senz'altro quella giusta, ma ti resta da aggiustare il dettaglio che i due sottoinsiemi così trovati non è detto siano disgiunti, come richiesto...

[HumanTorch]

Ah, ggià, come dire, "mai fasciarsi la testa prima di essersela rotta", comunque: se i due sottoinsiemi in questione hanno degli elementi in comune (diciamo $ c_1, c_2,.., c_i $) chiamiamo $ C=\displaystyle\sum^i_{k=1} c_k $ e siano $ \mathbb{M}_1 $ e $ \mathbb{M}_2 $ tali insiemi e $ S_1 $ e $ S_2 $ le somme dei rispettivi elementi. Sarà $ S_1=S_2 $, quindi $ S_1-C=S_2-C $. Essendo i due insiemi non vuoti, ogni membro dell'equazione precedente sarà $ >0 $ e, avendo eliminato gli elementi $ c_k\in\{\mathbb{M}_1\cap\mathbb{M}_2\} $, avremo i due insiemi disgiunti non vuoti proprio come li volevamo noi