2004 AIME II Problems/Problem 14

From AoPSWiki

Problem

Consider a string of $n$ $7$ 's, $7777\cdots77,$ into which $+$ signs are inserted to produce an arithmetic expression. For example, $7+77+777+7+7=875$ could be obtained from eight $7$ 's in this way. For how many values of $n$ is it possible to insert $+$ signs so that the resulting expression has value $7000$ ?

Solution

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

A note: Above, we formulated the solution in a forward manner (the last four paragraphs are devoted to showing that all the solutions we found worked except for the four cases pointed out; in a contest setting, we wouldn't need to be nearly as rigorous). A more natural manner of attacking the problem is to think of the process in reverse, namely seeing that $n \equiv 1 \pmod{9}$ , and noting that small values of $n$ would not work.

Looking at the number $7000$ , we obviously see the maximum number of $7's$ : a string of $1000 \ 7's$ . Then, we see that the minimum is $28 \ 7's: \ 777*9 + 1 = 7000$ . The next step is to see by what interval the value of $n$ increases. Since $777$ is $3 \ 7's, \ 77*10 + 7 is 21 \ 7's$ , we can convert a $777$ into $77's$ and $7's$ and add $18$ to the value of $n$ . Since we have $9 \ 777's$ to work with, this gives us $28,46,64,82,100,118,136,154,172,190 ( = 28 + 18n | 1\leq n\leq 9)$ as values for $n$ . Since $77$ can be converted into $7*11$ , we can add $9$ to $n$ by converting $77$ into $7's$ . Our $n = 190$ , which has $0 \ 777's \ 90 \ 77's \ 10 7's$ . We therefore can add $9$ to $n \ 90$ times by doing this. All values of $n$ not covered by this can be dealt with with the $n = 46 \ (8 \ 777's \ 10 \ 77's \ 2 \ 7's)$ up to $190$ .

2004 AIME II (Problems • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

2004 AIME II Problems/Problem 14

From AoPSWiki

Problem

Solution

See also