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?
Piccoli sottoinsiemi
Piccoli sottoinsiemi
"Il fatto che un'opinione sia ampiamente condivisa, non è affatto una prova che non sia completamente assurda" B. Russell
-
pic88
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
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\} $
{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\} $