Difference between revisions of "2004 AIME II Problems/Problem 14"
m |
Phoenixfire (talk | contribs) (→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 2: | Line 2: | ||
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 == |
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>. | 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>. | ||
Line 23: | Line 23: | ||
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. | 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>. | + | 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>. | ||
== See also == | == See also == |
Revision as of 13:02, 21 September 2020
Contents
Problem
Consider a string of 's, into which signs are inserted to produce an arithmetic expression. For example, could be obtained from eight 's in this way. For how many values of is it possible to insert signs so that the resulting expression has value ?
Solution 1
Suppose we require s, s, and s to sum up to (). Then , or dividing by , . Then the question is asking for the number of values of .
Manipulating our equation, we have . Thus the number of potential values of is the number of multiples of from to , or .
However, we forgot to consider the condition that . For a solution set , it is possible that (for example, suppose we counted the solution set , but substituting into our original equation we find that , so it is invalid). In particular, this invalidates the values of for which their only expressions in terms of fall into the inequality .
For , we can express in terms of and (in other words, we take the greatest possible value of , and then "fill in" the remainder by incrementing ). Then , so these values work.
Similarily, for , we can let , and the inequality . However, for , we can no longer apply this approach.
So we now have to examine the numbers on an individual basis. For , works. For , we find (using that respectively, for integers ) that their is no way to satisfy the inequality .
Thus, the answer is .
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 , and noting that small values of would not work.
Looking at the number , we obviously see the maximum number of : a string of . Then, we see that the minimum is . The next step is to see by what interval the value of increases. Since is is , we can convert a into and and add to the value of . Since we have to work with, this gives us as values for . Since can be converted into , we can add to by converting into . Our , which has . We therefore can add to times by doing this. All values of not covered by this can be dealt with with the up to .
Solution 2
To simplify, replace all the ’s with ’s. Because the sum is congruent to and Also, . There are
For , the greatest sum that is less than or equal to is .
Thus and let .
Note that is possible because .
When , the greatest sum that is at most is .
All other elements of are possible because if any element of between and is possible, then must be too.
’s
It must have at least one . If it has exactly one , there must be nine ’s and . Thus, for , the sum has more than one , so it must have at least number of ’s. For , at least one . To show that if is possible, then is possible, replace a with , replace eleven ’s with eleven ’s, and include nine new ’s as ’s. The sum remains .
.
Replace an with , and include nine new ’s as ’s. Now note that is possible because . Thus all elements of except are possible.
Thus there are possible values for .
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.