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

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

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

Messaggio da Ido Bovski » 15 ott 2012, 09:12

Determinare il numero delle $2n$-uple $(x_1,\ldots, x_n, y_1, \ldots, y_n)$ tali che:
  • tutti gli $x_i$ e gli $y_i$ sono $0$ oppure $1$
  • la somma $x_1y_1+\ldots+x_ny_n$ è un numero pari.
p.s. è abbastanza facile, ma carino :)

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

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

Messaggio da razorbeard » 15 ott 2012, 18:50

A me è uscita una cosa un po' strana...
$\displaystyle \sum_{k=0}^{\frac {n}{2}} {\binom {n}{2k}}{\cdot 3^{n-2k}}$, con $\displaystyle\frac{n}{2}$sopra la sommatoria intendo soltanto che $n-2k$ deve essere maggiore di 0.
E' un buon giorno... per morire

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

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

Messaggio da fph » 15 ott 2012, 18:56

Hmm... non si riesce a scrivere in forma chiusa quella sommatoria?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

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

Messaggio da Ido Bovski » 15 ott 2012, 19:59

razorbeard ha scritto:A me è uscita una cosa un po' strana...
$\displaystyle \sum_{k=0}^{\frac {n}{2}} {\binom {n}{2k}}{\cdot 3^{n-2k}}$, con $\displaystyle\frac{n}{2}$sopra la sommatoria intendo soltanto che $n-2k$ deve essere maggiore di 0.
No, il risultato non è quello giusto. Comunque la somma che hai scritto è uguale a $2^{2n-1}+2^{n-1}$, perché?

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

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

Messaggio da razorbeard » 15 ott 2012, 20:18

Forse l'errore sta nel caso di $k=0$,perchè non si ha $3^n$ come dice la sommatoria ma si deve avere 1???
In ogni caso non saprei trasformare la sommatoria di prima in $2^{2n-1}+2^{n-1}$ :cry:
E' un buon giorno... per morire

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

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

Messaggio da ma_go » 15 ott 2012, 21:39

se magari ci dicessi come sei arrivato alla conclusione, potremmo provare a capire dove hai sbagliato, razorbeard.
come mettere quella somma in forma chiusa è un altro paio di maniche: facciamo una roba alla volta.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

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

Messaggio da jordan » 16 ott 2012, 01:29

Ido Bovski ha scritto:Comunque la somma che hai scritto è uguale a $2^{2n-1}+2^{n-1}$, perché?
Che e' anche il risultato del problema, sbaglio?
The only goal of science is the honor of the human spirit.

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

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

Messaggio da razorbeard » 16 ott 2012, 15:53

Scrivi qui il mio ragionamento:
Il numero di coppie $x_iy_i$ uguali ad 1 deve per forza essere pari,quindi si suddivide il problema in due casi:
-caso1: se non ci sono coppie uguali ad 1 allora tutte le coppie sono uguali a 0. Lo zero si può ottenere in 3 modi diversi $0\cdot 0,0\cdot 1,1\cdot 0$,quindi il numero di n-uple senza fattori uguali ad 1 è $3^n$.
-caso2:se ci sono un numero pari di fattori uguali ad 1 allora si sceglie nei vari modi le coppie uguali ad 1 che,ricordo,sono sempre pari, con $\displaystyle\binom{n}{2k}$, le restanti $n-2k$ coppie sono uguali a 0,lo zero,come detto prima,è ottenibile in 3 modi,quindi si moltiplica per $3^{n-2k}$.
Da qui esce fuori la sommatoria di due messaggi fa.
Però oggi durante l'ora di matematica a scuola ho seguito un altro metodo :D :chiamo $p_n$ le n-uple con somma pari e $d_n$ le n-uple con somma dispari.
Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.
E' un buon giorno... per morire

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

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

Messaggio da jordan » 16 ott 2012, 16:25

razorbeard ha scritto:Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.
Entrambe le soluzioni sono corrette. Ora, deduci in entrambi i modi che $p_n=\displaystyle \sum_{0\le 2i\le n}{3^{2i}\binom{n}{2i}}=2^{n-1}+2^{2n-1}$..
The only goal of science is the honor of the human spirit.

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

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

Messaggio da Ido Bovski » 16 ott 2012, 16:26

razorbeard ha scritto:Scrivi qui il mio ragionamento:
Il numero di coppie $x_iy_i$ uguali ad 1 deve per forza essere pari,quindi si suddivide il problema in due casi:
-caso1: se non ci sono coppie uguali ad 1 allora tutte le coppie sono uguali a 0. Lo zero si può ottenere in 3 modi diversi $0\cdot 0,0\cdot 1,1\cdot 0$,quindi il numero di n-uple senza fattori uguali ad 1 è $3^n$.
-caso2:se ci sono un numero pari di fattori uguali ad 1 allora si sceglie nei vari modi le coppie uguali ad 1 che,ricordo,sono sempre pari, con $\displaystyle\binom{n}{2k}$, le restanti $n-2k$ coppie sono uguali a 0,lo zero,come detto prima,è ottenibile in 3 modi,quindi si moltiplica per $3^{n-2k}$.
Da qui esce fuori la sommatoria di due messaggi fa.
Però oggi durante l'ora di matematica a scuola ho seguito un altro metodo :D :chiamo $p_n$ le n-uple con somma pari e $d_n$ le n-uple con somma dispari.
Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.
Ehm, in effetti avevo sbagliato un conto stupido e mi veniva $2^{2n-1}+2^n$ :mrgreen: . La mia soluzione praticamente frutta la tua seconda idea: hai che $p_{n+1}=3p_n+d_n=2p_n+(p_n+d_n)=2p_n+2^{2n}$, da cui puoi ricavare facilmente il termine generale $p_n$ sapendo che $p_1=3$.

Ti metto nascosto come scrivere in "forma chiusa" la sommatoria del tuo primo post.
Testo nascosto:
$\displaystyle \sum_{\substack{i=0 \\ i\equiv 0 \pmod 2}}^n \binom{n}{i}\cdot 3^{n-i}=\frac{1}{2}\left\{ \sum_{i=0}^n \binom{n}{i}\cdot 3^{n-i}+\sum_{i=0}^n \binom{n}{i}\cdot 3^{n-i}\cdot(-1)^i \right\}=\frac{1}{2}\{(3+1)^n+(3-1)^n \}=2^{2n-1}+2^{n-1}$

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

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

Messaggio da jordan » 16 ott 2012, 18:16

Un terzo metodo:
\[ \begin{cases} p_1=3 \\ d_1=1 \\ p_{n+1}=3p_n+d_n \\ d_{n+1}=p_n+3d_{n+1}\end{cases} \]
ricavare che $p_{n+1}=3p_n+d_n=3p_n+p_{n-1}+3d_{n-1}=3p_n+p_{n-1}+3(p_n-3p_{n-1})=6p_n-8p_{n-1}$, l'equazione caratteristica $x^2-6x+8=(x-2)(x-4)$ da cui $p_n=\alpha 2^n+ \beta 4^n$ per qualche $\alpha, \beta$ (imponendo la condizione iniziale troviamo $\alpha=\beta=\frac{1}{2}$)
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

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

Messaggio da jordan » 16 ott 2012, 18:33

Un quarto metodo (simile al terzo, ma piu' bovino):
Dati $p_1=3, d_1=1$, allora , detto $\zeta:=\frac{\sqrt{2}}{2}$, vale:
\[ \left[ \begin{array}{*{20}c} {p_{n+1}} \\ {d_{n+1}}\end{array} \right] =\left[ { {\begin{array}{*{20}c} {3} & {1} \\ {1} & { 3} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{n}} \\ {d_{n}}\end{array} \right]= \left[ { {\begin{array}{*{20}c} {3} & {1} \\ {1} & { 3} \\ \end{array}} } \right]^n \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right]=\left[ { {\begin{array}{*{20}c} {\zeta} & {-\zeta} \\ {\zeta} & { \zeta} \\ \end{array}} } \right]\left[ { {\begin{array}{*{20}c} {2} & {0} \\ {0} & {4} \\ \end{array}} } \right]^n \left[ { {\begin{array}{*{20}c} {\zeta} & {\zeta} \\ {-\zeta} & { \zeta} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right]= \left[ { {\begin{array}{*{20}c} {\zeta} & {-\zeta} \\ {\zeta} & { \zeta} \\ \end{array}} } \right]\left[ { {\begin{array}{*{20}c} {2^n} & {0} \\ {0} & {4^n} \\ \end{array}} } \right] \left[ { {\begin{array}{*{20}c} {\zeta} & {\zeta} \\ {-\zeta} & { \zeta} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right] \]
The only goal of science is the honor of the human spirit.

bummer
Messaggi: 3
Iscritto il: 18 set 2012, 00:05

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

Messaggio da bummer » 16 ott 2012, 20:35

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 nessuna configurazione). Nel caso in cui tutti gli $x_i$ sono uguali a 0 si può scegliere arbitrariamente ogni $y_i$ ($2^n$ modi). Quindi, ricapitolando: $(2^n-1)2^{n-1} + 2^{n} = 2^{2n-1}+2^{n-1}$.

Rispondi