Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1993 AIME Problems/Problem 7"

m (→‎Solution 4 (Permutation))
(Permutation and Combination typically go together, so switched the order of sols a bit.)
 
(6 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
Three numbers, <math>a_1, a_2, a_3</math>, are drawn randomly and without replacement from the set <math>\{1, 2, 3,\ldots, 1000\}</math>. Three other numbers, <math>b_1, b_2, b_3</math>, are then drawn randomly and without replacement from the remaining set of <math>997</math> numbers. Let <math>p</math> be the probability that, after suitable rotation, a brick of dimensions <math>a_1 \times a_2 \times a_3</math> can be enclosed in a box of dimension <math>b_1 \times b_2 \times b_3</math>, with the sides of the brick parallel to the sides of the box. If <math>p</math> is written as a fraction in lowest terms, what is the sum of the numerator and denominator?
 
Three numbers, <math>a_1, a_2, a_3</math>, are drawn randomly and without replacement from the set <math>\{1, 2, 3,\ldots, 1000\}</math>. Three other numbers, <math>b_1, b_2, b_3</math>, are then drawn randomly and without replacement from the remaining set of <math>997</math> numbers. Let <math>p</math> be the probability that, after suitable rotation, a brick of dimensions <math>a_1 \times a_2 \times a_3</math> can be enclosed in a box of dimension <math>b_1 \times b_2 \times b_3</math>, with the sides of the brick parallel to the sides of the box. If <math>p</math> is written as a fraction in lowest terms, what is the sum of the numerator and denominator?
  
−
== Solution 1 (Combination) ==
+
== Solution 1 (Permutation) ==
 +
There is a total of <math>P(1000,6)</math> possible ordered <math>6</math>-tuples <math>(a_1,a_2,a_3,b_1,b_2,b_3).</math>
 +
 
 +
There are <math>C(1000,6)</math> possible sets <math>\{a_1,a_2,a_3,b_1,b_2,b_3\}.</math> We have five valid cases for the increasing order of these six elements:
 +
<ol style="margin-left: 1.5em;">
 +
  <li><math>aaabbb</math></li><p>
 +
  <li><math>aababb</math></li><p>
 +
  <li><math>aabbab</math></li><p>
 +
  <li><math>abaabb</math></li><p>
 +
  <li><math>ababab</math></li><p>
 +
</ol>
 +
Note that the <math>a</math>'s are different from each other, as there are <math>3!=6</math> ways to permute them as <math>a_1,a_2,</math> and <math>a_3.</math> Similarly, the <math>b</math>'s are different from each other, as there are <math>3!=6</math> ways to permute them as <math>b_1,b_2,</math> and <math>b_3.</math>
 +
 
 +
So, there is a total of <math>C(1000,6)\cdot5\cdot6^2</math> valid ordered <math>6</math>-tuples. The requested probability is <cmath>p=\frac{C(1000,6)\cdot5\cdot6^2}{P(1000,6)}=\frac{C(1000,6)\cdot5\cdot6^2}{C(1000,6)\cdot6!}=\frac14,</cmath> from which the answer is <math>1+4=\boxed{005}.</math>
 +
 
 +
~MRENTHUSIASM
 +
 
 +
== Solution 2 (Combination) ==
 
Call the six numbers selected <math>x_1 > x_2 > x_3 > x_4 > x_5 > x_6</math>. Clearly, <math>x_1</math> must be a dimension of the box, and <math>x_6</math> must be a dimension of the brick.  
 
Call the six numbers selected <math>x_1 > x_2 > x_3 > x_4 > x_5 > x_6</math>. Clearly, <math>x_1</math> must be a dimension of the box, and <math>x_6</math> must be a dimension of the brick.  
  
Line 13: Line 30:
 
Note that the <math>1000</math> in the problem, is not used, and is cleverly bypassed in the solution, because we can call our six numbers <math>x_1,x_2,x_3,x_4,x_5,x_6</math> whether they may be <math>1,2,3,4,5,6</math> in some order or <math>999,5,3,998,997,891</math> in some order.
 
Note that the <math>1000</math> in the problem, is not used, and is cleverly bypassed in the solution, because we can call our six numbers <math>x_1,x_2,x_3,x_4,x_5,x_6</math> whether they may be <math>1,2,3,4,5,6</math> in some order or <math>999,5,3,998,997,891</math> in some order.
  
−
== Solution 2 (Hook Length Formula) ==
+
== Solution 3 (Hook Length Formula) ==
−
Like Solution 1, call the six numbers selected <math>x_1 > x_2 > x_3 > x_4 > x_5 > x_6</math>. Using the Hook Length Formula, the number of valid configuration is <math>\frac{6!}{4\cdot3\cdot2\cdot3\cdot2}=5</math>. We proceed as Solution 1 does.
+
Like Solution 2, call the six numbers selected <math>x_1 > x_2 > x_3 > x_4 > x_5 > x_6</math>. Using the Hook Length Formula, the number of valid configuration is <math>\frac{6!}{4\cdot3\cdot2\cdot3\cdot2}=5</math>. We proceed as Solution 2 does.
  
−
== Solution 3 (Hook Length Formula) ==
+
== Solution 4 (Catalan Numbers) ==
−
As in the preceding solutions, we let <math>x_1>x_2>x_3>x_4>x_5>x_6</math> where each <math>x_i</math> 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 <math>n</math>th Catalan number (where <math>n</math> is the number of pairs of rising and falling sections) is <cmath>\frac{\binom{2n}{n}}{n+1}</cmath>
+
As in Solutions 2 and 3, we let <math>x_1>x_2>x_3>x_4>x_5>x_6</math> where each <math>x_i</math> 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 <math>n</math>th Catalan number (where <math>n</math> is the number of pairs of rising and falling sections) is <cmath>\frac{\binom{2n}{n}}{n+1}</cmath>
 
Thus, there are <math>\frac{\binom{6}{3}}{4}</math> ways to pick which of <math>x_1,x_2,x_3,x_4,x_5,</math> and <math>x_6</math> are the dimensions of the box, and which are the dimensions of the brick, such that the condition is fulfilled.  There are <math>\binom{6}{3}</math> total ways to choose which numbers make up the brick and box, so the probability of the condition being fulfilled is <math>\frac{\binom{6}{3}/4}{\binom{6}{3}}=\frac14\Longrightarrow \boxed{005}</math>.
 
Thus, there are <math>\frac{\binom{6}{3}}{4}</math> ways to pick which of <math>x_1,x_2,x_3,x_4,x_5,</math> and <math>x_6</math> are the dimensions of the box, and which are the dimensions of the brick, such that the condition is fulfilled.  There are <math>\binom{6}{3}</math> total ways to choose which numbers make up the brick and box, so the probability of the condition being fulfilled is <math>\frac{\binom{6}{3}/4}{\binom{6}{3}}=\frac14\Longrightarrow \boxed{005}</math>.
−
 
−
== Solution 4 (Permutation) ==
 
−
There is a total of <math>P(1000,6)</math> possible ordered <math>6</math>-tuples <math>(a_1,a_2,a_3,b_1,b_2,b_3).</math>
 
−
 
−
There are <math>C(1000,6)</math> possible sets <math>\{a_1,a_2,a_3,b_1,b_2,b_3\}.</math> We have five valid cases for the increasing order of these six elements:
 
−
<ol style="margin-left: 1.5em;">
 
−
  <li><math>AAABBB</math></li><p>
 
−
  <li><math>AABABB</math></li><p>
 
−
  <li><math>AABBAB</math></li><p>
 
−
  <li><math>ABAABB</math></li><p>
 
−
  <li><math>ABABAB</math></li><p>
 
−
</ol>
 
−
Note that the <math>A</math>'s are different from each other, as there are <math>3!=6</math> ways to permute them as <math>a_1,a_2,</math> and <math>a_3.</math> Similarly, the <math>B</math>'s are different from each other, as there are <math>3!=6</math> ways to permute them as <math>b_1,b_2,</math> and <math>b_3.</math>
 
−
 
−
So, there is a total of <math>C(1000,6)\cdot5\cdot6^2</math> valid ordered <math>6</math>-tuples. The requested probability is <cmath>p=\frac{C(1000,6)\cdot5\cdot6^2}{P(1000,6)}=\frac{C(1000,6)\cdot5\cdot6^2}{C(1000,6)\cdot6!}=\frac14,</cmath> from which the answer is <math>1+4=\boxed{005}.</math>
 
−
 
−
~MRENTHUSIASM
 
  
 
== See also ==
 
== See also ==

Latest revision as of 08:04, 7 January 2022

Problem

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 suitable rotation, a brick of dimensions $a_1 \times a_2 \times a_3$ can be enclosed in a box of dimension $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?

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}$.

See also

1993 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 6 		Followed by
Problem 8
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_7&oldid=169469"