Monday, September 4, 2006

Throw! Topic: NT/Probability. Level: AIME.

Problem: (2004 Putnam - A1) Basketball star Shanille Oâ€™Kealâ€™s team statistician keeps track of the number, $S(N)$, of successful free throws she has made in her first N attempts of the season. Early in the season, $S(N)$ was less than $80%$ of $N$, but by the end of the season, $S(N)$ was more than $80%$ of $N$. Was there necessarily a moment in between when $S(N)$ was exactly $80%$ of $N$?

Solution: We claim that the answer is yes and we will prove it by contradiction. Suppose that there isn't such a moment. Then there is some $k$ such that $S(k) < 0.8k$ and $S(k+1) > 0.8(k+1)$. Clearly, the $(k+1)$th throw must have been in for the ratio to increase. So $S(k+1) = S(k)+1$. Let $a = S(k)$. The above inequalities become

$a < 0.8k$ and $a+1 > 0.8k+0.8$,

which simplify to

$0.8k-0.2 < a < 0.8k$.

Multiply this by $5$ to get

$4k-1 < 5a < 4k$.

But since $5a$ is an integer and there are no integers between $4k-1$ and $4k$, we have a contradiction. Hence the answer is yes, as claimed. QED.

--------------------

Comment: A tricky problem; intuitively it seems like there must exist some case for which this isn't true, but after searching a bit for a counterexample, I pretty much assumed it was true and began trying to prove it. This wasn't hard as we reached a contradiction pretty easily.

--------------------

Practice Problem: For what other numbers does the above problem hold instead of $80%$?