Pagina 1 di 1
Piccoli sottoinsiemi
Inviato: 08 set 2007, 08:12
da Russell
Sia $ S\subseteq \left\{1,2,3,.....9\right\} $ tale che sommando due coppie diverse di elementi di $ S $ si ottengono sempre risultati diversi. Per esempio $ \left\{1,2,3,4\right\} $ non ha le caratteristiche richieste (4+1=2+3), mentre $ \left\{1,2,3,5\right\} $ sì.
Qual è il massimo numero di elementi che $ S $ può avere?
Inviato: 08 set 2007, 08:26
da pic88
Olimpiadi nazionali della Lituania, mi pare...
{1,2,3,5,8} funziona.
Se un insieme avesse 6 elementi allora ci sarebbero 15 somme diverse, e le possibili somme di elementi distinti tra 1 e 9 sono in totale proprio 15. Quindi il pigeonhole non basta... Però, se esistono una coppia con somma 3 e una con somma 17, non può che trattarsi di (1,2) e (8,9) e 1+8=2+9. Quindi il massimo è 5.
Rilancio: generalizzare ad insiemi $ S \subseteq A = \{1, 2, \ldots, n\} $