Mock AIME 2 Pre 2005 Problems/Problem 14

Problem

$3$ Elm trees, $4$ Dogwood trees, and $5$ Oak trees are to be planted in a line in front of a library such thati) No two Elm trees are next to each other.ii) No Dogwood tree is adjacent to an Oak tree.iii) All of the trees are planted.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 $3$ Elm trees. Label the number of trees that these empty blocks can hold $E_1, E_2, ..., E_n,$ and trivially the sum of all $E_i$ for $1 \leq i \leq n$ is $9$. Now, call an $n$-tuple $(E_1, E_2, ..., E_n)$ basic if $E_i \leq E_{i+1}$ for all $1 \leq i \leq n-1.$ We note that for every legal placement of the $3$ Elm trees (and the distribution of the values of $E_1, E_2, ..., E_n$), the number of ways to place the Dogwood trees and the Oak trees for the said placement of the $3$ Elm trees is simplify the number of distinct subsets $S$ such of our aforementioned set $E_1, E_2, ..., E_n$ such that the sum of the members in $S$ is equal to $4$. Case 1: two "empty blocks" are offered (this happens when two of the $3$ planted Elm trees are at the two ends of the row) The only basic ordered pair $(E_1, E_2)$ that offers a nonzero number of legal placements of the Dogwood trees is $(4, 5)$ (in which there is only one way to place the Dogwood Trees according to that placement), and there are $2$ permutations of $(4, 5)$, so there are a total of $2 \cdot 1 = 2$ ways for this case. Case 2: three "empty blocks" are offered (this happens when one of the $3$ planted Elm trees are at an end of the row) Let $S(n)$ be the set of all ordered basic $n$-tuples $(E_1, E_2, ..., E_n)$ of positive integers such that $\sum_{i=1}^{n} E_i = 9.$ Now, given a member of $S(n)$ $S(n, i)$ (the $i$th element in $S(n)$) let $P(n, i)$ be the number of distinct permutations of that said $n$-tuple, and let $D(n, i)$ be the number of subsets of positive integers in the ordered tuple $S(n, i)$ such that the sum of the elements in that subset is equal to $4$. For this case we are aiming to find\[2 \sum P(3, i) D(3, i),\]since for each basic $n$-tuple there are $2$ ways to set up the Elm trees without affecting the $n$-tuple. We can make a chart here (ignoring the ordered triples with $D(i) = 0$):

\[\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}\]

Thus, a total of $2(6 \cdot 1 + 3 \cdot 2 + 3 \cdot 1 + 6 \cdot 1) = 42$ ways for this case. Case 3: four "empty blocks" are offered (this happens when none of the $3$ planted Elm trees are at an end of the row) Note that for this case each basic $4$-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 $D(i) = 0$):

\[\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}\]

Thus, we have a total of $12(1+3+2+2) + 4\cdot 3 = 108$ ways for Case 3. Adding up our ways for each of the three cases, we obtain a final answer of $2 + 42 + 108 = \boxed{152}$ distinct legal plantings.

-fidgetboss_4000