Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /130 of 359

Taiwan IMO Selection Camp

Combinatorics Difficulty 5.5 AIME, harder Prove it Taiwan

Determine all integers m≥2m \ge 2 such that for all n,m3≤n≤m2n, \frac{m}{3} \le n \le \frac{m}{2}, nn divides the binomial coefficient (nm−2n)\binom{n}{m-2n}.

Solution

Solution: The integers satisfying the problem's condition are all primes.

First we check that all primes satisfy the condition of the problem. That is, if pp is a prime, then for all nn, 1≤n≤p21 \le n \le \frac{p}{2}, nn divides the binomial coefficient (np−2n)\binom{n}{p-2n}. When p=2p=2 this holds. For an odd prime pp, take n∈[1,p2]n \in [1, \frac{p}{2}] and consider
(p−2n)⋅(np−2n)=n⋅(n−1p−2n−1). (p-2n) \cdot \binom{n}{p-2n} = n \cdot \binom{n-1}{p-2n-1}.
Since p≥2np \ge 2n and pp is odd, every factor in the above expression is nonzero. If d=gcd⁡(p−2n,n)d = \gcd(p-2n, n), then dd divides pp, but d≤n<pd \le n < p, so d=1d=1. This shows that p−2np-2n and nn are coprime. Therefore nn divides the binomial coefficient (np−2n)\binom{n}{p-2n}.

Next, we prove that no composite number mm satisfies the property of the problem. Consider two cases:

(1) If m=2k,k>1m = 2k, k > 1, take n=kn = k. Then m3≤n≤m2\frac{m}{3} \le n \le \frac{m}{2}, but (k0)=1\binom{k}{0} = 1 cannot be divided by kk.

(2) If mm is odd, then there exists an odd prime pp and an integer k≥1k \ge 1 such that m=p(2k+1)m = p(2k+1). Take n=pkn = pk, then from k≥1k \ge 1 we get m3≤n≤m2\frac{m}{3} \le n \le \frac{m}{2}. However
1n(nm−2n)=1pk(pkp)=(pk−1)(pk−2)⋯(pk−(p−1))p! \frac{1}{n} \binom{n}{m-2n} = \frac{1}{pk} \binom{pk}{p} = \frac{(pk-1)(pk-2)\cdots(pk-(p-1))}{p!}
is not an integer, because pp divides the denominator but does not divide the numerator.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from the original; metadata (topic, difficulty) added by this project.