AIME 1993 · 第 7 题

Solution 1 (Permutation)

There is a total of $P(1000,6)$ possible ordered $6$-tuples $(a_1,a_2,a_3,b_1,b_2,b_3).$

There are $C(1000,6)$ possible sets $\{a_1,a_2,a_3,b_1,b_2,b_3\}.$ We have five valid cases for the increasing order of these six elements:

1. $aaabbb$
2. $aababb$
3. $aabbab$
4. $abaabb$
5. $ababab$

Note that the $a$'s are different from each other, as there are $3!=6$ ways to permute them as $a_1,a_2,$ and $a_3.$ Similarly, the $b$'s are different from each other, as there are $3!=6$ ways to permute them as $b_1,b_2,$ and $b_3.$

So, there is a total of $C(1000,6)\cdot5\cdot6^2$ valid ordered $6$-tuples. The requested probability is

$$p=\frac{C(1000,6)\cdot5\cdot6^2}{P(1000,6)}=\frac{C(1000,6)\cdot5\cdot6^2}{C(1000,6)\cdot6!}=\frac14,$$ from which the answer is $1+4=\boxed{005}.$

~MRENTHUSIASM

Solution 2 (Combination)

Call the six numbers selected $x_1 > x_2 > x_3 > x_4 > x_5 > x_6$. Clearly, $x_1$ must be a dimension of the box, and $x_6$ must be a dimension of the brick.

• If $x_2$ is a dimension of the box, then any of the other three remaining dimensions will work as a dimension of the box. That gives us $3$ possibilities.
• If $x_2$ is not a dimension of the box but $x_3$ is, then both remaining dimensions will work as a dimension of the box. That gives us $2$ possibilities.
• If $x_4$ is a dimension of the box but $x_2,x_3$ aren’t, there are no possibilities (same for $x_5$).

The total number of arrangements is ${6\choose3} = 20$; therefore, $p = \frac{3 + 2}{20} = \frac{1}{4}$, and the answer is $1 + 4 = \boxed{005}$.

Note that the $1000$ in the problem, is not used, and is cleverly bypassed in the solution, because we can call our six numbers $x_1,x_2,x_3,x_4,x_5,x_6$ whether they may be $1,2,3,4,5,6$ in some order or $999,5,3,998,997,891$ in some order.

Solution 3 (Hook Length Formula)

Like Solution 2, call the six numbers selected $x_1 > x_2 > x_3 > x_4 > x_5 > x_6$. Using the Hook Length Formula, the number of valid configuration is $\frac{6!}{4\cdot3\cdot2\cdot3\cdot2}=5$. We proceed as Solution 2 does.

Solution 4 (Catalan Numbers)

As in Solutions 2 and 3, we let $x_1>x_2>x_3>x_4>x_5>x_6$ where each $x_i$ is a number selected. It is clear that when choosing whether each number must be in the set with larger dimensions (the box) or the set with smaller dimensions (the brick) there must always be at least as many numbers in the former set as the latter. We realize that this resembles Catalan numbers, where the indices of the numbers in the first set can be replaced with rising sections of a mountain, and the other indices representing falling sections of a mountain. The formula for the $n$th Catalan number (where $n$ is the number of pairs of rising and falling sections) is

$$\frac{\binom{2n}{n}}{n+1}$$ Thus, there are $\frac{\binom{6}{3}}{4}$ ways to pick which of $x_1,x_2,x_3,x_4,x_5,$ and $x_6$ are the dimensions of the box, and which are the dimensions of the brick, such that the condition is fulfilled. There are $\binom{6}{3}$ total ways to choose which numbers make up the brick and box, so the probability of the condition being fulfilled is $\frac{\binom{6}{3}/4}{\binom{6}{3}}=\frac14\Longrightarrow \boxed{005}$.

Solution 5 (1-1 Correspondence and Constructive Counting)

In order (after rotation, of course), for the brick to fit in the box, we must have $a_1 < b_1$, $a_2 < b_2$, and $a_3 < b_3$. Also, to correct for the rotation, we must have that $a_1 < a_2 < a_3$, and $b_1 < b_2 < b_3$. Due to the fact that all $a_1$, $a_2$, $a_3$, $b_1$, $b_2$, and $b_3$ are distinct, and also the fact that each $a_i$ and $b_i$: $1 \le i \le 3$ are a set of six distinct elements from the set $\{1,2,3,\dots,100\}$, it suffices to just find the probability that $a_1 < b_1$, $a_2 < b_2$, and $a_3 < b_3$ from the set $\{1,2,3,4,5,6\}$. If you aren't convinced, $a_1$, $a_2$, and $a_3$ are independently chosen from $\{1,2,3,\dots,100\}$. Once chosen, $b_1$, $b_2$, and $b_3$ are chosen from the remaining 997 elements. Thus, any subset of six elements can satisfy the criteria of the dimensions of the brick and box. The simplest of these subsets is $\{1,2,3,4,5,6\}$. Thus, there is a 1-1 correspondence (bijection).

Then, we know that $a_1 = 1$ and $b_3 = 6$ (This is quite easy to see. Notice that $a_1$ is the smallest possible number and $b_3$ is the largest due to the simplicity after rotation of $a_1 < b_1$, $a_2 < b_2$, and $a_3 < b_3$, $a_1 < a_2 < a_3$, and $b_1 < b_2 < b_3$). Thus, we must evaluate the possible cases for $a_2$, $a_3$, $b_1$, and $b_2$.

Case 1: $a_2 = 2$. Then, there are three cases for $a_3$ (either 3, 4, or 5), in which $b_1$ and $b_2$ are uniquely determined. (if $a_3 = 3$, then $b_1 = 4$ and $b_2 = 5$; if $a_3 = 4$, $b_1 = 3$ and $b_2 = 5$; and if $a_3 = 5$, $b_1 = 3$ and $b_2 = 4$).

Case 2: $a_2 = 3$. Then, there are two cases for $a_3$ (4 or 5). (if $a_3 = 4$, then $b_2 = 5$ and $b_1 = 2$; and if $a_3 = 5$, then $b_2 = 4$ and $b_1 = 2$).

Case 3: $a_2 = 4$. At this case, $a_3$ must be 5. But then, the inequality $a_2 < b_2$ cannot be satisfied. This case is not allowed.

Case 4: $a_2 = 5$. At this case, $a_3 < a_2$. But, we said that $a_2 < a_3$! Thus, there lies a contradiction, and this case is not allowed.

Thus, there are $3 + 2 = 5$ total cases that satisfy the conditions.

Because we don't care about the order we choose the numbers to give to $a_1$, $a_2$, and $a_3$ (as we could just permute them such that $a_1 < a_2 < a_3$), and the same for $b_1$, $b_2$, and $b_3$, there are a total of $\binom{6}{3} \cdot \binom{3}{3} = 20 \cdot 1 = 20$ ways to distribute the elements of the set to each $a_1$, $a_2$, $a_3$, $b_1$, $b_2$, $b_3$. Thus, our probability is $\frac{5}{20} = 1/4$, in which our answer is $1+4 = \boxed{005}$.

~Pinotation