Maths Olympiad Prep

Library / /17 of 20

Algebra Difficulty 6.9 National olympiad Find the answer

For integers nk0n \ge k \ge 0 we define the bibinomial coefficient ((nk))\left( \binom{n}{k} \right) by
((nk))=n!!k!!(nk)!!. \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!} .
Determine all pairs (n,k)(n,k) of integers with nk0n \ge k \ge 0 such that the corresponding bibinomial coefficient is an integer.

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

Solution

To solve the problem of determining the pairs (n,k)(n, k) such that the bibinomial coefficient ((nk))\left( \binom{n}{k} \right) is an integer, let us first express the bibinomial coefficient using the given formula:

((nk))=n!!k!!(nk)!! \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!}

where the notation n!! n!! denotes the double factorial, defined as:

- n!!=n×(n2)×(n4)××1 n!! = n \times (n-2) \times (n-4) \times \ldots \times 1 if n n is odd,
- n!!=n×(n2)×(n4)××2 n!! = n \times (n-2) \times (n-4) \times \ldots \times 2 if n n is even.

Given nk0 n \ge k \ge 0 , we need to find when this quotient is an integer. Let's analyze different scenarios:

1. **Case k=0 k = 0 :**
Here, we have:
((n0))=n!!0!!n!!=1, \left( \binom{n}{0} \right) = \frac{n!!}{0!! \cdot n!!} = 1,
which is clearly an integer.

2. **Case k=n k = n :**
Similarly, we have:
((nn))=n!!n!!0!!=1, \left( \binom{n}{n} \right) = \frac{n!!}{n!! \cdot 0!!} = 1,
which is also an integer.

3. **Case both n n and k k are even:**
Let n=2m n = 2m and k=2l k = 2l where m m and l l are integers. The expression becomes:
((nk))=(2m)!!(2l)!!(2m2l)!!. \left( \binom{n}{k} \right) = \frac{(2m)!!}{(2l)!!(2m-2l)!!}.
Each of these double factorials is a product of even numbers. Consequently, the quotient ((nk))\left( \binom{n}{k} \right) is an integer since every factor in the denominator can be paired with the factors in the numerator.

4. **Special case (n, k) = (2, 1):** Here, calculate directly: \[ \left( \binom{2}{1} \right) = \frac{2!!}{1!! \cdot 1!!} = \frac{2}{1} = 2, \] which is an integer. Thus, the pairs \((n, k) for which the bibinomial coefficient is an integer are:
- Such that k=0 k = 0 or k=n k = n ,
- Both n n and k k are even, or
- (n,k)=(2,1) (n, k) = (2, 1) .

Therefore, the complete set of pairs is:
(n,k) such that k=0 or k=n, or both n and k are even,  or  (n, k) = (2, 1). \boxed{(n, k) \text{ such that } k = 0 \text{ or } k = n, \text{ or both } n \text{ and } k \text{ are even, \text{ or } (n, k) = (2, 1)}.}

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.