Maths Olympiad Prep

Track / Stage 7 / 190 of 300 #1590 of 1964

Problem 1590

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.3 Find the answer

Compute the number of ordered quadruples (a,b,c,d)(a,b,c,d) of distinct positive integers such that ((ab)(cd))=21\displaystyle \binom{\binom{a}{b}}{\binom{c}{d}}=21.

Proposed by Luke Robitaille

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

To solve the problem, we need to find the number of ordered quadruples (a,b,c,d)(a, b, c, d) of distinct positive integers such that ((ab)(cd))=21\binom{\binom{a}{b}}{\binom{c}{d}} = 21.

First, we note that 2121 can be expressed as a binomial coefficient in the following ways:
21=(72)=(75)=(211)=(2120) 21 = \binom{7}{2} = \binom{7}{5} = \binom{21}{1} = \binom{21}{20}

We will consider each case separately and count the number of valid quadruples (a,b,c,d)(a, b, c, d) for each case.

1. **Case 1: ((ab)(cd))=(72)\binom{\binom{a}{b}}{\binom{c}{d}} = \binom{7}{2}**
- (ab)=7\binom{a}{b} = 7
- (cd)=2\binom{c}{d} = 2

To make (ab)=7\binom{a}{b} = 7, we have:
(71)=7and(76)=7 \binom{7}{1} = 7 \quad \text{and} \quad \binom{7}{6} = 7

To make (cd)=2\binom{c}{d} = 2, we have:
(21)=2 \binom{2}{1} = 2

Therefore, the possible quadruples are:
(7,1,2,1)and(7,6,2,1) (7, 1, 2, 1) \quad \text{and} \quad (7, 6, 2, 1)

However, the numbers must be distinct, so (7,1,2,1)(7, 1, 2, 1) is not valid. Thus, there is only 11 valid solution:
(7,6,2,1) (7, 6, 2, 1)

2. **Case 2: ((ab)(cd))=(75)\binom{\binom{a}{b}}{\binom{c}{d}} = \binom{7}{5}**
- (ab)=7\binom{a}{b} = 7
- (cd)=5\binom{c}{d} = 5

To make (ab)=7\binom{a}{b} = 7, we have:
(71)=7and(76)=7 \binom{7}{1} = 7 \quad \text{and} \quad \binom{7}{6} = 7

To make (cd)=5\binom{c}{d} = 5, we have:
(51)=5and(54)=5 \binom{5}{1} = 5 \quad \text{and} \quad \binom{5}{4} = 5

Therefore, the possible quadruples are:
(7,1,5,1),(7,1,5,4),(7,6,5,1),(7,6,5,4) (7, 1, 5, 1), (7, 1, 5, 4), (7, 6, 5, 1), (7, 6, 5, 4)

However, the numbers must be distinct, so (7,1,5,1)(7, 1, 5, 1) is not valid. Thus, there are 33 valid solutions:
(7,1,5,4),(7,6,5,1),(7,6,5,4) (7, 1, 5, 4), (7, 6, 5, 1), (7, 6, 5, 4)

3. **Case 3: ((ab)(cd))=(211)\binom{\binom{a}{b}}{\binom{c}{d}} = \binom{21}{1}**
- (ab)=21\binom{a}{b} = 21
- (cd)=1\binom{c}{d} = 1

There are no ways to make (cd)=1\binom{c}{d} = 1 with distinct positive integers, so there are no valid solutions for this case.

4. **Case 4: ((ab)(cd))=(2120)\binom{\binom{a}{b}}{\binom{c}{d}} = \binom{21}{20}**
- (ab)=21\binom{a}{b} = 21
- (cd)=20\binom{c}{d} = 20

To make (ab)=21\binom{a}{b} = 21, we have:
(72)=21and(75)=21and(211)=21and(2120)=21 \binom{7}{2} = 21 \quad \text{and} \quad \binom{7}{5} = 21 \quad \text{and} \quad \binom{21}{1} = 21 \quad \text{and} \quad \binom{21}{20} = 21

To make (cd)=20\binom{c}{d} = 20, we have:
(201)=20and(2019)=20and(63)=20 \binom{20}{1} = 20 \quad \text{and} \quad \binom{20}{19} = 20 \quad \text{and} \quad \binom{6}{3} = 20

Therefore, the possible quadruples are:
(21,1,20,1),(21,1,20,19),(21,1,6,3),(21,20,20,1),(21,20,20,19),(21,20,6,3),(7,2,20,1),(7,2,20,19),(7,2,6,3),(7,5,20,1),(7,5,20,19),(7,5,6,3) (21, 1, 20, 1), (21, 1, 20, 19), (21, 1, 6, 3), (21, 20, 20, 1), (21, 20, 20, 19), (21, 20, 6, 3), (7, 2, 20, 1), (7, 2, 20, 19), (7, 2, 6, 3), (7, 5, 20, 1), (7, 5, 20, 19), (7, 5, 6, 3)

However, the numbers must be distinct, so (21,1,20,1)(21, 1, 20, 1), (21,20,20,1)(21, 20, 20, 1), and (21,20,20,19)(21, 20, 20, 19) are not valid. Thus, there are 99 valid solutions:
(21,1,20,19),(21,1,6,3),(21,20,6,3),(7,2,20,1),(7,2,20,19),(7,2,6,3),(7,5,20,1),(7,5,20,19),(7,5,6,3) (21, 1, 20, 19), (21, 1, 6, 3), (21, 20, 6, 3), (7, 2, 20, 1), (7, 2, 20, 19), (7, 2, 6, 3), (7, 5, 20, 1), (7, 5, 20, 19), (7, 5, 6, 3)

Adding up all the valid solutions from each case, we get:
1+3+0+9=13 1 + 3 + 0 + 9 = 13

The final answer is 13\boxed{13}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.