1) Dimostrare che preso un insieme A di 14 numeri distinti di tre cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
2) Dimostrare che preso un insieme A di 12 numeri distinti di due cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, con un numero di elementi non superiore a 3, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
somme
Ah, è da un bel pò che non scrivo sul forum, guarda come cambiano i tempi (tocca impararsi sto Latex)
1) Dimostrare che preso un insieme A di 14 numeri distinti di tre cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
DIMOSTRAZIONE:tutti i possibili sottoinsiemi di A sono 2^14=16384, e i valori che la somma degli elementi di ciascun insieme può variare tra 100*14 a 1000*14 (ho un pò esagerato ma per snellire i calcoli), ovvero tra 900*14=12600 valori.
Ora usiamo il pigeonhole: abbiamo 16384 piccioni, e 12600 buchi(scatole), quindi ci sono sicuramente almeno 2 piccioni in almeno 1 buco.morale:almeno 2 sottoinsiemi hanno la somma dei propri elementi uguale.
2) Dimostrare che preso un insieme A di 12 numeri distinti di due cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, con un numero di elementi non superiore a 3, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
DIMOSTRAZIONE: molto simile a prima: i sottoinsiemi sono 12 + 12C1 + 12C2 = 298 (scusate lo schifo per scrivere i binomiali), mentre i valori possibili sono tra 10 e 3*100, 290. Uguale a prima, 298 piccioni in 290 buchi ===> due sottoinsiemi con la stessa somma degli elementi.
Per il "disgiunti" me la cavo così:
LEMMA: se esiste una coppia di sottoinsiemi con intersezione C, |C|>0, che hanno la stessa somma degli elementi, esistono anche due sottoinsiemi disgiunti con la stessa proprietà.
Dimostrazione:chiamo A e B i due sottoinsiemi, e si vede facilmente che A-C e B-C soddisfano la tesi, perchè la loro intersezione è 0 per ipotesi.
Adesso mi direte(oltre agli eventuali errori): c'è una parte del forum che spiega come usare latex,ecc.....lo so lo so, ma sono uno che si adatta difficilmente ai cambiamenti.
Ciao a tutti
Francesco
1) Dimostrare che preso un insieme A di 14 numeri distinti di tre cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
DIMOSTRAZIONE:tutti i possibili sottoinsiemi di A sono 2^14=16384, e i valori che la somma degli elementi di ciascun insieme può variare tra 100*14 a 1000*14 (ho un pò esagerato ma per snellire i calcoli), ovvero tra 900*14=12600 valori.
Ora usiamo il pigeonhole: abbiamo 16384 piccioni, e 12600 buchi(scatole), quindi ci sono sicuramente almeno 2 piccioni in almeno 1 buco.morale:almeno 2 sottoinsiemi hanno la somma dei propri elementi uguale.
2) Dimostrare che preso un insieme A di 12 numeri distinti di due cifre, possiamo trovare due sottoinsiemi (B e C) di A disgiunti, non vuoti, con un numero di elementi non superiore a 3, tali che la somma degli elementi di B sia uguale alla somma degli elementi di C
DIMOSTRAZIONE: molto simile a prima: i sottoinsiemi sono 12 + 12C1 + 12C2 = 298 (scusate lo schifo per scrivere i binomiali), mentre i valori possibili sono tra 10 e 3*100, 290. Uguale a prima, 298 piccioni in 290 buchi ===> due sottoinsiemi con la stessa somma degli elementi.
Per il "disgiunti" me la cavo così:
LEMMA: se esiste una coppia di sottoinsiemi con intersezione C, |C|>0, che hanno la stessa somma degli elementi, esistono anche due sottoinsiemi disgiunti con la stessa proprietà.
Dimostrazione:chiamo A e B i due sottoinsiemi, e si vede facilmente che A-C e B-C soddisfano la tesi, perchè la loro intersezione è 0 per ipotesi.
Adesso mi direte(oltre agli eventuali errori): c'è una parte del forum che spiega come usare latex,ecc.....lo so lo so, ma sono uno che si adatta difficilmente ai cambiamenti.
Ciao a tutti
Francesco
questa mi è venuta in mente pensando ad un es su un altro forum... Dato che l'argomento è simile agli esempi sopra, la posto anche quà... Non ho ancora trovato una sol che confermi o smentisca: se i mods pensano sia necessario, spostino pure il tutto nella parte dovuta (ho postato quà l'es perchè c'era il topic proprio fatto a puntino)...
CONGETTURA: scelto un insieme A di k elementi minori o uguali a [2^(k-1)-1], si possono sempre trovare due sottoinsiemi A1 ed A2 di A tali che la somma degli elementi di A1 sia uguale a quella degli elementi di A2...
praticamente è uguale agli es sopra ma con dei limiti molto più forti...
ps: qualcuno scrive la formula (mi pare sia famosa) che indica in quanti modi si può ottenere un numero come somma di interi diversi tra loro?
CONGETTURA: scelto un insieme A di k elementi minori o uguali a [2^(k-1)-1], si possono sempre trovare due sottoinsiemi A1 ed A2 di A tali che la somma degli elementi di A1 sia uguale a quella degli elementi di A2...
praticamente è uguale agli es sopra ma con dei limiti molto più forti...
ps: qualcuno scrive la formula (mi pare sia famosa) che indica in quanti modi si può ottenere un numero come somma di interi diversi tra loro?
-
MindFlyer
Immagino che tu voglia anche A1 e A2 distinti e non vuoti. In caso contrario la congettura è banalmente vera.info ha scritto:CONGETTURA: scelto un insieme A di k elementi minori o uguali a [2^(k-1)-1], si possono sempre trovare due sottoinsiemi A1 ed A2 di A tali che la somma degli elementi di A1 sia uguale a quella degli elementi di A2...
Altrimenti è falsa: prendi k=5 e A={6,10,12,14,15}.