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% $?
Practice: 1 and .... 0.2 or 20%
ReplyDeletemaybe...
There are more than those (I'm not sure yours work either)... at least prove it works for all n/(n+1).
ReplyDelete