Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 AIME II Problems/Problem 14"

m
(→‎Solution 2)
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Consider a string of <math> n </math> <math> 7 </math>'s, <math> 7777\cdots77, </math> into which <math> + </math> signs are inserted to produce an arithmetic expression. For example, <math> 7+77+777+7+7=875 </math> could be obtained from eight <math> 7 </math>'s in this way. For how many values of <math> n </math> is it possible to insert <math> + </math> signs so that the resulting expression has value <math> 7000 </math>?
+
Consider a string of <math> n </math> <math> 7 </math>'s, <math> 7777\cdots77, </math> into which <math> + </math> signs are inserted to produce an arithmetic [[expression]]. For example, <math> 7+77+777+7+7=875 </math> could be obtained from eight <math> 7 </math>'s in this way. For how many values of <math> n </math> is it possible to insert <math> + </math> signs so that the resulting expression has value <math> 7000 </math>?
  
−
== Solution ==
+
== Solution 1 ==
−
{{solution}}
+
Suppose we require <math>a</math> <math>7</math>s, <math>b</math> <math>77</math>s, and <math>c</math> <math>777</math>s to sum up to <math>7000</math> (<math>a,b,c \ge 0</math>). Then <math>7a + 77b + 777c = 7000</math>, or dividing by <math>7</math>, <math>a + 11b + 111c = 1000</math>. Then the question is asking for the number of values of <math>n = a + 2b + 3c</math>.
 +
 
 +
Manipulating our equation, we have <math>a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 < 9(b+12c) < 1000</math>. Thus the number of potential values of <math>n</math> is the number of multiples of <math>9</math> from <math>0</math> to <math>1000</math>, or <math>112</math>.
 +
 
 +
 
 +
However, we forgot to consider the condition that <math>a \ge 0</math>. For a solution set <math>(b,c): n=1000-9(b+12c)</math>, it is possible that <math>a = n-2b-3c < 0</math> (for example, suppose we counted the solution set <math>(b,c) = (1,9) \Longrightarrow n = 19</math>, but substituting into our original equation we find that <math>a = -10</math>, so it is invalid). In particular, this invalidates the values of <math>n</math> for which their only expressions in terms of <math>(b,c)</math> fall into the inequality <math>9b + 108c < 1000 < 11b + 111c</math>. 
 +
 
 +
For <math>1000 - n = 9k \le 9(7 \cdot 12 + 11) = 855</math>, we can express <math>k</math> in terms of <math>(b,c): n \equiv b \pmod{12}, 0 \le b \le 11</math> and <math>c = \frac{n-b}{12} \le 7</math> (in other words, we take the greatest possible value of <math>c</math>, and then "fill in" the remainder by incrementing <math>b</math>). Then <math>11b + 111c \le 855 + 2b + 3c \le 855 + 2(11) + 3(7) = 898 < 1000</math>, so these values work.
 +
 
 +
Similarily, for <math>855 \le 9k \le 9(8 \cdot 12 + 10) = 954</math>, we can let <math>(b,c) = (k-8 \cdot 12,8)</math>, and the inequality <math>11b + 111c \le 954 + 2b + 3c \le 954 + 2(10) + 3(8) = 998 < 1000</math>. However, for <math>9k \ge 963 \Longrightarrow n \le 37</math>, we can no longer apply this approach.
 +
 
 +
So we now have to examine the numbers on an individual basis. For <math>9k = 972</math>, <math>(b,c) = (0,9)</math> works. For <math>9k = 963, 981, 990, 999 \Longrightarrow n = 37, 19, 10, 1</math>, we find (using that respectively, <math>b = 11,9,10,11 + 12p</math> for integers <math>p</math>) that their is no way to satisfy the inequality <math>11b + 111c < 1000</math>.
 +
 
 +
Thus, the answer is <math>112 - 4 = \boxed{108}</math>.
 +
 
 +
 
 +
----
 +
 
 +
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 <math>n \equiv 1 \pmod{9}</math>, and noting that small values of <math>n</math> would not work. 
 +
 
 +
Looking at the number <math>7000</math>, we obviously see the maximum number of <math>7's</math>: a string of <math>1000 \ 7's</math>.  Then, we see that the minimum is <math>28 \ 7's: \ 777*9 + 7 = 7000</math>.  The next step is to see by what interval the value of <math>n</math> increases.  Since <math>777</math> is <math>3 \ 7's, \ 77*10 + 7</math> is <math>21 \ 7's</math>, we can convert a <math>777</math> into <math>77's</math> and <math>7's</math> and add <math>18</math> to the value of <math>n</math>.  Since we have <math>9 \ 777's</math> to work with, this gives us <math>28,46,64,82,100,118,136,154,172,190 ( = 28 + 18n | 1\leq n\leq 9)</math> as values for <math>n</math>.  Since <math>77</math> can be converted into <math>7*11</math>, we can add <math>9</math> to <math>n</math> by converting <math>77</math> into <math>7's</math>.  Our <math>n = 190</math>, which has <math>0 \ 777's \ 90 \ 77's \ 10 7's</math>.  We therefore can add <math>9</math> to <math>n \ 90</math> times by doing this.  All values of <math>n</math> not covered by this can be dealt with with the <math>n = 46 \ (8 \ 777's \ 10 \ 77's \ 2 \ 7's)</math> up to <math>190</math>.
 +
 
 +
== Solution 2==
 +
To simplify, replace all the <math>7</math>’s with <math>1</math>’s.
 +
Because the sum is congruent to <math>n \pmod 9</math> and <cmath>1000 \equiv 1 \pmod 9 \implies n \equiv 1 \pmod 9</cmath>
 +
Also, <math>n \leq 1000</math>. There are <cmath> \left \lfloor \frac{1000}{9} \right \rfloor + 1 = 112 \textrm{ positive integers that satisfy both conditions i.e. } \{1, 10, 19, 28, 37, 46, . . . , 1000\}.</cmath>
 +
 
 +
For <math>n = 1, 10, 19</math>, the greatest sum that is less than or equal to <math>1000</math> is <math>6 \cdot 111 + 1 = 677 \implies 112-3 = 109</math>.
 +
 
 +
 
 +
Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>.
 +
 
 +
Note that <math>n=28</math> is possible because <math>9 \cdot 111+1 \cdot 1 = 1000</math>.
 +
 
 +
When <math>n = 37</math>, the greatest sum that is at most <math>1000</math> is <math>8 \cdot 111+6\cdot 11+1 \cdot 1 = 955</math>.
 +
 
 +
 
 +
All other elements of <math>S</math> are possible because if any element <math>n</math> of <math>S</math> between <math>46</math> and <math>991</math> is possible, then <math>(n+ 9)</math> must be too.
 +
 
 +
 
 +
<math>\textrm{Case } 1:\text{ Sum has no } 11</math>’s
 +
 
 +
It must have at least one <math>1</math>.
 +
If it has exactly one <math>1</math>, there must be nine <math>111</math>’s and <math>n = 28</math>.
 +
Thus, for <math>n \geq 46</math>, the sum has more than one <math>1</math>, so it must have at least <math>1000 - 8 \cdot 111 = 112</math> number of <math>1</math>’s.
 +
For <math>n \leq 1000</math>, at least one <math>111</math>.
 +
To show that if <math>n</math> is possible, then <math>(n + 9)</math> is possible, replace a <math>111</math> with <math>1 + 1 + 1</math>, replace eleven <math>(1 + 1)</math>’s with eleven <math>11</math>’s, and include nine new <math>1</math>’s as <math>+1</math>’s. The sum remains <math>1000</math>.
 +
 
 +
 
 +
<math>\textrm{Case } 2: \textrm{ Sum has at least one } 11</math>.
 +
 
 +
Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s.
 +
Now note that <math>46</math> is possible because <math>8 \cdot 111 + 10 \cdot 11 + 2 \cdot 1 = 1000</math>.
 +
Thus all elements of <math>S</math> except <math>37</math> are possible.
 +
 
 +
 
 +
Thus there are <math>\boxed{108}</math> possible values for <math>n</math>.
 +
 
 +
~phoenixfire
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2004|n=II|num-b=13|num-a=15}}
 
{{AIME box|year=2004|n=II|num-b=13|num-a=15}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 11:03, 5 October 2020

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 1

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 + 7 = 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$.

Solution 2

To simplify, replace all the $7$’s with $1$’s. Because the sum is congruent to $n \pmod 9$ and \[1000 \equiv 1 \pmod 9 \implies n \equiv 1 \pmod 9\] Also, $n \leq 1000$. There are \[\left \lfloor \frac{1000}{9} \right \rfloor + 1 = 112 \textrm{ positive integers that satisfy both conditions i.e. } \{1, 10, 19, 28, 37, 46, . . . , 1000\}.\]

For $n = 1, 10, 19$, the greatest sum that is less than or equal to $1000$ is $6 \cdot 111 + 1 = 677 \implies 112-3 = 109$.


Thus $n \geq 28$ and let $S = \{28, 37, 46, . . . , 1000\}$.

Note that $n=28$ is possible because $9 \cdot 111+1 \cdot 1 = 1000$.

When $n = 37$, the greatest sum that is at most $1000$ is $8 \cdot 111+6\cdot 11+1 \cdot 1 = 955$.


All other elements of $S$ are possible because if any element $n$ of $S$ between $46$ and $991$ is possible, then $(n+ 9)$ must be too.


$\textrm{Case } 1:\text{ Sum has no } 11$’s

It must have at least one $1$. If it has exactly one $1$, there must be nine $111$’s and $n = 28$. Thus, for $n \geq 46$, the sum has more than one $1$, so it must have at least $1000 - 8 \cdot 111 = 112$ number of $1$’s. For $n \leq 1000$, at least one $111$. To show that if $n$ is possible, then $(n + 9)$ is possible, replace a $111$ with $1 + 1 + 1$, replace eleven $(1 + 1)$’s with eleven $11$’s, and include nine new $1$’s as $+1$’s. The sum remains $1000$.


$\textrm{Case } 2: \textrm{ Sum has at least one } 11$.

Replace an $11$ with $1 + 1$, and include nine new $1$’s as $+1$’s. Now note that $46$ is possible because $8 \cdot 111 + 10 \cdot 11 + 2 \cdot 1 = 1000$. Thus all elements of $S$ except $37$ are possible.


Thus there are $\boxed{108}$ possible values for $n$.

~phoenixfire

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_14&oldid=134627"