# How many distinct values of $x_1+x_2+x_3+x_4+x_5+x_6+x_7$ when $x_1,x_2,x_3,..,x_7 \in \{0,3,4,5\}$

I have a multiple choice question.

Suppose $x_1,x_2,x_3,..,x_7 \in \{0,3,4,5\}$. How many distinct answers are possible for $A$, when $A=x_1+x_2+x_3+x_4+x_5+x_6+x_7$?

Choices:
14
30
34
28

I can try to put all the $(0,0,...,0), (3,0,0,...,0) ... (5,5,5,...,5)$, but it takes a long time. I think there is a trick to find the possible answer by combinatorics, but how?

Clearly, we have $0\leq A\leq 35$, so there are at most $36$ possibilities. Also clearly $A\neq 1,2$. In fact any other $A$ is possible. (Maybe you can prove this yourself; if not there is a spoilered explanation below.)

Starting from $0,0,0,0,0,0,3$ you can go through every number as follows. If there is an $x_i$ which is $3$ or $4$, replace it by $x_i+1$. If not you have all $0$ and $5$, and at least one of each, so replace $0,5$ by $3,3$. In this way from an arrangement for $A$ you can get $A+1$, provided $3\leq A<35$.

So the answer is $34$.

Leaving out $1,2$, we get that a number is of five forms : $5n + 0,1,2,3,4$.

$5n : n \times 5$, $0 \leq n \leq 7$.

$5n+1 : (n-1) \times 5 + 2 \times 3$, $1 \leq n \leq 6$.

$5n+2 : (n-1) \times 5 + 3 + 4$, $1 \leq n \leq 6$.

$5n+3 : (n) \times 5 + 3$, $0 \leq n \leq 6$.

$5n+4 : (n) \times 5 + 4$, $0 \leq n \leq 6$.

Which means precisely two numbers are left out from the set $\{0,1,...,35\}$, all the rest can be expressed in the form you have stated.

• It is also possible to get $0$ by setting each $x_k = 0$. – N. F. Taussig Oct 14 '17 at 9:06
• But of course. That case comes from the first case I have written, by setting $n = 0$, by which I meant the rest(in this case all) are substituted by zeros. – астон вілла олоф мэллбэрг Oct 14 '17 at 9:06
• The reason I pointed this case out is that you omitted $0$ from the set of possible outcomes in the final sentence, so there are a total of $34$ possible outcomes. – N. F. Taussig Oct 14 '17 at 9:14
• Oh, yes, I will add it in. – астон вілла олоф мэллбэрг Oct 14 '17 at 9:15
• Thank you for the vote! – астон вілла олоф мэллбэрг Oct 14 '17 at 9:16

If we impose the condition $x_i\in\{0,3\}$ we can do all multiples of $3$ from $0$ to $21$. Since in reality we are allowed to increase any present $3$ by one or two we can do all integers in the following union of intervals: $$[0,0]\cup[3,5]\cup[6,10]\cup[9,15]\cup\ldots\cup[21,35]\ .$$ Since the later intervals overlap it follows that we can do all integers from $0$ to $35$ with the exception of $1$ and $2$. The answer to the question therefore is $34$.