CombinatoricsDifficulty 7.8National olympiad, round 2Find the answer
Given a positive integer n, let M(n) be the largest integer m such that (n−1m)>(nm−1). Evaluate n→∞limnM(n).
A number or a short expression. Spacing and $ signs are ignored.
Solution
The answer is 23+5. Note that for m>n+1, both binomial coefficients are nonzero and their ratio is (n−1m)/(nm−1)=(m−1)!(n−1)!(m−n+1)!m!n!(m−n−1)!=(m−n+1)(m−n)mn. Thus the condition (n−1m)>(nm−1) is equivalent to (m−n+1)(m−n)−mn<0. The left hand side of this last inequality is a quadratic function of m with roots α(n)=23n−1+5n2−2n+1,β(n)=23n−1−5n2−2n+1, both of which are real since 5n2−2n+1=4n2+(n−1)2>0; it follows that m satisfies the given inequality if and only if β(n)<m<α(n). (Note in particular that since α(n)−β(n)=5n2−2n+1>1, there is always some integer m between β(n) and α(n).) We conclude that M(n) is the greatest integer strictly less than α(n), and thus that α(n)−1≤M(n)<α(n). Now n→∞limnα(n)=n→∞lim23−n1+5−n2+n21=23+5 and similarly limn→∞nα(n)−1=23+5, and so by the sandwich theorem, limn→∞nM(n)=23+5.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.