Maths Olympiad Prep

Library / /142 of 397

Combinatorics Difficulty 5.5 AIME, harder Prove it Taiwan

Determine all integers m2m \ge 2 such that for all n,m3nm2n, \frac{m}{3} \le n \le \frac{m}{2}, nn divides the binomial coefficient (nm2n)\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, 1np21 \le n \le \frac{p}{2}, nn divides the binomial coefficient (np2n)\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
(p2n)(np2n)=n(n1p2n1). (p-2n) \cdot \binom{n}{p-2n} = n \cdot \binom{n-1}{p-2n-1}.
Since p2np \ge 2n and pp is odd, every factor in the above expression is nonzero. If d=gcd(p2n,n)d = \gcd(p-2n, n), then dd divides pp, but dn<pd \le n < p, so d=1d=1. This shows that p2np-2n and nn are coprime. Therefore nn divides the binomial coefficient (np2n)\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 m3nm2\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 k1k \ge 1 such that m=p(2k+1)m = p(2k+1). Take n=pkn = pk, then from k1k \ge 1 we get m3nm2\frac{m}{3} \le n \le \frac{m}{2}. However
1n(nm2n)=1pk(pkp)=(pk1)(pk2)(pk(p1))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,000 problems in a working order, from AMC 10 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.