$2n \text{-uple}$

[Rho33]

Determinare il numero delle $2n \text{-uple}$ $(x_1,...,x_n,y_1,...,y_n)$ tali che:

(i)tutti gli $x_i,y_i$ siano $0 $ oppure $1$

(ii)$\displaystyle \sum_{i=1}^n x_iy_i$ sia pari


P.S.Io non mi trovo con il risultato ufficiale (è un Cortona del 2000) quindi cerco qualche soluzione diversa per esserne sicuro, in caso tra un poco posto la mia "finta" soluzione.

[Gerald Lambeau]

Testo nascosto:

Siano $P_n$ e $D_n$ il numero di $2n$-uple con somme rispettivamente pari e dispari. Chiaramente $P_1=3, D_1=1$.
Abbiamo anche che
$P_{n+1}=3P_n+D_n$;
$D_{n+1}=3D_n+P_n$.
Consideriamo la successione $A_n=P_n-D_n$. Abbiamo che $A_{n+1}=P_{n+1}-D_{n+1}=2(P_n-D_n)=2A_n$. Da ciò si ricava facilmente per induzione che $A_n=2^n$, inoltre $B_n=P_n+D_n=4^n$ (è il numero di tutte le possibili $2n$-uple).
Da cui si ha $P_n=(A_n+B_n)/2=2^{n-1}(2^n+1)$.
Analogamente possiamo trovare $D_n=(B_n-A_n)/2=2^{n-1}(2^n-1)$. Curiosamente vale $D_6=2016$.

[Rho33]

Eh, caro Gerald, concordo sul risultato! Il punto è che nella soluzione ufficiale il numero è $2^n(2^{n-1}+1)$ che chiaramente non va bene, basta fare i primi casi d'esempio