Question

Three numbers, $a_1,$ $a_2,$ $a_3,$ are drawn randomly and without replacement from the set $\{1,2,3,\ldots,1000\}.$ Three other numbers, $b_1,$ $b_2,$ $b_3,$ are then drawn randomly and without replacement from the remaining set of $997$ numbers. Let $p$ be the probability that, after a suitable rotation, a brick of dimensions $a_1\times a_2\times a_3$ can be enclosed in a box of dimensions $b_1\times b_2\times b_3,$ with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?

Answer

Answer: 5

Concepts:basic probability Catalan Number sampling without replacement

Difficulty rating: 2410

Small Hint:

Condition on the six selected values and record only whether each belongs to the brick or the box in increasing order

Big Hint:

The brick fits exactly when every prefix of this six-letter word contains at least as many $a$ ’s as $b$ ’s

Solution:

After the six distinct values are fixed and sorted, each of the $\binom63=20$ assignments of three values to the brick is equally likely. The sorted brick dimensions fit the sorted box dimensions exactly when, in every prefix of the resulting word of three $a$ ’s and three $b$ ’s, the number of $a$ ’s is at least the number of $b$ ’s. There are $C_3=5$ such words. Thus $p=\frac{5}{20}=\frac{1}{4},$ and the requested sum is $1+4=5.$

1993 AIME Problem 7

Answer: 5

Difficulty rating: 2410

Small Hint:

Big Hint:

Solution:

Problem 7 in Other Years