Find the number of series

Question

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that:

$$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$

(this is not a homework)

There is a similar problem (Problem 6) in the IMO 1995.

Answer 1

Since the second term is larger than the first term

-Sum = (2n * (2n+1))/2 - 2*(n*(n+1))/2 = n*(2n+1) -n*(n+1) =n*n

(Sorry not used to site so plain english).

So 11 divides the series iff 11 divides n.

Answer 2

For a fixed $n$, let $ A_r $ be the number of sequences of $n$ terms, whose sum is $r \pmod{11}$. Then, we want the value of $ \sum A_r ^2 $.

As pointed out by ABC, the generating function $f(x) = \left ( 1 + x + x^2 + \ldots + x^9 \right) ^n $ gives us the number of sequences of $n$ terms, with a total sum of $r$. We find the sum of those coefficients with the power mod 11, we use the typical counting trick. Let $\omega$ be a primitive 11th root of unity. We know that $ 1 + \omega + \omega^2 + \ldots + \omega^{10} = 0 $. For $ i \not \equiv 0 \pmod{11}$, we have $ f( \omega^i) = ( -\omega^{10i})^n$

We have $$ 11 A_r = \sum_{i=0}^{10} \omega^{-ri} f( \omega^i) = 10^n + \sum_{i=1}^{10} \omega^{-ri} (- \omega^{10i})^n = 10^n + (-1)^n \sum_{i=1}^{10} \omega^{(10n-r)i}. $$

In particular, this shows that for $r \neq 10n \pmod{11}$, we have $A_r = \frac{10^n-(-1)^{n}}{11}$. Otherwise, for $R \equiv 10n \equiv -n \pmod{11}$, we have $A_R = \frac{10^n+10 \times (-1)^n}{11}$.

Hence, we can now find the sum as

$$ \sum_{r=0}^{10} A_r^2 = 10 \left (\frac{10^n-(-1)^n}{11} \right)^2 + \left( \frac{10^n+10\times (-1)^n}{11} \right)^2$$

---

Note: This solution is nice 9 because 2 less than 11, which makes $f(\omega^i)$ easy to evaluate. For a much more general case, the equations would not be pretty.