Difference between revisions of "2009 AIME II Problems/Problem 4"
(→Another Solution) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 16: | Line 16: | ||
The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term <math>n</math> (the number of grapes eaten by the child in <math>1</math>-st place), difference <math>d=-2</math>, and number of terms <math>c</math>. We can easily compute that this sum is equal to <math>c(n-c+1)</math>. | The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term <math>n</math> (the number of grapes eaten by the child in <math>1</math>-st place), difference <math>d=-2</math>, and number of terms <math>c</math>. We can easily compute that this sum is equal to <math>c(n-c+1)</math>. | ||
− | Hence we have the equation <math>2009=c(n-c+1)</math>, and we are looking for a solution <math>(n,c)</math>, where both <math>n</math> and <math>c</math> are positive integers, <math>n\geq 2(c-1)</math>, and <math>n</math> is | + | Hence we have the equation <math>2009=c(n-c+1)</math>, and we are looking for a solution <math>(n,c)</math>, where both <math>n</math> and <math>c</math> are positive integers, <math>n\geq 2(c-1)</math>, and <math>n</math> is minimized. (The condition <math>n\geq 2(c-1)</math> states that even the last child had to eat a non-negative number of grapes.) |
The prime factorization of <math>2009</math> is <math>2009=7^2 \cdot 41</math>. Hence there are <math>6</math> ways how to factor <math>2009</math> into two positive terms <math>c</math> and <math>n-c+1</math>: | The prime factorization of <math>2009</math> is <math>2009=7^2 \cdot 41</math>. Hence there are <math>6</math> ways how to factor <math>2009</math> into two positive terms <math>c</math> and <math>n-c+1</math>: | ||
Line 34: | Line 34: | ||
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>. | 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>. | ||
+ | |||
+ | === Solution 3 (similar to solution 1) === | ||
+ | If the winner ate n grapes, then 2nd place ate <math>n+2-4=n-2</math> grapes, 3rd place ate <math>n+2-6=n-4</math> grapes, 4th place ate <math>n-6</math> grapes, and so on. Our sum can be written as <math>n+(n-2)+(n-4)+(n-6)\dots</math>. If there are x places, we can express this sum as <math>(x+1)n-x(x+1)</math>, as there are <math>(x+1)</math> occurrences of n, and <math>(2+4+6+\dots)</math> is equal to <math>x(x+1)</math>. This can be factored as <math>(x+1)(n-x)=2009</math>. Our factor pairs are (1,2009), (7,287), and (41,49). To minimize n we take (41,49). If <math>x+1=41</math>, then <math>x=40</math> and <math>n=40+49=\boxed{089}</math>. (Note we would have come upon the same result had we used <math>x+1=49</math>.) | ||
+ | ~MC413551 | ||
== 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}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 18:40, 12 January 2024
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
.
Solution 1
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 minimized. (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 ,
.
Solution 2
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
.
Solution 3 (similar to solution 1)
If the winner ate n grapes, then 2nd place ate grapes, 3rd place ate
grapes, 4th place ate
grapes, and so on. Our sum can be written as
. If there are x places, we can express this sum as
, as there are
occurrences of n, and
is equal to
. This can be factored as
. Our factor pairs are (1,2009), (7,287), and (41,49). To minimize n we take (41,49). If
, then
and
. (Note we would have come upon the same result had we used
.)
~MC413551
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.