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?
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}.