Maths Olympiad Prep

Library / /23 of 144

Combinatorics Difficulty 7.7 National olympiad, round 2 Find the answer

Determine all integers m2m \geq 2 such that every nn with m3nm2\frac{m}{3} \leq n \leq \frac{m}{2} divides the binomial coefficient (nm2n)\binom{n}{m-2n}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are tasked with determining all integers m2 m \ge 2 such that for every integer n n satisfying m3nm2 \frac{m}{3} \leq n \leq \frac{m}{2} , the binomial coefficient (nm2n)\binom{n}{m-2n} is divisible by n n .

To approach this problem, let's first consider the conditions on n n . For a given m m , the range for n n is [m3,m2]\left[\frac{m}{3}, \frac{m}{2}\right]. Let m2n=k m - 2n = k , so we need to ensure that the binomial coefficient (nk)\binom{n}{k} is divisible by n n .

### Understanding the Binomial Coefficient

The binomial coefficient (nk)\binom{n}{k} can be expressed as:
(nk)=n(n1)(n2)(nk+1)k! \binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}

For this to be divisible by n n , the numerator must be divisible by n n , which implies that n n divides at least one of the terms in the product n(n1)(n2)(nk+1) n(n-1)(n-2)\cdots(n-k+1) .

### Analyzing when (nk)\binom{n}{k} is Divisible by n n

For the divisibility condition to be true for every n n in the specified range, one key requirement is to examine when n n appears as a factor in (nk)\binom{n}{k}. It often occurs that this condition is satisfied when n n is a prime number because in such cases, the factorial division in the binomial coefficient won't introduce a common factor across the range of [m3,m2] \left[\frac{m}{3}, \frac{m}{2}\right] .

Therefore, if m m itself is structured such that every n n in the range can be non-composite, particularly being a prime, it inherently satisfies the condition that n(nm2n) n \mid \binom{n}{m-2n}.

### Conclusion

Given this analysis, we can conclude that m m must be such that every applicable n n is inherently prime or acts divisibly in the factorial representation—specifically when m m is a prime number, this condition can be satisfied efficiently.

Thus, the required set of integers m m that ensures the condition is fulfilled for every n n in the specified range are all prime numbers. Therefore, the answer is:
all prime numbers \boxed{\text{all prime numbers}}

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.