1984 AIME Problems/Problem 11

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 in lowest terms be the probability that no two birch trees are next to one another. Find .

Solution

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 different ways to arrange this.

There are total ways to arrange the twelve trees, so the probability is .

The answer is .

Solution 2

Let , denote birch tree and not-birch tree, respectively. Notice that we only need s to separate the s. Specifically, Since we have s, we are placing the extra s into the intervals beside the s.

Now doing simple casework.

If all s are in the same interval, there are ways.

If of the s are in the same interval, there are ways.

If the s are in different intervals, there are ways.

In total there are ways.

There are ways to distribute the birch trees among all trees.

Thus the probability equals .

~ 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!}$ (Error compiling LaTeX. Unknown error_msg). To compute the number of configurations with at least one pair of adjacent Birch trees, we use PIE.

1. (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!}$ (Error compiling LaTeX. Unknown error_msg) 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!}$ (Error compiling LaTeX. Unknown error_msg) cases. So our second term is $\frac{2 \cdot 10!}[2! \cdot 3! \cdot 4!}$ (Error compiling LaTeX. Unknown error_msg).

The third term can also happen in two ways. The three pairs could be arranged like BBBB or BBB BB. Both cases give $\frac{2 \cdot 9!}[3! \cdot 4!}$ (Error compiling LaTeX. Unknown error_msg) arrangements.

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

Substituting these into our PIE expression, we find that there are 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$ (Error compiling LaTeX. Unknown error_msg) 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}$ (Error compiling LaTeX. Unknown error_msg).

Therefore, the desired result is given by .

~ Vietajumping

See also

• AIME Problems and Solutions
• American Invitational Mathematics Examination
• Mathematics competition resources