https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Mroreojuice&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T05:40:50ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_14&diff=1417612004 AIME II Problems/Problem 142021-01-09T12:30:17Z<p>Mroreojuice: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
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>?<br />
<br />
== Solution 1 ==<br />
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>.<br />
<br />
Manipulating our equation, we have <math>a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 \le 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>.<br />
<br />
<br />
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>. <br />
<br />
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. <br />
<br />
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. <br />
<br />
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>. <br />
<br />
Thus, the answer is <math>112 - 4 = \boxed{108}</math>.<br />
<br />
<br />
---- <br />
<br />
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. <br />
<br />
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>.<br />
<br />
== Solution 2==<br />
To simplify, replace all the <math>7</math>’s with <math>1</math>’s. <br />
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><br />
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> <br />
<br />
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>.<br />
<br />
<br />
Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>.<br />
<br />
Note that <math>n=28</math> is possible because <math>9 \cdot 111+1 \cdot 1 = 1000</math>.<br />
<br />
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>. <br />
<br />
<br />
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. <br />
<br />
<br />
<math>\textrm{Case } 1:\text{ Sum has no } 11</math>’s<br />
<br />
It must have at least one <math>1</math>. <br />
If it has exactly one <math>1</math>, there must be nine <math>111</math>’s and <math>n = 28</math>. <br />
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.<br />
For <math>n \leq 1000</math>, at least one <math>111</math>. <br />
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>.<br />
<br />
<br />
<math>\textrm{Case } 2: \textrm{ Sum has at least one } 11</math>.<br />
<br />
Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s.<br />
Now note that <math>46</math> is possible because <math>8 \cdot 111 + 10 \cdot 11 + 2 \cdot 1 = 1000</math>.<br />
Thus all elements of <math>S</math> except <math>37</math> are possible. <br />
<br />
<br />
Thus there are <math>\boxed{108}</math> possible values for <math>n</math>.<br />
<br />
~phoenixfire<br />
<br />
== Solution 3 ==<br />
It's obvious that we cannot have any number <math>\ge 7777</math> because <math>7777 > 7000</math> so the max number that an occur is <math>777</math><br />
<br />
Let's say we have <math>a</math> 777's , <math>b</math> 77's and <math>c</math> 7's<br />
<br />
From here we get our required equation as <math>777a + 77b + 7c = 7000</math><br />
<br />
Now comes the main problem , one might think that if we find number of <math>(a,b,c)</math> then we're done , but in reality we are over-counting our number of <math>n</math>'s. This is because <math>n</math> is the total number of 7's and from our equation we'll get <math>n</math> as <math>3a + 2b + c</math> (because there are three 7's , two 7's and one 7) <br />
<br />
The reason why we're over-counting is because , say <math>a_1 , b_1 , c_1</math> be a solution of our original equation and <math>a_2 , b_2 , c_2</math> be another solution of our original equation , then there can be a possibility that <math>3a_1 + 2b_1 + c_1 = 3a_2 + 2b_2 + c_2</math> where <math>a_1 \neq a_2 , b_1 \neq b_2 , c_1 \neq c_2</math> (example : <math> 2 + 3 + 4 = 1 + 5 + 3</math> but <math>2 \neq 1 , 3 \neq 5 , 4 \neq 3</math><br />
<br />
We know that <math>0 \le a \le 9</math> , <math>0 \le b \le 90</math> , <math>0 \le c \le 1000</math><br />
The bound on <math>a</math> is easier to handle with , so lets start putting values on <math>a</math> and calculate <math>b , c , n</math> by making cases<br />
<br />
Reduced equation : <math>111a + 11b + c = 1000</math><br />
<br />
Case 1 : <math>a = 9</math><br />
<br />
We get <math>11b + c = 1 \implies b = 0 , c = 1</math> is our only solution thus only <math>\boxed{1}</math> value of <math>n</math><br />
<br />
Case 2 : <math>a = 8</math><br />
<br />
We get <math>11b + c = 112 \implies b = 0,1,2,\cdots ,10</math> and <math>c = 112 , 101 , 90,\cdots ,2</math> From here we get different <math>n</math>'s as <math>24 + 112 , 24 + 101 , 24 + 94, \cdots ,24 + 22</math> (remember <math>n = 3a + 2b + c</math> and if you have difficulty in understanding how we got <math>n = 24 + (\cdots)</math> then just put the values of <math>a,b,c</math> i am sure you will get it :) )<br />
<br />
Let's write the sequences of <math>n</math>'s in a compact form , <math>T_p = 24 + 22 + 9(p-1)</math> (This will be helpful later on)<br />
There are <math>\boxed{11}</math> values of <math>n</math><br />
<br />
Case 3 : <math>a = 7</math><br />
<br />
We get <math>11b + c = 223 \implies b=0,1,2, \cdots ,20</math> and <math>c = 223,212,201, \cdots ,3</math> From here we get different <math>n</math>'s as <math>21 + 223, 21 + 214 , 21 + 205, \cdots ,21 + 43</math><br />
<br />
Let's also write the sequences of <math>n</math>'s in a compact form , <math>T_q = 21 + 43 + 9(q-1)</math><br />
<br />
Now comes the major part , since we need to find distinct <math>n</math>'s so let's subtract the cases where we find common values , from the total number of values.<br />
<br />
To do this we need to make <math>T_p = T_q \implies p - q = 2</math> (after some calculations you'll get <math>p - q = 2</math>) . Now we know that <math>0 \le p \le 10</math> and <math>0 \le q \le 20</math> so we get <math>p</math> as <math>10,9,\cdots,2</math> and <math>q</math> as <math>8,7,\cdots,0</math> so there are 9 common solutions out of 21(diff values of <math>q</math>) total , so there are <math>\boxed{21 - 9}</math> values of <math>n</math><br />
<br />
Case 4 : <math>a = 6</math><br />
<br />
We get <math>11b + c = 334 \implies b = 0,1,2, \cdots ,30</math> and <math>c = 334,323,312, \cdots ,4</math> From here we get the different <math>n</math>'s as <math>18 + 334,18 + 325,18 + 316, \cdots ,18 + 64</math><br />
<br />
Compact form of terms is <math>T_r = 18 + 64 + 9(r-1)</math><br />
Now let's repeat the process of eliminating common solutions (one thing to notice is that we've removed common solutions of case 2 from case 3 so if we check case 4 with case 3 we'll remove common solutions from all previous cases and hence we do not have to handle common solutions of case 4 with case 2,1 and in general case X with case X-2,X-3,...2,1 , {basically means checking case X with case X-1 is enough})<br />
<br />
<math>T_q = T_r \implies 21 + 43 + 9(q-1) = 18 + 64 + 9(r-1) \implies q - r = 2</math><br />
<math>\implies q = 20,19,18, \cdots ,2</math> and <math>r = 18,17,16, \cdots ,0</math> so there are 19 common solutions out of 31 (diff values of r) so there are <math>\boxed{31 - 19}</math> values of <math>n</math><br />
<br />
Now hopefully you've seen a pattern , if not try another case 5 with <math>a = 5</math> you'll get <math>\boxed{41 - 29}</math> values of <math>n</math><br />
<br />
Like this we get the value of "distinct" <math>n</math> by summing all the sub-values from the cases that we've solved.<br />
<br />
<math>n = 1 + 11 + (21 - 9) + (31 - 19) + (41 - 29) + \cdots + (91 - 79)</math><br />
<br />
<math>\implies n = (1 + 11 + 21 + 31 + 41 + \cdots + 91) - (0 + 0 + 9 + 19 + 29 + \cdots + 79)</math><br />
<br />
<math>\implies \boxed{n = 108}</math><br />
<br />
~MrOreoJuice<br />
<br />
== See also ==<br />
<br />
{{AIME box|year=2004|n=II|num-b=13|num-a=15}}<br />
<br />
[[Category:Intermediate Number Theory Problems]]<br />
{{MAA Notice}}</div>Mroreojuicehttps://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_14&diff=1417602004 AIME II Problems/Problem 142021-01-09T12:21:40Z<p>Mroreojuice: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
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>?<br />
<br />
== Solution 1 ==<br />
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>.<br />
<br />
Manipulating our equation, we have <math>a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 \le 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>.<br />
<br />
<br />
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>. <br />
<br />
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. <br />
<br />
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. <br />
<br />
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>. <br />
<br />
Thus, the answer is <math>112 - 4 = \boxed{108}</math>.<br />
<br />
<br />
---- <br />
<br />
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. <br />
<br />
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>.<br />
<br />
== Solution 2==<br />
To simplify, replace all the <math>7</math>’s with <math>1</math>’s. <br />
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><br />
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> <br />
<br />
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>.<br />
<br />
<br />
Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>.<br />
<br />
Note that <math>n=28</math> is possible because <math>9 \cdot 111+1 \cdot 1 = 1000</math>.<br />
<br />
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>. <br />
<br />
<br />
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. <br />
<br />
<br />
<math>\textrm{Case } 1:\text{ Sum has no } 11</math>’s<br />
<br />
It must have at least one <math>1</math>. <br />
If it has exactly one <math>1</math>, there must be nine <math>111</math>’s and <math>n = 28</math>. <br />
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.<br />
For <math>n \leq 1000</math>, at least one <math>111</math>. <br />
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>.<br />
<br />
<br />
<math>\textrm{Case } 2: \textrm{ Sum has at least one } 11</math>.<br />
<br />
Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s.<br />
Now note that <math>46</math> is possible because <math>8 \cdot 111 + 10 \cdot 11 + 2 \cdot 1 = 1000</math>.<br />
Thus all elements of <math>S</math> except <math>37</math> are possible. <br />
<br />
<br />
Thus there are <math>\boxed{108}</math> possible values for <math>n</math>.<br />
<br />
~phoenixfire<br />
<br />
== Solution 3 ==<br />
It's obvious that we cannot have any number <math>\ge 7777</math> because <math>7777 > 7000</math> so the max number that an occur is <math>777</math><br />
<br />
Let's say we have <math>a</math> 777's , <math>b</math> 77's and <math>c</math> 7's<br />
<br />
From here we get our required equation as <math>777a + 77b + 7c = 7000</math><br />
<br />
Now comes the main problem , one might think that if we find number of <math>(a,b,c)</math> then we're done , but in reality we are over-counting our number of <math>n</math>'s. This is because <math>n</math> is the total number of 7's and from our equation we'll get <math>n</math> as <math>3a + 2b + c</math> (because there are three 7's , two 7's and one 7) <br />
<br />
The reason why we're over-counting is because , say <math>a_1 , b_1 , c_1</math> be a solution of our original equation and <math>a_2 , b_2 , c_2</math> be another solution of our original equation , then there can be a possibility that <math>3a_1 + 2b_1 + c_1 = 3a_2 + 2b_2 + c_2</math> where <math>a_1 \neq a_2 , b_1 \neq b_2 , c_1 \neq c_2</math> (example : <math> 2 + 3 + 4 = 1 + 5 + 3</math> but <math>2 \neq 1 , 3 \neq 5 , 4 \neq 3</math><br />
<br />
We know that <math>0 \le a \le 9</math> , <math>0 \le b \le 90</math> , <math>0 \le c \le 1000</math><br />
The bound on <math>a</math> is easier to handle with , so lets start putting values on <math>a</math> and calculate <math>b , c , n</math> by making cases<br />
<br />
Reduced equation : <math>111a + 11b + c = 1000</math><br />
<br />
Case 1 : <math>a = 9</math><br />
<br />
We get <math>11b + c = 1 \implies b = 0 , c = 1</math> is our only solution thus only <math>\boxed{1}</math> value of <math>n</math><br />
<br />
Case 2 : <math>a = 8</math><br />
<br />
We get <math>11b + c = 112 \implies b = 0,1,2,\cdots ,10</math> and <math>c = 112 , 101 , 90,\cdots ,2</math> From here we get different <math>n</math>'s as <math>24 + 112 , 24 + 101 , 24 + 94, \cdots ,24 + 22</math> (remember <math>n = 3a + 2b + c</math> and if you have difficulty in understanding how we got <math>n = 24 + (\cdots)</math> then just put the values of <math>a,b,c</math> i am sure you will get it :) )<br />
<br />
Let's write the sequences of <math>n</math>'s in a compact form , <math>T_p = 24 + 22 + 9(p-1)</math> (This will be helpful later on)<br />
There are <math>\boxed{11}</math> values of <math>n</math><br />
<br />
Case 3 : <math>a = 7</math><br />
<br />
We get <math>11b + c = 223 \implies b=0,1,2, \cdots ,20</math> and <math>c = 223,212,201, \cdots ,3</math> From here we get different <math>n</math>'s as <math>21 + 223, 21 + 214 , 21 + 205, \cdots ,21 + 43</math><br />
<br />
Let's also write the sequences of <math>n</math>'s in a compact form , <math>T_q = 21 + 43 + 9(q-1)</math><br />
<br />
Now comes the major part , since we need to find distinct <math>n</math>'s so let's subtract the cases where we find common values , from the total number of values.<br />
<br />
To do this we need to make <math>T_p = T_q \implies p - q = 2</math> (after some calculations you'll get <math>p - q = 2</math>) . Now we know that <math>0 \le p \le 10</math> and <math>0 \le q \le 20</math> so we get <math>p</math> as <math>10,9,\cdots,2</math> and <math>q</math> as <math>8,7,\cdots,0</math> so there are 9 common solutions out of 21(diff values of <math>q</math>) total , so there are <math>\boxed{21 - 9}</math> values of <math>n</math><br />
<br />
Case 4 : <math>a = 6</math><br />
<br />
We get <math>11b + c = 334 \implies b = 0,1,2, \cdots ,30</math> and <math>c = 334,323,312, \cdots ,4</math> From here we get the different <math>n</math>'s as <math>18 + 334,18 + 325,18 + 316, \cdots ,18 + 64</math><br />
<br />
Compact form of terms is <math>T_r = 18 + 64 + 9(r-1)</math><br />
Now let's repeat the process of eliminating common solutions (one thing to notice is that we've removed common solutions of case 2 from case 3 so if we check case 4 with case 3 we'll remove common solutions from all previous cases)<br />
<br />
<math>T_q = T_r \implies 21 + 43 + 9(q-1) = 18 + 64 + 9(r-1) \implies q - r = 2</math><br />
<math>\implies q = 20,19,18, \cdots ,2</math> and <math>r = 18,17,16, \cdots ,0</math> so there are 19 common solutions out of 31 (diff values of r) so there are <math>\boxed{31 - 19}</math> values of <math>n</math><br />
<br />
Now hopefully you've seen a pattern , if not try another case 5 with <math>a = 5</math> you'll get <math>\boxed{41 - 29}</math> values of <math>n</math><br />
<br />
Like this we get the value of "distinct" <math>n</math> by summing all the sub-values from the cases that we've solved.<br />
<br />
<math>n = 1 + 11 + (21 - 9) + (31 - 19) + (41 - 29) + \cdots + (91 - 79)</math><br />
<br />
<math>\implies n = (1 + 11 + 21 + 31 + 41 + \cdots + 91) - (0 + 0 + 9 + 19 + 29 + \cdots + 79)</math><br />
<br />
<math>\implies \boxed{n = 108}</math><br />
<br />
~MrOreoJuice<br />
<br />
== See also ==<br />
<br />
{{AIME box|year=2004|n=II|num-b=13|num-a=15}}<br />
<br />
[[Category:Intermediate Number Theory Problems]]<br />
{{MAA Notice}}</div>Mroreojuicehttps://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_14&diff=1417592004 AIME II Problems/Problem 142021-01-09T12:20:34Z<p>Mroreojuice: </p>
<hr />
<div>== Problem ==<br />
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>?<br />
<br />
== Solution 1 ==<br />
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>.<br />
<br />
Manipulating our equation, we have <math>a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 \le 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>.<br />
<br />
<br />
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>. <br />
<br />
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. <br />
<br />
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. <br />
<br />
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>. <br />
<br />
Thus, the answer is <math>112 - 4 = \boxed{108}</math>.<br />
<br />
<br />
---- <br />
<br />
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. <br />
<br />
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>.<br />
<br />
== Solution 2==<br />
To simplify, replace all the <math>7</math>’s with <math>1</math>’s. <br />
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><br />
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> <br />
<br />
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>.<br />
<br />
<br />
Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>.<br />
<br />
Note that <math>n=28</math> is possible because <math>9 \cdot 111+1 \cdot 1 = 1000</math>.<br />
<br />
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>. <br />
<br />
<br />
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. <br />
<br />
<br />
<math>\textrm{Case } 1:\text{ Sum has no } 11</math>’s<br />
<br />
It must have at least one <math>1</math>. <br />
If it has exactly one <math>1</math>, there must be nine <math>111</math>’s and <math>n = 28</math>. <br />
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.<br />
For <math>n \leq 1000</math>, at least one <math>111</math>. <br />
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>.<br />
<br />
<br />
<math>\textrm{Case } 2: \textrm{ Sum has at least one } 11</math>.<br />
<br />
Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s.<br />
Now note that <math>46</math> is possible because <math>8 \cdot 111 + 10 \cdot 11 + 2 \cdot 1 = 1000</math>.<br />
Thus all elements of <math>S</math> except <math>37</math> are possible. <br />
<br />
<br />
Thus there are <math>\boxed{108}</math> possible values for <math>n</math>.<br />
<br />
~phoenixfire<br />
<br />
== Solution 3 ==<br />
It's obvious that we cannot have any number <math>\ge 7777</math> because <math>7777 > 7000</math> so the max number that an occur is <math>777</math><br />
<br />
Let's say we have <math>a</math> 777's , <math>b</math> 77's and <math>c</math> 7's<br />
<br />
From here we get our required equation as <math>777a + 77b + 7c = 7000</math><br />
<br />
Now comes the main problem , one might think that if we find number of <math>(a,b,c)</math> then we're done , but in reality we are over-counting our number of <math>n</math>'s. This is because <math>n</math> is the total number of 7's and from our equation we'll get <math>n</math> as <math>3a + 2b + c</math> (because there are three 7's , two 7's and one 7) <br />
<br />
The reason why we're over-counting is because , say <math>a_1 , b_1 , c_1</math> be a solution of our original equation and <math>a_2 , b_2 , c_2</math> be another solution of our original equation , then there can be a possibility that <math>3a_1 + 2b_1 + c_1 = 3a_2 + 2b_2 + c_2</math> where <math>a_1 \neq a_2 , b_1 \neq b_2 , c_1 \neq c_2</math> (example : <math> 2 + 3 + 4 = 1 + 5 + 3</math> but <math>2 \neq 1 , 3 \neq 5 , 4 \neq 3</math><br />
<br />
We know that <math>0 \le a \le 9</math> , <math>0 \le b \le 90</math> , <math>0 \le c \le 1000</math><br />
The bound on <math>a</math> is easier to handle with , so lets start putting values on <math>a</math> and calculate <math>b , c , n</math> by making cases<br />
<br />
Reduced equation : <math>111a + 11b + c = 1000</math><br />
<br />
Case 1 : <math>a = 9</math><br />
<br />
We get <math>11b + c = 1 \implies b = 0 , c = 1</math> is our only solution thus only <math>\boxed{1}</math> value of <math>n</math><br />
<br />
Case 2 : <math>a = 8</math><br />
<br />
We get <math>11b + c = 112 \implies b = 0,1,2,\cdots ,10</math> and <math>c = 112 , 101 , 90,\cdots ,2</math> From here we get different <math>n</math>'s as <math>24 + 112 , 24 + 101 , 24 + 94, \cdots ,24 + 22</math> (remember <math>n = 3a + 2b + c</math> and if you have difficulty in understanding how we got <math>n = 24 + (\cdots)</math> then just put the values of <math>a,b,c</math> i am sure you will get it :) )<br />
<br />
Let's write the sequences of <math>n</math>'s in a compact form , <math>T_p = 24 + 22 + 9(p-1)</math> (This will be helpful later on)<br />
There are <math>\boxed{11}</math> values of <math>n</math><br />
<br />
Case 3 : <math>a = 7</math><br />
<br />
We get <math>11b + c = 223 \implies b=0,1,2, \cdots ,20</math> and <math>c = 223,212,201, \cdots ,3</math> From here we get different <math>n</math>'s as <math>21 + 223, 21 + 214 , 21 + 205, \cdots ,21 + 43</math><br />
<br />
Let's also write the sequences of <math>n</math>'s in a compact form , <math>T_q = 21 + 43 + 9(q-1)</math><br />
<br />
Now comes the major part , since we need to find distinct <math>n</math>'s so let's subtract the cases where we find common values , from the total number of values.<br />
<br />
To do this we need to make <math>T_p = T_q \implies p - q = 2</math> (after some calculations you'll get <math>p - q = 2</math>) . Now we know that <math>0 \le p \le 10</math> and <math>0 \le q \le 20</math> so we get <math>p</math> as <math>10,9,\cdots,2</math> and <math>q</math> as <math>8,7,\cdots,0</math> so there are 9 common solutions out of 21(diff values of <math>q</math>) total , so there are <math>\boxed{21 - 9}</math> values of <math>n</math><br />
<br />
Case 4 : <math>a = 6</math><br />
<br />
We get <math>11b + c = 334 \implies b = 0,1,2, \cdots ,30</math> and <math>c = 334,323,312, \cdots ,4</math> From here we get the different <math>n</math>'s as <math>18 + 334,18 + 325,18 + 316, \cdots ,18 + 64</math><br />
<br />
Compact form of terms is <math>T_r = 18 + 64 + 9(r-1)</math><br />
Now let's repeat the process of eliminating common solutions (one thing to notice is that we've removed common solutions of case 2 from case 3 so if we check case 4 with case 3 we'll remove common solutions from all previous cases)<br />
<br />
<math>T_q = T_r \implies 21 + 43 + 9(q-1) = 18 + 64 + 9(r-1) \implies q - r = 2</math><br />
<math>\implies q = 20,19,18, \cdots ,2</math> and <math>r = 18,17,16, \cdots ,0</math> so there are 19 common solutions out of 31 (diff values of r) so there are <math>\boxed{31 - 19}</math> values of <math>n</math><br />
<br />
Now hopefully you've seen a pattern , if not try another case 5 with <math>a = 5</math> you'll get <math>\boxed{41 - 29}</math> values of <math>n</math><br />
<br />
Like this we get the value of "distinct" <math>n</math> by summing all the sub-values from the cases that we've solved.<br />
<br />
<math>n = 1 + 11 + (21 - 9) + (31 - 19) + (41 - 29) + \cdots + (91 - 79)</math><br />
<br />
<math>\implies n = (1 + 11 + 21 + 31 + 41 + \cdots + 91) - (0 + 0 + 9 + 19 + 29 + \cdots + 79)</math><br />
<br />
<math>\implies \boxed{n = 108}</math><br />
<br />
== See also ==<br />
<br />
{{AIME box|year=2004|n=II|num-b=13|num-a=15}}<br />
<br />
[[Category:Intermediate Number Theory Problems]]<br />
{{MAA Notice}}</div>Mroreojuice