Difference between revisions of "2009 AIME II Problems/Problem 4"
God of Math (talk | contribs) (→Another Solution) |
|||
Line 27: | Line 27: | ||
The smallest valid solution is therefore <math>c=41</math>, <math>n=\boxed{089}</math>. | The smallest valid solution is therefore <math>c=41</math>, <math>n=\boxed{089}</math>. | ||
+ | === Another Solution === | ||
− | === | + | If the first child ate <math>n=2m</math> grapes, then the maximum number of grapes eaten by all the children together is <math>2m + (2m-2) + (2m-4) + \cdots + 4 + 2 = m(m+1)</math>. Similarly, if the first child ate <math>2m-1</math> grapes, the maximum total number of grapes eaten is <math>(2m-1)+(2m-3)+\cdots+3+1 = m^2</math>. |
+ | |||
+ | For <math>m=44</math> the value <math>m(m+1)=44\cdot 45 =1980</math> is less than <math>2009</math>. Hence <math>n</math> must be at least <math>2\cdot 44+1=89</math>. For <math>n=89</math>, the maximum possible sum is <math>45^2=2025</math>. And we can easily see that <math>2009 = 2025 - 16 = 2025 - (1+3+5+7)</math>, hence <math>2009</math> grapes can indeed be achieved for <math>n=89</math> by dropping the last four children. | ||
− | + | Hence we found a solution with <math>n=89</math> and <math>45-4=41</math> kids, and we also showed that no smaller solution exists. Therefore the answer is <math>\boxed{089}</math>. | |
== See Also == | == See Also == | ||
{{AIME box|year=2009|n=II|num-b=3|num-a=5}} | {{AIME box|year=2009|n=II|num-b=3|num-a=5}} |
Revision as of 13:12, 9 April 2009
Contents
Problem
A group of children held a grape-eating contest. When the contest was over, the winner had eaten grapes, and the child in
-th place had eaten
grapes. The total number of grapes eaten in the contest was
. Find the smallest possible value of
.
Solution
Resolving the ambiguity
The problem statement is confusing, as it can be interpreted in two ways: Either as "there is a such that the child in
-th place had eaten
grapes", or "for all
, the child in
-th place had eaten
grapes".
The second meaning was apparrently the intended one. Hence we will restate the problem statement in this way:
A group of children held a grape-eating contest. When the contest was over, the following was true: There was a
such that for each
between
and
, inclusive, the child in
-th place had eaten exactly
grapes. The total number of grapes eaten in the contest was
. Find the smallest possible value of
.
Solving this problem
The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term (the number of grapes eaten by the child in
-st place), difference
, and number of terms
. We can easily compute that this sum is equal to
.
Hence we have the equation , and we are looking for a solution
, where both
and
are positive integers,
, and
is maximized. (The condition
states that even the last child had to eat a non-negative number of grapes.)
The prime factorization of is
. Hence there are
ways how to factor
into two positive terms
and
:
,
, then
is a solution.
,
, then
is a solution.
,
, then
is a solution.
- In each of the other three cases,
will obviously be less than
, hence these are not valid solutions.
The smallest valid solution is therefore ,
.
Another Solution
If the first child ate grapes, then the maximum number of grapes eaten by all the children together is
. Similarly, if the first child ate
grapes, the maximum total number of grapes eaten is
.
For the value
is less than
. Hence
must be at least
. For
, the maximum possible sum is
. And we can easily see that
, hence
grapes can indeed be achieved for
by dropping the last four children.
Hence we found a solution with and
kids, and we also showed that no smaller solution exists. Therefore the answer is
.
See Also
2009 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |