Difference between revisions of "2009 AIME II Problems/Problem 4"

(Solution)
(Another Solution)
Line 30: Line 30:
 
=== Another Solution ===
 
=== Another Solution ===
  
Let us go in order of place, from <math>1</math> to <math>k</math>. The first kid eats <math>n</math> grapes, the second kid eats <math>n - 2</math> grapes, and so on. These must sum up to 2009. Hence <math>n(k + 1) - 2(k)(k + 1)/2 = 2009</math>, or <math>n(k + 1) - k(k + 1) = 2009</math>. Factoring, we get <math>(n - k)(k + 1) = 2009</math>. We are only looking for integer solutions, so we can prime factorize 2009 and look for factor pairs. <math>2009 = (7)*(7)*(41)</math>. So <math>(n - k) = 2009</math> and <math>k + 1 = 1</math>, <math>(n - k) = 49</math> and <math>(k + 1) = 41</math>, or <math>(n - k) = 287 and </math>(k + 1) = 7<math>. The solution sets (in the form (n , k), respectively, are </math>(2009, 0)<math>, </math>(293, 6)<math>, and </math>(89, 48)<math>. The pair with the smallest n value has </math>n=\boxed{089}$.
+
Let us go in order of place, from <math>1</math> to <math>k</math>. The first kid eats <math>n</math> grapes, the second kid eats <math>n - 2</math> grapes, and so on. These must sum up to 2009. Hence <math>n(k + 1) - 2(k)(k + 1)/2 = 2009</math>, or <math>n(k + 1) - k(k + 1) = 2009</math>. Factoring, we get <math>(n - k)(k + 1) = 2009</math>. We are only looking for integer solutions, so we can prime factorize 2009 and look for factor pairs. <math>2009 = (7)*(7)*(41)</math>. So <math>(n - k) = 2009</math> and <math>k + 1 = 1</math>, <math>(n - k) = 49</math> and <math>(k + 1) = 41</math>, or <math>(n - k) = 287</math> and <math>(k + 1) = 7</math>. The solution sets (in the form (n , k), respectively, are <math>(2009, 0)</math>, <math>(293, 6)</math>, and <math>(89, 48)</math>. The pair with the smallest n value has <math>n=\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 20:14, 8 April 2009

Problem

A group of children held a grape-eating contest. When the contest was over, the winner had eaten $n$ grapes, and the child in $k$-th place had eaten $n+2-2k$ grapes. The total number of grapes eaten in the contest was $2009$. Find the smallest possible value of $n$.

Solution

Resolving the ambiguity

The problem statement is confusing, as it can be interpreted in two ways: Either as "there is a $k>1$ such that the child in $k$-th place had eaten $n+2-2k$ grapes", or "for all $k$, the child in $k$-th place had eaten $n+2-2k$ grapes".

The second meaning was apparrently the intended one. Hence we will restate the problem statement in this way:

A group of $c$ children held a grape-eating contest. When the contest was over, the following was true: There was a $n$ such that for each $k$ between $1$ and $c$, inclusive, the child in $k$-th place had eaten exactly $n+2-2k$ grapes. The total number of grapes eaten in the contest was $2009$. Find the smallest possible value of $n$.

Solving this problem

The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term $n$ (the number of grapes eaten by the child in $1$-st place), difference $d=-2$, and number of terms $c$. We can easily compute that this sum is equal to $c(n-c+1)$.

Hence we have the equation $2009=c(n-c+1)$, and we are looking for a solution $(n,c)$, where both $n$ and $c$ are positive integers, $n\geq 2(c-1)$, and $n$ is maximized. (The condition $n\geq 2(c-1)$ states that even the last child had to eat a non-negative number of grapes.)

The prime factorization of $2009$ is $2009=7^2 \cdot 41$. Hence there are $6$ ways how to factor $2009$ into two positive terms $c$ and $n-c+1$:

  • $c=1$, $n-c+1=2009$, then $n=2009$ is a solution.
  • $c=7$, $n-c+1=7\cdot 41=287$, then $n=293$ is a solution.
  • $c=41$, $n-c+1=7\cdot 7=49$, then $n=89$ is a solution.
  • In each of the other three cases, $n$ will obviously be less than $2(c-1)$, hence these are not valid solutions.

The smallest valid solution is therefore $c=41$, $n=\boxed{089}$.


Another Solution

Let us go in order of place, from $1$ to $k$. The first kid eats $n$ grapes, the second kid eats $n - 2$ grapes, and so on. These must sum up to 2009. Hence $n(k + 1) - 2(k)(k + 1)/2 = 2009$, or $n(k + 1) - k(k + 1) = 2009$. Factoring, we get $(n - k)(k + 1) = 2009$. We are only looking for integer solutions, so we can prime factorize 2009 and look for factor pairs. $2009 = (7)*(7)*(41)$. So $(n - k) = 2009$ and $k + 1 = 1$, $(n - k) = 49$ and $(k + 1) = 41$, or $(n - k) = 287$ and $(k + 1) = 7$. The solution sets (in the form (n , k), respectively, are $(2009, 0)$, $(293, 6)$, and $(89, 48)$. The pair with the smallest n value has $n=\boxed{089}$.

See Also

2009 AIME II (ProblemsAnswer KeyResources)
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
Invalid username
Login to AoPS