# 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 findsince 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 ):

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 ):

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