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 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 $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

Page

Toolbox

Search

Mock AIME 2 Pre 2005 Problems/Problem 14

Problem

Solution