Difference between revisions of "2004 AIME II Problems/Problem 14"
Phoenixfire (talk | contribs) (→Solution 2) |
m (→Solution 2) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 5: | Line 5: | ||
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>. | ||
− | Manipulating our equation, we have <math>a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 | + | 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>. |
Line 28: | Line 28: | ||
To simplify, replace all the <math>7</math>’s with <math>1</math>’s. | 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> | 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 < | + | Also, <math>n \leq 1000</math>. There are <math>\big\lfloor \tfrac{1000}{9} \big\rfloor + 1 = 112</math> positive integers that satisfy both conditions i.e. <math>\{1, 10, 19, 28, 37, 46, . . . , 1000\}.</math> |
− | |||
− | |||
+ | For <math>n = 1, 10, 19</math>, the greatest sum that is less than or equal to <math>1000</math> is <cmath>6 \cdot 111 + 1 = 667 \implies 112-3 = 109.</cmath> | ||
Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>. | Thus <math>n \geq 28</math> and let <math>S = \{28, 37, 46, . . . , 1000\}</math>. | ||
Line 42: | Line 41: | ||
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. | 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>\textbf{Case 1:}</math> Sum has no <math>11</math>'s | |
− | <math>\ | ||
It must have at least one <math>1</math>. | It must have at least one <math>1</math>. | ||
Line 51: | Line 49: | ||
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>. | 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>\textbf{Case 2:}</math> Sum has at least one <math>11</math>. | |
− | <math>\ | ||
Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s. | Replace an <math>11</math> with <math>1 + 1</math>, and include nine new <math>1</math>’s as <math>+1</math>’s. | ||
Line 58: | Line 55: | ||
Thus all elements of <math>S</math> except <math>37</math> are possible. | 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 | ||
+ | |||
+ | == Solution 3 == | ||
+ | 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> | ||
+ | |||
+ | Let's say we have <math>a</math> 777's , <math>b</math> 77's and <math>c</math> 7's | ||
+ | |||
+ | From here we get our required equation as <math>777a + 77b + 7c = 7000</math> | ||
+ | |||
+ | 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) | ||
+ | |||
+ | 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> | ||
+ | |||
+ | We know that <math>0 \le a \le 9</math> , <math>0 \le b \le 90</math> , <math>0 \le c \le 1000</math> | ||
+ | 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 | ||
+ | |||
+ | Reduced equation : <math>111a + 11b + c = 1000</math> | ||
+ | |||
+ | Case 1 : <math>a = 9</math> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Case 2 : <math>a = 8</math> | ||
+ | |||
+ | 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 + 103 , 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 :) ) | ||
+ | |||
+ | 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) | ||
+ | There are <math>\boxed{11}</math> values of <math>n</math> | ||
+ | |||
+ | Case 3 : <math>a = 7</math> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Let's also write the sequences of <math>n</math>'s in a compact form , <math>T_q = 21 + 43 + 9(q-1)</math> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Case 4 : <math>a = 6</math> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Compact form of terms is <math>T_r = 18 + 64 + 9(r-1)</math> | ||
+ | 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}) | ||
+ | |||
+ | <math>T_q = T_r \implies 21 + 43 + 9(q-1) = 18 + 64 + 9(r-1) \implies q - r = 2</math> | ||
+ | <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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Like this we get the value of "distinct" <math>n</math> by summing all the sub-values from the cases that we've solved. | ||
+ | |||
+ | <math>n = 1 + 11 + (21 - 9) + (31 - 19) + (41 - 29) + \cdots + (91 - 79)</math> | ||
+ | |||
+ | <math>\implies n = (1 + 11 + 21 + 31 + 41 + \cdots + 91) - (0 + 0 + 9 + 19 + 29 + \cdots + 79)</math> | ||
+ | |||
+ | <math>\implies \boxed{n = 108}</math> | ||
− | + | ~MrOreoJuice | |
== 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]] | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 12:57, 18 July 2024
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
positive integers that satisfy both conditions i.e.
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.
Sum has no
'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
.
Sum has at least one
.
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
.
~phoenixfire
Solution 3
It's obvious that we cannot have any number because
so the max number that an occur is
Let's say we have 777's ,
77's and
7's
From here we get our required equation as
Now comes the main problem , one might think that if we find number of then we're done , but in reality we are over-counting our number of
's. This is because
is the total number of 7's and from our equation we'll get
as
(because there are three 7's , two 7's and one 7)
The reason why we're over-counting is because , say be a solution of our original equation and
be another solution of our original equation , then there can be a possibility that
where
(example :
but
We know that ,
,
The bound on
is easier to handle with , so lets start putting values on
and calculate
by making cases
Reduced equation :
Case 1 :
We get is our only solution thus only
value of
Case 2 :
We get and
From here we get different
's as
(remember
and if you have difficulty in understanding how we got
then just put the values of
i am sure you will get it :) )
Let's write the sequences of 's in a compact form ,
(This will be helpful later on)
There are
values of
Case 3 :
We get and
From here we get different
's as
Let's also write the sequences of 's in a compact form ,
Now comes the major part , since we need to find distinct 's so let's subtract the cases where we find common values , from the total number of values.
To do this we need to make (after some calculations you'll get
) . Now we know that
and
so we get
as
and
as
so there are 9 common solutions out of 21(diff values of
) total , so there are
values of
Case 4 :
We get and
From here we get the different
's as
Compact form of terms is
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})
and
so there are 19 common solutions out of 31 (diff values of r) so there are
values of
Now hopefully you've seen a pattern , if not try another case 5 with you'll get
values of
Like this we get the value of "distinct" by summing all the sub-values from the cases that we've solved.
~MrOreoJuice
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.