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% $?