# 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?

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?

• There a only two copies of $0$ which you put a sign before. It is also worth noting that $1$ and $4$ have essentially the same effect, as do $2$ and $3$. So you effectively have two $0$s, five $1$s and five $2$s. Order of the numbers does not matter (addition is commutative) and a $1$ and a $2$ combined has an almost stable effect times $2^2$, so five pairs at gives about $\frac{2^{10}}5$ of each mod $5$ value (more precisely $204$ equivalent to $0$ mod $5$, and $205$ for the others); the two copies of $0$ each multiplies the possibilities by $2$, giving $816$ equivalent to $0$ mod $5$ Commented Nov 25, 2022 at 18:40
• The title (and your Approach) says you can place both plus and minus signs in front of zero, however the quoted question says $−$ sign can be only in between the numbers. The difference would be exactly a factor of $2$, so you should clarify. From your computer program it appears you did not consider a $−$ sign before the zero as a valid pattern, else the count would have been $1632$. Commented Nov 26, 2022 at 6:47
• The quoted part is directly from the NIMO paper. My interpretation is wrong. I apologise. Commented Nov 26, 2022 at 10:34

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}.$$

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$$

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.