7
$\begingroup$

From the set {1, 2, 3, ... 999}, 6 distinct numbers are chosen. These are divided into two groups $a_1,a_2,a_3$ and $b_1,b_2,b_3$. Find the probability that a brick made from the dimensions of group $a$ fits into a box made from the dimensions of $b$. Assume that the brick can be rotated in a suitable manner to be made to fit inside the box

I am able to comprehend this question and what it asks. However, I don't have a strategy in place to solve this question. The solution provided has the following to say:

without loss of generality, we can say that out of the 20 possible cases, 5 are suitable. Therefore, the probability is $\frac 1 4$.

What are the twenty possible cases here? How can we set conditions on $a$ and $b$ such that we can obtain these cases? The ability to rotate the brick before placing in the box has confused me. Any help would be appreciated!

$\endgroup$
9
  • 1
    $\begingroup$ just say WLOG and then magically reach the answer! xd $\endgroup$
    – terrace
    Nov 25, 2019 at 17:17
  • 1
    $\begingroup$ rotated so as to permute the axes i.e. by 90° increments along any axis $\endgroup$
    – Aniruddha Deb
    Nov 25, 2019 at 17:18
  • 1
    $\begingroup$ @terrace: I wasn't sure -- I thought I'd ask whether it's necessary to think about that before I spend time thinking about it :-) $\endgroup$
    – joriki
    Nov 25, 2019 at 17:19
  • 1
    $\begingroup$ "What are the 20 possible cases here?" It helps to note that $\binom{6}{3}=20$. Given any choice of six numbers, splitting them into the three numbers used for $a$ and the three numbers used for $b$, there are twenty different ways that you can split. It did not actually matter what the values of the six numbers are, just their relation to one another in terms of which is larger than the next. $\endgroup$
    – JMoravitz
    Nov 25, 2019 at 17:20
  • 3
    $\begingroup$ Yes, there are cases where putting one box at an angle makes it work. For example, a $1 \times 2 \times 20$ box will fit in a $17 \times 18 \times 19$ box, but only at an angle. The official solution does not consider this. $\endgroup$
    – Ross Millikan
    Nov 25, 2019 at 17:30

1 Answer 1

Reset to default
7
$\begingroup$

The $20$ cases are given by $C^{6}_{3} = 20$. They are ways of splinting a set of $6$ distinct numbers into $2$ sets of $3$ numbers.

Ie. consider $\{a_{1},a_{2},a_{3},a_{4}, a_{5},a_{6}\}$ to be in increasing order. Then the $5$ good cases are:

$(\{a_{1},a_{2},a_{3}\},\{a_{4}, a_{5},a_{6}\})$

$(\{a_{1},a_{2},a_{4}\},\{a_{3}, a_{5},a_{6}\})$

$(\{a_{1},a_{2},a_{5}\},\{a_{3}, a_{4},a_{6}\})$

$(\{a_{1},a_{3},a_{4}\},\{a_{2}, a_{5},a_{6}\})$

$(\{a_{1},a_{3},a_{5}\},\{a_{2}, a_{4},a_{6}\})$

Edit: there should be ways of proving there are only $5$ without checking them all. Here is one method: $a_1$ must be part of the first set because if it were part of the second set, there is no number smaller than $a_1$, so the brick wouldn't fit. Similarly, $a_6$ must be part of the second set. It remains to split the remaining $4$ numbers $\{a_{2},a_{3},a_{4},a_{5}\}$ into $2$ sets of $2$. We have $C^{4}_{2} = 6$ ways of doing this. Five of those give us the above sets. The sixth one is $(\{a_{4},a_{5}\},\{a_{2},a_{3}\})$ giving $(\{a_{1},a_{4},a_{5}\},\{a_{2},a_{3},a_{6}\})$

which does not describe fitting bricks because $a_{4}>a_{3}$.

$\endgroup$
2
  • $\begingroup$ Are these cases exhaustive? Could you also prove that no more cases exist? $\endgroup$
    – Aniruddha Deb
    Nov 25, 2019 at 17:25
  • 1
    $\begingroup$ @AniruddhaDeb Yes. The correct search term here would be catalan numbers. Here we are counting the number of Dyck words formed by six characters. $\endgroup$
    – JMoravitz
    Nov 25, 2019 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.