How many ways to place plus and minus signs in front of numbers from 0 to 12 so that the sum is divisible by 5?

Question

This question is from an old NIMO contest.

Find the number of ways a series of + and − signs can be inserted between the numbers 0, 1, 2, · · ·, 12 such that the value of the resulting expression is divisible by 5.

A computer program seems to indicate that the answer is 816.

Approach: Reduce the problem to mod 5. There are three copies of 0,1,2 and two copies of 3,4. Now suppose there are exactly $x_i$ plus signs for copy $i$. We see that for the sum to be divisible by 5, we must have $\sum ix_i =$ 4 mod 5. Now I was planning to crunch it out or use generating functions, but it looks complicated.

Suggestions?

Answer 1

Unfortunately, I don't think this method is easy to generalize, but allows this problem to be solved with little casework.

Throw out $5$ and $10$ (we will multiply by $4$ to account for this at the end). Note that $+1 \equiv -4 \pmod{5}$, so in some sense we have $5$ copies of $1$ and $5$ copies of $2$. Say that $a_1$ copies of $1$ have a $+$ in front of them, and define $a_2$ similarly. Then, we must have $$ a_1 - (5-a_1) + 2a_2 - 2(5-a_2) \equiv 2a_1 + 4a_2 \equiv 0 \pmod{5} $$ so we sum up $\binom{5}{a_1} \binom{5}{a_2}$ for values such that the above is true. However, note that if $a_1$ is $\pm 1 \pmod{5}$ then $a_2$ is $\pm 2\pmod{5}$, and vice versa. If $a_1 \equiv 0 \pmod{5}$, there are $4$ choices: $a_1,a_2 \in \{0,5\}$. Thus, the answer is $$ 4 \left( 4\binom{5}{1}\binom{5}{2} + 4\right) = \fbox{816}. $$

Answer 2

Let $f(n)$ be the required count for numbers $0, 1, 2, 3, \dots n$.

Similar to fleablood's initial approach, if $n=12$, note the last two, $\pm12\pm11 \equiv \pm1\pm2 \pmod 5$ cover all the numbers in $1, 2, 3, 4 \pmod 5$ exactly once, hence as long as the numbers till $10$ are NOT divisible by $5$, we have a valid pattern. Hence $f(12) = 2^{10}-f(10)$.

This logic is generalisable to $f(n+2) = 2^n-f(n)$ for all natural $n \in \{0, 2\} \pmod 5$.

Further, it is easily seen $f(n)=2f(n-1)$ if $n\equiv 0 \pmod 5$, as adding $\pm n \equiv 0$ retains the divisibility. Hence $f(n+2) = 2^n-2f(n-1)$ when $n\equiv 0 \pmod 5$

With these, we have enough to solve the problem. Starting with observing $f(2)=0, f(4) = 4-f(2)=4, f(7) = 2^5-2\cdot 4=24, f(9) = 2^7-f(7) = 104, f(12) = 2^{10} - 2\cdot 104 = 816$

Answer 3

It does matter what we put in front of the $0,5,10$. Of the $2^3\pm$ combinations you can do for those the result will have the same divisibility as any other. So It suffices to solve for $1,2,3,4,6,7,8,9,11,12$ and multiply the result by $8$.

Consider $A_1 = \pm 1 \pm 2\pm 3\pm 4$ and $A_2=\pm 6\pm 7\pm 8 \pm 9$ and $B = \pm 11\pm 12$. $B$ can never be divisible by $5$ but of the four values it can have it can be by divisible by $1,2,3$ or $4$ meaning $A_1 + A_2$ must be $\equiv -B\pmod 5$.

Going through the 16 possible values of $A_1$ (and equivalently $A_2$) There are $4$ that are congruent to $0$ $(\pm(1+4)\pm(2+3)$; $3$ that are congruent to $1$ (basically $-7+3$); $3$ that are congruent to $2$ ($6-4=1+2+3-4; 8-2=1-2+3+4;9-1=-1+2+3+4$; $3$ that are congruent to $3\equiv -2$ (symmetry; and $3$ that are congruent to $4$.

Okay: If $B\equiv 1 \pmod 5$ (that is $-11+12$) we must have $A_1+A_2 \equiv 4$ so we must have $A_1,A_2\equiv (0,4),(1,3), (2,2)$ there are $4\times 3$ ways to do $(0,4)$ and $3\times 3$ ways to do $(1,3)$ or $(2,2)$. so there are $12 + 9+9=30$ ways to do that.

If $B \equiv 2 \pmod 5$ (that is $-11-12$) we must have $A_1+A_2\equiv 3$ so we must have $A_1,A_2 \equiv (0,3), (1,2),(4,4)$ and there are $4\times 3=12$ and $3\times 3$ and $3\times 3$ respectively to do that. So there are $30$ ways.

By symmetry the some is true for $B\equiv 3,4\pmod 5$.

So there should by $8\times 4\times 30 = 960$ ways.

I don't know if I or you have an error (probably I do) but that is how I solved it.