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.

  • 4
    $\begingroup$ Whatever it is, HW or not, one would expect you show some self effort, some work, some ideas on what's going on here... $\endgroup$ – DonAntonio Mar 25 '14 at 13:54
  • $\begingroup$ $(0,....,0)$ or $a_{i}=0$ is a solution since $11|0$ is true. $\endgroup$ – Danny Mar 25 '14 at 14:03
  • $\begingroup$ Consider $1+z+...+z^9$ If we put $(1+z+...+z^9)^n$ the coefficient of $z^k$ in its expansion will be the number of ways to write $k$ as a sum of $n$ numbers from $\{0,...,9\}$. Similarly, in $f(z)=(1+z+...+z^9)^n(1+z^{-1}+...+z^{-9})^n$ the coefficient of $z^k$ is the number of ways to write $k$ as $\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i$, with $a_i\in\{0,...,9\}$. Now we only need to remove from there the terms with exponents that are not multiples of $11$, consider $w=e^{2\pi i/11}$. Recall that $1+w+...+w^{10}=0$, and $w^{11}=1$. Then $(f(z)+f(wz)+...+f(w^{10})/11$ ... $\endgroup$ – OR. Mar 25 '14 at 14:33
  • $\begingroup$ has the terms of $f$ with exponents divisible by $11$. Finally, since we want to count all possible series for all possible sum divisible by $11$ we can take $(f(z)+f(wz)+f(w^2z)+...+f(w^{10}z))/11$ and evaluate it at $z=1$. $\endgroup$ – OR. Mar 25 '14 at 14:37
  • $\begingroup$ Now notice that we can simplify $f$. We have$f(z)=\left(\frac{z^{10}-1}{z-1}\right)^n\left(\frac{z^{0}-z^{10}}{z^{9}-z^{10}}\right)^n$ $\endgroup$ – OR. Mar 25 '14 at 14:43

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.

  • $\begingroup$ There is a wait of 14 hours until you get your bounty. $\endgroup$ – OR. Mar 28 '14 at 0:08
  • $\begingroup$ Why the down vote? $\endgroup$ – Calvin Lin Mar 29 '14 at 19:22
  • $\begingroup$ Could it be that you made a small mistake when replacing $(-\omega^{10i})^n$ by $-\omega^{10in}$ or is there something else you did? If so, there would be different answers depending on the parity of $n$, namely $10\left(\frac{10^n+1}{11}\right)^2+\left(\frac{10^n-10}{11}\right)^2$ for odd $n$ and $10\left(\frac{10^n-1}{11}\right)^2+\left(\frac{10^n+10}{11}\right)^2$ for even $n$, right? I suppose so, because the result you got for $A_r$ is not integer for even $n$, as $10^{2m}\equiv1\pmod{11}$. But apart from this, nice solution! It took me some time to understand but I learned much from it! $\endgroup$ – punctured dusk Apr 4 '14 at 13:00
  • $\begingroup$ @barto Yes indeed! Updated. $A_r$ wouldn't have been an integer in certain cases. $\endgroup$ – Calvin Lin Apr 4 '14 at 20:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.