Problema di cardinalità
Fisso $X\subset {1,...,n}$ non vuoto.
E' vero che gli $A\subset {1,...,n}$ per cui $A\nn X$ ha cardinalità pari sono lo stesso numero dei $B\subset {1,...,n}$ per cui $B\nn X$ ha cardinalità dispari?
In tal caso come posso dimostrarlo?
Se $X$ ha cardinalità dispari è vero: ad ogni $A$ con $#(A\nn X)$ pari posso far corrispondere (in modo biunivoco) $A^c$ (il complementare di A), che soddisfa $#(A^c\nn X)$ dispari.
Infatti $(A\nn X) \uu (A^c\nn X)=X$ quindi, visto che l'unione è disgiunta, $#(A\nn X) + #(A^c\nn X)=#X$, da qui, essendo $#X$ dispari e $#(A\nn X)$ pari, ne viene $#(A^c\nn X)$ dispari.
Se invece $X$ ha cardinalità pari non riesco a rifare un discorso del genere. A qualcuno viene in mente?
Avete altre idee?
E' vero che gli $A\subset {1,...,n}$ per cui $A\nn X$ ha cardinalità pari sono lo stesso numero dei $B\subset {1,...,n}$ per cui $B\nn X$ ha cardinalità dispari?
In tal caso come posso dimostrarlo?
Se $X$ ha cardinalità dispari è vero: ad ogni $A$ con $#(A\nn X)$ pari posso far corrispondere (in modo biunivoco) $A^c$ (il complementare di A), che soddisfa $#(A^c\nn X)$ dispari.
Infatti $(A\nn X) \uu (A^c\nn X)=X$ quindi, visto che l'unione è disgiunta, $#(A\nn X) + #(A^c\nn X)=#X$, da qui, essendo $#X$ dispari e $#(A\nn X)$ pari, ne viene $#(A^c\nn X)$ dispari.
Se invece $X$ ha cardinalità pari non riesco a rifare un discorso del genere. A qualcuno viene in mente?
Avete altre idee?
Risposte
ho visto una soluzione che passa per un'altra strada:
quanti sono i sottoinsiemi di $X$, con $#X=n$ ? non so se lo sai ma sono $2^n$.
quindi devi mostrare che la metà hanno un numero dispari di elementi, l'altra metà un numero pari.
ma poi osserviamo che, sempre dato $X$ di cardinalità $n$, in che modo dobbiamo scegliere i suoi sottoinsiemi?
ad esempio quali avranno un numero dispari di elementi? ovviamente quelli che hanno 1,3,5... elementi.
e analogo per i pari, dobbiamo scegliere i sottoinsiemi che hanno 0,2,4,6... elementi.
e quanti sono tali elementi? banalmente per i dispari saranno $ ( (n),(1) ) $ per i sottoinsiemi di cardinalità 1; $ ((n),(3))$ per quelli di cardinalità eccetera..
analogamente per i pari i sottoinsiemi con 0 element sonoi $ ( ( n ),( 0 ) ) $ (ovvio che è uno solo, ma per fare capire il meccanismo)
$ ( ( n ),( 2 ) ) $ sono i sottoinsiemi con 2 elementi...
a questo punto la buona osservazione è che i coefficienti binomali $ ( ( n ),( 0 ) ) $ , $ ( (n),(1) ) $ , $ ( ( n ),( 2 ) ) $ ecc.
sono gli elementi dell' $n$esima riga del triangolo di Tartaglia. allora tutto si riduce a far vedere che nel triangolo di Tartaglia, in una qualunque riga la somma degli elementi di posto pari è uguale alla somma di quelli di posto dispari.
quanti sono i sottoinsiemi di $X$, con $#X=n$ ? non so se lo sai ma sono $2^n$.
quindi devi mostrare che la metà hanno un numero dispari di elementi, l'altra metà un numero pari.
ma poi osserviamo che, sempre dato $X$ di cardinalità $n$, in che modo dobbiamo scegliere i suoi sottoinsiemi?
ad esempio quali avranno un numero dispari di elementi? ovviamente quelli che hanno 1,3,5... elementi.
e analogo per i pari, dobbiamo scegliere i sottoinsiemi che hanno 0,2,4,6... elementi.
e quanti sono tali elementi? banalmente per i dispari saranno $ ( (n),(1) ) $ per i sottoinsiemi di cardinalità 1; $ ((n),(3))$ per quelli di cardinalità eccetera..
analogamente per i pari i sottoinsiemi con 0 element sonoi $ ( ( n ),( 0 ) ) $ (ovvio che è uno solo, ma per fare capire il meccanismo)
$ ( ( n ),( 2 ) ) $ sono i sottoinsiemi con 2 elementi...
a questo punto la buona osservazione è che i coefficienti binomali $ ( ( n ),( 0 ) ) $ , $ ( (n),(1) ) $ , $ ( ( n ),( 2 ) ) $ ecc.
sono gli elementi dell' $n$esima riga del triangolo di Tartaglia. allora tutto si riduce a far vedere che nel triangolo di Tartaglia, in una qualunque riga la somma degli elementi di posto pari è uguale alla somma di quelli di posto dispari.
Intanto grazie. Ho provato a dimostrare che la somma degli elementi di posto pari e uguale a quella degli elementi de posto dispari su una riga del triangolo di tartaglia, ma non mi sembra così facile. Come posso fare?
è molto facile, pensa a come scrivi una riga in funzione di quella precedente.
Ok, sono riuscito, grazie mille!
Così ho dimostrato che i sottinsiemi di $X$ di cardinalità pari sono tanti quanti quelli di cardinalità dispari.
Io però ho bisogno di qualcosa di leggermente diverso: fissato $X\subset{1,...,n}$ non vuoto, voglio dire che gli $A\subset{1,...,n}$ con cardinalità di $A\nn X$ pari sono tanti quanti quelli con cardinalità di $A\nn X$ dispari.
Come faccio ad ottenere questo dal risultato precedente?
Così ho dimostrato che i sottinsiemi di $X$ di cardinalità pari sono tanti quanti quelli di cardinalità dispari.
Io però ho bisogno di qualcosa di leggermente diverso: fissato $X\subset{1,...,n}$ non vuoto, voglio dire che gli $A\subset{1,...,n}$ con cardinalità di $A\nn X$ pari sono tanti quanti quelli con cardinalità di $A\nn X$ dispari.
Come faccio ad ottenere questo dal risultato precedente?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo