2004 AIME II Problems/Problem 14
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.