How many ways to sum up to 2017 by adding 1 , 2 and 4

Question

Given numbers 1, 2 and 4, how many ways there are to add up to 2017, with order not mattering?

I searched but can't find a systematic solution to this. This is supposed to a middle school level math problem.

Answer 1

Let $a,b,c$ be nonnegative integers such that $$a+2b+4c= 2017$$

We see that $c\leq 504$ and for each fixed $c$ you have that $b$ is at most $1008-2c$, since $$ 2b\leq a+2b = 2017-4c$$

So for each $c$ we have $1008-2c+1$ possibilites for $b$. For each $b$ (and $c$) we have determined uniqly $a$. So we have

$$(1009-2\cdot 0)+ (1009-2\cdot 1)+...+(1009-2\cdot 504)=505 \cdot 1009 -2{504\cdot 505\over 2}=505^2$$ solutions.

Answer 2

I believe that this is the intended middle school solution.

---

First note that we're always going to use at least one $1$, because $2017$ is odd and the other two numbers are even. So we can instead ask the number of ways to sum up to $2016$, knowing that we'll also tack one $1$ at the end.

Let's start with the solution of all $4$s, since $2016$ is divisible by $4$. $2016/4 = 504$, so we need $504$ of them to do it.

Now for each $4$ we have the option of splitting it into two $2$s. And for each $2$ we have the option of splitting it into two $1$s.

Let $k$ be the number of $4$s we split into $2$s and $l$ be the number of $2$s we then split into $1$s. Then our total amount of possibilities is:

$$\sum_{k=0}^{504}\sum_{l=0}^{2k} 1 = \sum_{k=0}^{504}(2k+1) = (505)^2 = 255025$$

Answer 3

As has been mentioned it's enough to find the answer for 2016 (instead of 2017) and just add a single 1 onto each number.

So let's count according to the number of 4s.

There is 1 way to write 2016 as all 4's, namely $4 \times 504$.

There are 3 ways to write 2016 with 503 4s, namely $4 \times 503 + 2 \times 2, 4 \times 503 + 2 \times 1 + 1 \times 2, 4 \times 503 + 1 \times 4$.

There are 5 ways to write 2016 with 502 4s, namely $4 \times 502 + 2 \times 4, 4 \times 502 + 2 \times 3 + 1 \times 2, 4 \times 502 + 2 \times 2 + 1 \times 4, 4 \times 502 + 2 \times 1 + 1 \times 6, 4 \times 502 + 1 \times 8$.

This pattern can be extended; there are $2k + 1$ ways to write $2016$ with $504 - k$ 4s, for $k = 0, 1, \ldots, 504$.

So the total number of ways to write $2016$ is $1 + 3 + 5 + \cdots + 1009$, the sum of the first $505$ odd integers. This is $505^2$ by the well-known identity

$$ 1 + 3 + 5 + \cdots + (2n-1) = n^2$$

As a sanity check, we could say that the number of ways to write $4n + 1$ as a sum of 1, 2, and 4, with order not mattering, is $(n+1)^2$. For $n = 1$ this says that there are $(1+1)^2 = 4$ ways to write 5: these are

$$ 4 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1. $$

And similarly there are $(2+1)^2 = 9$ ways to write 9: these are

$$ 4 + 4 + 1, 4 + 2 + 2 + 1, 4 + 2 + 1 + 1 + 1, 4 + 1 + 1 + 1 + 1 + 1, 2 + 2 + 2 + 2 + 1, 2 + 2 + 2 + 1 + 1 + 1, 2 + 2 + 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. $$

Answer 4

Since $2017$ is odd, you have to have a least one $1$. After that, you can specify any number of $2$s and $4$s that sum to $2016$ or less, filling out the remainder with $1$s. The number of ways to do this is equal to the number of ways to specify a number of $1$s and $2$ that sum to $1008$ or less. By letting the number of $2$s range from $0$ to $504$, this number is

$$1009+1007+1005+\cdots+5+3+1=505^2$$

(The final result uses the well known fact that the sum of the first $n$ odd integers is $n^2$. This may or may not, of course, be well known at the middle school level.)