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 "1984 AIME Problems/Problem 11"

(→‎Solution 3 (using PIE))
m (→‎Solution 4)
 
(12 intermediate revisions by 4 users not shown)
Line 2: Line 2:
 
A gardener plants three maple trees, four oaks, and five birch trees in a row. He plants them in random order, each arrangement being equally likely. Let <math>\frac m n</math> in lowest terms be the [[probability]] that no two birch trees are next to one another. Find <math>m+n</math>.
 
A gardener plants three maple trees, four oaks, and five birch trees in a row. He plants them in random order, each arrangement being equally likely. Let <math>\frac m n</math> in lowest terms be the [[probability]] that no two birch trees are next to one another. Find <math>m+n</math>.
  
−
== Solution ==
+
== Solution 1 ==
 
First notice that there is no difference between the maple trees and the oak trees; we have only two types, birch trees and "non-birch" trees. (If you don't believe this reasoning, think about it. You could also differentiate the tall oak trees from the short oak trees, and the maple trees with many branches as opposed to those with few branches. Indeed, you could keep dividing until you have them each in their own category, but in the end it will not change the probability of the birch trees being near each other. That is, in the end, you multiply the numerator by the number of ways to arrange the oak and maple trees and you also multiply the denominator by the number of ways to arrange the oak and maple trees, making them cancel out.)
 
First notice that there is no difference between the maple trees and the oak trees; we have only two types, birch trees and "non-birch" trees. (If you don't believe this reasoning, think about it. You could also differentiate the tall oak trees from the short oak trees, and the maple trees with many branches as opposed to those with few branches. Indeed, you could keep dividing until you have them each in their own category, but in the end it will not change the probability of the birch trees being near each other. That is, in the end, you multiply the numerator by the number of ways to arrange the oak and maple trees and you also multiply the denominator by the number of ways to arrange the oak and maple trees, making them cancel out.)
  
Line 11: Line 11:
 
The answer is <math>7 + 99 = \boxed{106}</math>.
 
The answer is <math>7 + 99 = \boxed{106}</math>.
  
 +
 +
== (Another way to think about Solution 1) ==
 +
 +
So you can think of placing the <math>5</math> birch trees and the other trees with the restrictions as described above.
 +
Then let's take out one tree between each pair of birch trees. So you would remove <math>4</math> trees that aren't birch. What you are left with is a unique arrangement of <math>5</math> birch trees and <math>3</math> other trees that is unrestricted.
 +
Some birch trees might become adjacent after you remove <math>4</math> trees. Adding a tree between each pair of people gives a unique arrangement of <math>5</math> nonadjacent birch trees.
 +
This guarantees that there are no adjacent trees. The number of unrestricted <math>7</math> tree arrangments is <math>{8\choose5} = 56</math>. Then proceed as told in Solution <math>1</math>.
 +
 +
~ blueballoon
  
 
== Solution 2 ==
 
== Solution 2 ==
Line 38: Line 47:
  
 
Note that the requested probability is computed by dividing the number of configurations with no adjacent Birch trees by the total number of configurations. We can compute the number of configurations with no adjacent Birch trees using complementary counting and then the Principle of Inclusion-Exclusion.
 
Note that the requested probability is computed by dividing the number of configurations with no adjacent Birch trees by the total number of configurations. We can compute the number of configurations with no adjacent Birch trees using complementary counting and then the Principle of Inclusion-Exclusion.
−
 
  
 
The number of configurations with no adjacent Birch trees is equal to the total number of configurations minus the number of configurations with at least one pair of adjacent Birch trees.  
 
The number of configurations with no adjacent Birch trees is equal to the total number of configurations minus the number of configurations with at least one pair of adjacent Birch trees.  
−
 
  
 
The total number of configurations is given by <math>\frac{12!}{3! \cdot 4! \cdot 5!}</math>. To compute the number of configurations with at least one pair of adjacent Birch trees, we use PIE.
 
The total number of configurations is given by <math>\frac{12!}{3! \cdot 4! \cdot 5!}</math>. To compute the number of configurations with at least one pair of adjacent Birch trees, we use PIE.
  
−
 
+
<math>\#</math>(configurations with at least one pair of adjacent Birch trees) <math>=</math> <math>\#</math>(configurations with one pair) <math>-</math> <math>\#</math>(configurations with two pairs) <math>+</math> <math>\#</math>(configurations with three pairs) <math>-</math> <math>\#</math>(configurations with four pairs).
−
#(configurations with at least one pair of adjacent Birch trees) = #(configurations with one pair) - #(configurations with two pairs) + #(configurations with three pairs) - #(configurations with four pairs).
 
−
 
 
  
 
To compute the first term, note that we can treat the adjacent pair of Birch trees as one separate tree. This then gives <math>\frac{11!}{3! \cdot 3! \cdot 4!}</math> configurations.  
 
To compute the first term, note that we can treat the adjacent pair of Birch trees as one separate tree. This then gives <math>\frac{11!}{3! \cdot 3! \cdot 4!}</math> configurations.  
−
 
  
 
For the second term, we have two cases. The two pairs could either happen consecutively (BBB) or separately (BB BB). They both give <math>\frac{10!}{2! \cdot 3! \cdot 4!}</math> cases. So our second term is <math>\frac{2 \cdot 10!}{2! \cdot 3! \cdot 4!}</math>.
 
For the second term, we have two cases. The two pairs could either happen consecutively (BBB) or separately (BB BB). They both give <math>\frac{10!}{2! \cdot 3! \cdot 4!}</math> cases. So our second term is <math>\frac{2 \cdot 10!}{2! \cdot 3! \cdot 4!}</math>.
  
−
 
+
The third term can also happen in two ways. The three pairs could be arranged like BBBB or BBB BB. Both cases together give <math>\frac{2 \cdot 9!}{3! \cdot 4!}</math> arrangements.
−
The third term can also happen in two ways. The three pairs could be arranged like BBBB or BBB BB. Both cases give <math>\frac{2 \cdot 9!}{3! \cdot 4!}</math> arrangements.
 
−
 
 
  
 
The final term can happen in one way (BBBBB). This gives <math>\frac{8!}{3! \cdot 4!}</math> arrangements.
 
The final term can happen in one way (BBBBB). This gives <math>\frac{8!}{3! \cdot 4!}</math> arrangements.
−
 
  
 
Substituting these into our PIE expression, we find that there are <math>25760</math> configurations with at least one pair of adjacent Birch trees. Therefore, there are a total of <math>\frac{12!}{3! \cdot 4! \cdot 5!} - 25760 = 1960</math> configurations with no adjacent Birch trees.
 
Substituting these into our PIE expression, we find that there are <math>25760</math> configurations with at least one pair of adjacent Birch trees. Therefore, there are a total of <math>\frac{12!}{3! \cdot 4! \cdot 5!} - 25760 = 1960</math> configurations with no adjacent Birch trees.
−
 
  
 
Thus, the probability of a given configuration having no two adjacent Birch trees is given by <math>\frac{1960}{\frac{12!}{3! \cdot 4! \cdot 5!}} = \frac{7}{99}</math>.
 
Thus, the probability of a given configuration having no two adjacent Birch trees is given by <math>\frac{1960}{\frac{12!}{3! \cdot 4! \cdot 5!}} = \frac{7}{99}</math>.
Line 69: Line 69:
 
Therefore, the desired result is given by <math>7+99 = \boxed{106}</math>.
 
Therefore, the desired result is given by <math>7+99 = \boxed{106}</math>.
  
−
~ Vietajumping
+
~ vietajumping
 +
 
 +
=Solution 4=
 +
Here is a solution leaving out nothing. This solution is dedicated to those that are in self study and wish to learn the most they can. I will make it as elementary as possible and intuition based.
 +
Arrange first the <math>3</math> maple and <math>4</math> oaks as <math>MMMOOOO</math>. We then notice that for none of the <math>5</math> birch trees to be adjacent, they must be put in between these <math>M</math>'s and <math>O</math>'s. We then see that there are <math>8</math> spots to put these <math>5</math> birch trees in. So we can select <math>5</math> spots for these birch trees in <math>\binom{8}{5}</math>. But then, we can rearrange the <math>M</math>'s and <math>O</math>'s in <math>7!/(3!4!)=\binom{7}{3}</math> ways. So then there are <math>\binom{8}{5}\binom{7}{3}</math> valid arrangements with no given consecutive birch trees.
 +
There are then a total of <math>\frac{12!}{3!4!5!}</math> different total arrangements. Therefore the probability is given as <math>\frac{\binom{8}{5}\binom{7}{3}}{\frac{12!}{3!4!5!}}=\frac{7}{99}</math>, so the answer is <math>7+99=\boxed{106}</math>.
 +
 
 +
~th1nq3r
  
 
== See also ==
 
== See also ==

Latest revision as of 23:52, 6 September 2023

Problem

A gardener plants three maple trees, four oaks, and five birch trees in a row. He plants them in random order, each arrangement being equally likely. Let $\frac m n$ in lowest terms be the probability that no two birch trees are next to one another. Find $m+n$.

Solution 1

First notice that there is no difference between the maple trees and the oak trees; we have only two types, birch trees and "non-birch" trees. (If you don't believe this reasoning, think about it. You could also differentiate the tall oak trees from the short oak trees, and the maple trees with many branches as opposed to those with few branches. Indeed, you could keep dividing until you have them each in their own category, but in the end it will not change the probability of the birch trees being near each other. That is, in the end, you multiply the numerator by the number of ways to arrange the oak and maple trees and you also multiply the denominator by the number of ways to arrange the oak and maple trees, making them cancel out.)

The five birch trees must be placed amongst the seven previous trees. We can think of these trees as 5 dividers of 8 slots that the birch trees can go in, making ${8\choose5} = 56$ different ways to arrange this.

There are ${12 \choose 5} = 792$ total ways to arrange the twelve trees, so the probability is $\frac{56}{792} = \frac{7}{99}$.

The answer is $7 + 99 = \boxed{106}$.


(Another way to think about Solution 1)

So you can think of placing the $5$ birch trees and the other trees with the restrictions as described above. Then let's take out one tree between each pair of birch trees. So you would remove $4$ trees that aren't birch. What you are left with is a unique arrangement of $5$ birch trees and $3$ other trees that is unrestricted. Some birch trees might become adjacent after you remove $4$ trees. Adding a tree between each pair of people gives a unique arrangement of $5$ nonadjacent birch trees. This guarantees that there are no adjacent trees. The number of unrestricted $7$ tree arrangments is ${8\choose5} = 56$. Then proceed as told in Solution $1$.

~ blueballoon

Solution 2

Let $b$, $n$ denote birch tree and not-birch tree, respectively. Notice that we only need $4$ $n$s to separate the $5$ $b$s. Specifically, \[b,n,b,n,b,n,b,n,b\] Since we have $7$ $n$s, we are placing the extra $3$ $n$s into the $6$ intervals beside the $b$s.

Now doing simple casework.

If all $3$ $n$s are in the same interval, there are $6$ ways.

If $2$ of the $3$ $n$s are in the same interval, there are $6\cdot5=30$ ways.

If the $n$s are in $3$ different intervals, there are ${6 \choose 3} =20$ ways.

In total there are $6+30+20=56$ ways.

There are ${12\choose5}=792$ ways to distribute the birch trees among all $12$ trees.

Thus the probability equals $\frac{56}{792}=\frac{7}{99}\Longrightarrow m+n=7+99=\boxed{106}$.

~ Nafer

Solution 3 (using PIE)

Note that the requested probability is computed by dividing the number of configurations with no adjacent Birch trees by the total number of configurations. We can compute the number of configurations with no adjacent Birch trees using complementary counting and then the Principle of Inclusion-Exclusion.

The number of configurations with no adjacent Birch trees is equal to the total number of configurations minus the number of configurations with at least one pair of adjacent Birch trees.

The total number of configurations is given by $\frac{12!}{3! \cdot 4! \cdot 5!}$. To compute the number of configurations with at least one pair of adjacent Birch trees, we use PIE.

$\#$(configurations with at least one pair of adjacent Birch trees) $=$ $\#$(configurations with one pair) $-$ $\#$(configurations with two pairs) $+$ $\#$(configurations with three pairs) $-$ $\#$(configurations with four pairs).

To compute the first term, note that we can treat the adjacent pair of Birch trees as one separate tree. This then gives $\frac{11!}{3! \cdot 3! \cdot 4!}$ configurations.

For the second term, we have two cases. The two pairs could either happen consecutively (BBB) or separately (BB BB). They both give $\frac{10!}{2! \cdot 3! \cdot 4!}$ cases. So our second term is $\frac{2 \cdot 10!}{2! \cdot 3! \cdot 4!}$.

The third term can also happen in two ways. The three pairs could be arranged like BBBB or BBB BB. Both cases together give $\frac{2 \cdot 9!}{3! \cdot 4!}$ arrangements.

The final term can happen in one way (BBBBB). This gives $\frac{8!}{3! \cdot 4!}$ arrangements.

Substituting these into our PIE expression, we find that there are $25760$ configurations with at least one pair of adjacent Birch trees. Therefore, there are a total of $\frac{12!}{3! \cdot 4! \cdot 5!} - 25760 = 1960$ configurations with no adjacent Birch trees.

Thus, the probability of a given configuration having no two adjacent Birch trees is given by $\frac{1960}{\frac{12!}{3! \cdot 4! \cdot 5!}} = \frac{7}{99}$.


Therefore, the desired result is given by $7+99 = \boxed{106}$.

~ vietajumping

Solution 4

Here is a solution leaving out nothing. This solution is dedicated to those that are in self study and wish to learn the most they can. I will make it as elementary as possible and intuition based. Arrange first the $3$ maple and $4$ oaks as $MMMOOOO$. We then notice that for none of the $5$ birch trees to be adjacent, they must be put in between these $M$'s and $O$'s. We then see that there are $8$ spots to put these $5$ birch trees in. So we can select $5$ spots for these birch trees in $\binom{8}{5}$. But then, we can rearrange the $M$'s and $O$'s in $7!/(3!4!)=\binom{7}{3}$ ways. So then there are $\binom{8}{5}\binom{7}{3}$ valid arrangements with no given consecutive birch trees. There are then a total of $\frac{12!}{3!4!5!}$ different total arrangements. Therefore the probability is given as $\frac{\binom{8}{5}\binom{7}{3}}{\frac{12!}{3!4!5!}}=\frac{7}{99}$, so the answer is $7+99=\boxed{106}$.

~th1nq3r

See also

1984 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1984_AIME_Problems/Problem_11&oldid=197920"