## Thursday, May 3, 2012

### Sum of randomly selected numbers

In a class with 10 students, each student is allowed to choose a number from the following list: 100,101,102,300,301,302. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be 2012? Two "ways" are considered distinct if there is at least one student who chooses different numbers.

Variant: In a class with $2n+1$ students, each student is allowed to choose a number from the following list: $n, n+1, -n, -n-1$. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be zero?

Solution Suppose the number of students who chose 100,101,102,300,301,302 are $a,b,c,d,e,f$ respectively, so we have: $$a+b+c+d+e+f = 10$$ and $$100.a + 101.b + 102.c + 300.d + 301.e+ 302.f = 2012$$

Note that we can write 100=201-100-1, 101 as 201-100, 102 as 201-100+1, 300 as 201+100-1, 301 as 201+100, 302 as 201+100+1, so the second equation becomes: $$201(a+b+c+d+e+f) + 100(d+e+f-a-b-c) + (c+f-a-d) = 2012$$ Since $a+b+c+d+e+f = 10$ then: $$100(d+e+f-a-b-c) + (c+f-a-d) = 2$$

Now, since $|c+f-a-d| \leq 10$ then it must be the case that: $$d+e+f-a-b-c = 0$$ and $$c+f-a-d = 2$$

We also note that when the students choose one of the numbers, they're essentially making two choices: first, they choose if they want to choose small or big numbers (be included in $a+b+c$ or $d+e+f$), and second, they choose if they want their number to end with 0,1, or 2 (be included in $a+d, b+e$ or $c+f$).

Thus, the number of ways to satisfy the first constraint $a+b+c = d+e+f = 5$ is 10C5, which means 5 students choose the small numbers and the rest choose the big numbers.

In order to satisfy $c+f - a - d = 2$, we make the following substitutions: $x = a+d, y = b+e, z = c+f$. Then $x+y+z = 20, z-x = 2$. We divide the cases by the values of $z$. Note that once a student chooses to be included in $x$ or $y$ or $z$, he only needs to choose if he wants to choose a big or small number, since each of $x,y,z$ contains exactly one big and one small number.

If $z > 6$ then $x > 4$, impossible.

If $z = 6$, then $x = 4, y = 0$. There are 10C6 = 210 ways to choose this.
If $z = 5$, then $x = 3, y = 2$, there are 10! / 2! 5! 3! = 2520 ways.
If $z = 4$, then $x = 2, y = 4$, there are 10! / 4! 4! 2! = 3150 ways.
If $z = 3$, then $x = 1, y = 6$, there are 10! / 3! 6! 1! = 840 ways.
If $z = 2$, then $x = 0, y = 8$, there are 10C8 = 45 ways.

If $z < 2$ then $x < 0$, impossible.

So the total number of ways is $$_{10}C_{5} (210+2520+3150+840+45) = _{10}C_{5} 6765 = 1 704 780$$

Solution to variant

Suppose the number of students who chose $-n-1, n+1, -n, n$ are $a,b,c,d$ respectively, so we have: $$a+b+c+d = 2n+1$$ $$(n+1)(b-a) + n(d-c) = 0$$

Note that because $n$ and $n+1$ are relatively prime, so we must have $n+1 | d-c$. But $|d-c|$ can take any values from $0$ to $2n+1$, so $d-c = 0, n+1, -(n+1)$.

If $d-c=0$, then $b-a=0$, which means $a+b+c+d$ would be even, impossible.

If $d-c=n+1$, then $b-a = -n$. Combined with $a+b+c+d = 2n+1$ we have $(a,b,c,d) = (n,0,0,n+1)$. (Remember that $a,b,c,d$ have to be non-negative).

This means that $n$ of the students choose $-n-1$ and the other $n+1$ choose $n$. There are $_{2n+1}C_{n}$ ways to do that.

The case of $d-c = -n-1$ is similar, where $(a,b,c,d) = (0,n,n+1,0)$, and there are $_{2n+1}C_{n}$ ways. Note that all these ways are disjoint, so the total number of ways is $2_{2n+1}C_{n}$