Mock AIME 2 Pre 2005 Problems/Problem 14
Problem
Elm trees, 
Dogwood trees, and 
Oak trees are to be planted in a line in front of a library such that\begin{align*} i&) \text{ No two Elm trees are next to each other.} \\ ii&) \text{ No Dogwood tree is adjacent to an Oak tree.} \\ iii&) \text{ All of the trees are planted.} \end{align*}How many ways can the trees be situated in this manner?
Solution
We will do casework based on the number of "empty blocks" that are offered after planting only the Elm trees. Label the number of trees that these empty blocks can hold 
and trivially the sum of all 
for 
is 
. Now, call an 
-tuple 
basic if 
for all 
We note that for every legal placement of the Elm trees (and the distribution of the values of 
), the number of ways to place the Dogwood trees and the Oak trees for the said placement of the Elm trees is simplify the number of distinct subsets 
such of our aforementioned set such that the sum of the members in is equal to .
Case 1: two "empty blocks" are offered (this happens when two of the planted Elm trees are at the two ends of the row)
The only basic ordered pair 
that offers a nonzero number of legal placements of the Dogwood trees is 
(in which there is only one way to place the Dogwood Trees according to that placement), and there are 
permutations of , so there are a total of 
ways for this case.
Case 2: three "empty blocks" are offered (this happens when one of the planted Elm trees are at an end of the row)
Let 
be the set of all ordered basic -tuples of positive integers such that 
Now, given a member of 
(the 
th element in ) let 
be the number of distinct permutations of that said -tuple, and let 
be the number of subsets of positive integers in the ordered tuple such that the sum of the elements in that subset is equal to . For this case we are aiming to find![\[2 \sum P(3, i) D(3, i),\]](http://latex.artofproblemsolving.com/2/d/2/2d2d21056fac40755fbbbe2111df33f79ccfc8bc.png)
since for each basic -tuple there are ways to set up the Elm trees without affecting the -tuple. We can make a chart here (ignoring the ordered triples with 
):
![\[\begin{tabular}{|c|c|c|} \hline Basic ordered triple & P(i) & D(i) \\ \hline (1, 3, 5) & 6 & 1 \\ \hline (1, 4, 4) & 3 & 2 \\ \hline (2, 2, 5) & 3 & 1 \\ \hline (2, 3, 4) & 6 & 1 \\ \hline \end{tabular}\]](http://latex.artofproblemsolving.com/b/4/9/b49405ddd2ab678dcfbeb4e1c0e9731760af3e3d.png)
Thus, a total of 
ways for this case.
Case 3: four "empty blocks" are offered (this happens when none of the planted Elm trees are at an end of the row)
Note that for this case each basic -tuple only corresponds to one possible Elm tree placement. Like on Case 2, we can make a chart as follows (again, ignoring the ordered quadruples with ):
![\[\begin{tabular}{|c|c|c|c|} \hline Basic ordered quadruple & P(i) & D(i) \\ \hline (1, 1, 2, 5) & 12 & 1 \\ \hline (1, 1, 3, 4) & 12 & 3 \\ \hline (1, 2, 2, 4) & 12 & 2 \\ \hline (1, 2, 3, 3) & 12 & 2 \\ \hline (2, 2, 2, 3) & 4 & 3 \\ \hline \end{tabular}\]](http://latex.artofproblemsolving.com/9/e/5/9e5d9822a2b0796be419dd7fcb06dbd7987e0590.png)
Thus, we have a total of 
ways for Case 3.
Adding up our ways for each of the three cases, we obtain a final answer of 
distinct legal plantings.
-fidgetboss_4000
