Olympiad Maths Prep

Track / Stage 5 / 198 of 400 #798 of 2000

Problem 798

AIME late
Combinatorics Difficulty 5.5 Find the answer

Example 6 From the numbers 1,2,,141,2, \cdots, 14, select a1,a2,a3a_{1}, a_{2}, a_{3} in ascending order, and a2a13,a3a23a_{2}-a_{1} \geqslant 3, a_{3}-a_{2} \geqslant 3. How many different ways of selection are there that meet the conditions?

Official solution

Solution 1: Clearly, a1+(a2a1)+(a3a2)+(14a3)=14a_{1}+\left(a_{2}-a_{1}\right)+\left(a_{3}-a_{2}\right)+\left(14-a_{3}\right)=14, where a11,a2a13,a3a23,14a30a_{1} \geqslant 1, a_{2}-a_{1} \geqslant 3, a_{3}-a_{2} \geqslant 3, 14-a_{3} \geqslant 0. Transform the equation to:
(a11)+(a2a13)+(a3a23)+(14a3)=7. \left(a_{1}-1\right)+\left(a_{2}-a_{1}-3\right)+\left(a_{3}-a_{2}-3\right)+\left(14-a_{3}\right)=7.

At this point, a11,a2a13,a3a23,14a30a_{1}-1, a_{2}-a_{1}-3, a_{3}-a_{2}-3, 14-a_{3} \geqslant 0. The above indeterminate equation has C107=C103C_{10}^{7}=C_{10}^{3} different non-negative integer solutions. Therefore, the number of different ways to meet the requirements is C103=120C_{10}^{3}=120.

Solution 2: Let S={1,2,,14},S={1,2,,10},{a1,a2,a3}S=\{1,2, \cdots, 14\}, S^{\prime}=\{1,2, \cdots, 10\}, \left\{a_{1}, a_{2}, a_{3}\right\} be a three-element subset of SS, and {a1,a2,a3}\left\{a_{1}^{\prime}, a_{2}^{\prime}, a_{3}^{\prime}\right\} be a three-element subset of SS^{\prime}, satisfying a1=a1,a2=a22,a3=a34a_{1}^{\prime}=a_{1}, a_{2}^{\prime}=a_{2}-2, a_{3}^{\prime}=a_{3}-4, i.e., establish the following correspondence:
(a1,a2,a3)(a1,a2,a3)=(a1,a22,a34). \left(a_{1}, a_{2}, a_{3}\right) \rightarrow\left(a_{1}^{\prime}, a_{2}^{\prime}, a_{3}^{\prime}\right)=\left(a_{1}, a_{2}-2, a_{3}-4\right).

Clearly, this is a one-to-one correspondence from SS to SS^{\prime}. Thus, the number of ways to choose is equal to the number of ways to choose any three different numbers from SS^{\prime}, which is C103=120C_{10}^{3}=120.

Solution 3: Construct the following model:
Take 10 identical white balls and arrange them in a row. Take 5 different black balls and divide them into 3 groups in the order of 2,2,12,2,1, then insert them into the 10 gaps between the white balls, from left to right, excluding the left end but including the right end. The number of insertion methods is C103C_{10}^{3}. Each insertion method corresponds to an ordered array, as shown in the figure:
Thus, the number of different methods is C103=120C_{10}^{3}=120.

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