La ricerca ha trovato 3 risultati

da bummer
16 ott 2012, 20:35
Forum: Combinatoria
Argomento: $x_1y_1+\ldots+x_ny_n\equiv 0 \pmod 2$
Risposte: 12
Visite : 2688

Re: $x_1y_1+\ldots+x_ny_n\equiv 0 \pmod 2$

Un quinto metodo: associa un valore ad ogni $x_i$ a patto che non siano tutti 0 ($2^n -1$ modi) poi scegli un valore per ogni $y_i$ meno quella corrispondente al primo 1 degli $x_i$ ($2^{n-1}$ modi) e fissa l'$y_j$ rimanente in modo da sistemare la parità (è facile vedere che così non si perde nessu...
da bummer
24 set 2012, 17:43
Forum: Combinatoria
Argomento: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$
Risposte: 10
Visite : 1633

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

jordan ha scritto:
bummer ha scritto:per Dilworth
Scusa l'ignoranza, ma cos'è?
http://en.wikipedia.org/wiki/Dilworth's_theorem

È parte del bagaglio olimpico per quanto mi risulta.
da bummer
24 set 2012, 12:36
Forum: Combinatoria
Argomento: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$
Risposte: 10
Visite : 1633

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Testo nascosto:
sia t il minimo numero di catene (secondo l'ordine dato dalla divisione) che partiziona l'insieme, per Dilworth se $ t\geq m+1 $ abbiamo finito, altrimenti deve esistere una catena con almeno $ \lceil \frac{mn+1}{t} \rceil \geq \lceil \frac{nm+1}{m}\rceil = n+1 $ elementi.