Somma alterna multipla di 6

[Triarii]

Premetto che è un problema che mi ha proposto un mio amico, quindi non ho una soluzione ufficiale (anche se credo di aver trovato un risultato ragionevole)
Sia $A$ l'insieme di $10$-uple $(a_0,a_1,...,a_9)$ composte da 10 elementi appartenenti a $\left \{0,1,2,3,4\right \}$ e tali che
$$\sum_{i=0} ^9 (-1)^ia_i\equiv 0 \pmod 6$$
Trovare la cardinalità di $A$
(A scanso di equivoci, i vari $a_i$ possono essere anche uguali)

[Gottinger95]

Chiamo \(A_n\) la cardinalità di bla bla bla ma con \(n\)-uple invece di 10-uple.
Poniamo che \(\sum_{i=0}^{n-2} = m\). In quanti modi posso scegliere \(a_{n-1}, a_n\) in modo che la somma fino a \(n\) sia multipla di 6? Ammano, notiamo che se \(m=0\) ci sono 5 modi, altrimenti ce ne sono 4. Quindi possiamo scrivere la ricorrenza
\( A_{n} = 5 A_{n-2} + 4 (5^{n-2}-A_{n-2} ) = A_{n-2} + 4 \cdot 5^{n-2}\) (*)
\(A_{n-2} = A_{n-4} + 4 \cdot 5^{n-4} \)
Da cui
\(A_n - 25 A_{n-2} = A_{n-2} - 25 A_{n-4} \)
Ponendo \(B_n = A_{2n} \) e rimaneggiando abbiamo
\(B_{n}-26B_{n-1} + 25 B_{n-2} = 0\)
Il polinomio caratteristico è \(x^2-26x+25=0\), le cui soluzioni sono \( 1,25\). Perciò in generale \(B_n = a25^n + b\) per qualche \(a,b\).
Imponendo \( 5 = B_1 = 25a +b\) e \(105 = B_2 = 625a+b\) ( \(B_2\) lo troviamo dalla (*)), otteniamo \(a= 1/6\) e \(b=5/6\).
Dalla formula definitiva
\(\displaystyle A_{2n} = B_n = \frac{25^n+5}{6}\)
otteniamo \(\displaystyle A_{10} = \frac{25^5+5}{6} = 1\ 627\ 605\).

[Triarii]

Ok! Posto pure la mia:
Chiamo con $S_m(n)$ il numero di casi in cui la somma a segni alterni dei primi $n$ termini sia congrua a $m$ modulo $6$.
Facciamo finta che $a_9$ possa essere anche $6$. Notiamo che scelti i primi 9 numeri (selezionabili in $5^9$ modi nelle nostre ipotesi, affinchè la somma sia $\equiv 0 \pmod 6$, esiste una unica scelta. Il problema è che non abbiamo a disposizone il 5. Quindi non ci vanno bene tutte le sequenze tali che la somma a segni alterni dei primi 9 termini sia proprio congrua a 5. In notazione abbiamo che $S_6(10)=5^9-S_5(9)$
Ripetendo il giochino abbiamo che $S_5(9)=5^8-S_6(8)$, e così via, fino ad arrivare a $S_5(1)=0$
Abbiamo quindi che $S_6(10)$ è la somma di una progressione geometrica di ragione $-5$. Svolgendo abbiamo $S_6(10)=5\cdot \dfrac {-5^9-1} {-6}=1627605$
Metodo alternativo:

Testo nascosto:

la tesi equivale a dire che il numero in base 5 con cifre $a_9,..a_0$ sia multiplo di 6 (congruenza modulo 11 styie). Quindi ci basta trovare i multipli di 6 fino a $(4444444444)_5$, che sono $\dfrac {5^{10}-1} {6} +1$ (aggiungo 1 per considerare lo 0, che altrimenti non verrebbe considerato)

[darkcrystal]

Soluzione intesa come hint per viewtopic.php?f=16&t=18591. La scrivo in maniera un po' sintetica, se qualcosa non vi torna fate un fischio (e poi provate a fare l'altro problema usando questo approccio...)

1) Possiamo pensare che nelle posizioni dispari siamo autorizzati a mettere $0,1,2,3,4$ e in quelle pari $2,3,4,5,6$, tanto modulo 6 non cambia niente
2) Consideriamo $f(x)=\underbrace{(1+x+x^2+x^3+x^4)(x^2+x^3+x^4+x^5+x^6) \cdot \ldots \cdot (1+x+x^2+x^3+x^4)(x^2+x^3+x^4+x^5+x^6) }_{5 volte}$. Sviluppando questo polinomio otteniamo dei monomi in cui l'esponente è la somma degli esponenti che abbiamo preso e il coefficiente è il numero di modi per realizzare quella somma
3) Quindi vogliamo sapere qual è la somma dei coefficienti dei monomi di $f(x)$ in cui l'esponente è multiplo di 6
4) Osserviamo che se $\mu_6$ è l'insieme delle radici seste dell'unità vale $\displaystyle \sum_{\zeta \in \mu_6} \zeta^n = \begin{cases} 0, \mbox{ se } 6 \nmid n \\ 6, \mbox{ altrimenti}\end{cases}$
5) basta quindi calcolare $\displaystyle \frac{1}{6} \sum_{\zeta \in \mu_6} f(\zeta)$
6) ma questo è facile: infatti $\displaystyle f(x)=(1+x+x^2+x^3+x^4)^{10} \cdot x^{10} = \frac{(x^5-1)^{10} x^{10}}{(x-1)^{10}}$ per $x \neq 1$ e $f(1)= 5^{10}$. Non è difficile verificare che $f(\zeta)=1$ per ogni radice sesta dell'unità diversa da 1, e abbiamo finito.