The String of 7

As Johanz points out, we need to count the numbers $n$ such that the system $a+11b+111c=1000, a+2b+3c=n$ has non-negative integer solutions $a,b,c$ . Subtracting the equations from each other, we see that $9b+108c=1000-n$ , so that $1000-n$ is divisible by 9. We can write $n=1000-9k$ for some $0\leq{k}\leq{111}$ .

Our equations can now be written as $a=21c+1000-11k,b=k-12c$ . We need to choose $k$ and $c$ so that both $a$ and $b$ come out non-negative, meaning that $12c\leq{k}\leq{\frac{21c+1000}{11}}$ . If we let $c=0$ , we get solutions $0\leq{k}\leq{90}$ . If we let $c=7$ , we get solutions $84\leq{k}\leq{104}$ .(Why don't we need to check $1\leq{c}\leq{6}$ ).If we let $c=8$ , we get solutions $96\leq{k}\leq{106}$ . If we let $c=9$ , we get the single solution $k=108$ . Thus there are $\boxed{108}$ solutions overall, namely $0\leq{k}\leq{106}$ and $k=108$ .

This work may become clearer if you look at the "feasible region" in the $c-k$ plane, $12c\leq{k}\leq{\frac{21c+1000}{11}}$ , a triangle.

Suppose we require $a$ $7$ s, $b$ $77$ s, and $c$ $777$ s to sum up to $7000$ ( $a,b,c \ge 0$ ). Then $7a + 77b + 777c = 7000$ , or dividing by $7$ , $a + 11b + 111c = 1000$ . Then the question is asking for the number of values of $n = a + 2b + 3c$ .

Manipulating our equation, we have $a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 < 9(b+12c) < 1000$ . Thus the number of potential values of $n$ is the number of multiples of $9$ from $0$ to $1000$ , or $112$ .

However, we forgot to consider the condition that $a \ge 0$ . For a solution set $(b,c): n=1000-9(b+12c)$ , it is possible that $a = n-2b-3c < 0$ (for example, suppose we counted the solution set $(b,c) = (1,9) \Longrightarrow n = 19$ , but substituting into our original equation we find that $a = -10$ , so it is invalid). In particular, this invalidates the values of $n$ for which their only expressions in terms of $(b,c)$ fall into the inequality $9b + 108c < 1000 < 11b + 111c$ .

For $1000 - n = 9k \le 9(7 \cdot 12 + 11) = 855$ , we can express $k$ in terms of $(b,c): n \equiv b \pmod{12}, 0 \le b \le 11$ and $c = \frac{n-b}{12} \le 7$ (in other words, we take the greatest possible value of $c$ , and then "fill in" the remainder by incrementing $b$ ). Then $11b + 111c \le 855 + 2b + 3c \le 855 + 2(11) + 3(7) = 898 < 1000$ , so these values work.

Similarily, for $855 \le 9k \le 9(8 \cdot 12 + 10) = 954$ , we can let $(b,c) = (k-8 \cdot 12,8)$ , and the inequality $11b + 111c \le 954 + 2b + 3c \le 954 + 2(10) + 3(8) = 998 < 1000$ . However, for $9k \ge 963 \Longrightarrow n \le 37$ , we can no longer apply this approach.

So we now have to examine the numbers on an individual basis. For $9k = 972$ , $(b,c) = (0,9)$ works. For $9k = 963, 981, 990, 999 \Longrightarrow n = 37, 19, 10, 1$ , we find (using that respectively, $b = 11,9,10,11 + 12p$ for integers $p$ ) that their is no way to satisfy the inequality $11b + 111c < 1000$ .

Thus, the answer is $112 - 4 = \boxed{108}$ .

Its obvious that $7000 = 7(1000)$ .

Divide the problem into 10 cases which in the $k^{th}$ case $1000 = 111k + m$ for a positive integer $m$ .

From the 10 cases we got $n \in S$ with

$S$ = {28, 46, 55, 64, ..., 1000} = {28, 9(5) + 1, 9(6) + 1, ..., 9(111) + 1}.

It implies that there are exactly 108 positive integer $n$ possible.