Difference between revisions of "Mock AIME 2 Pre 2005 Problems/Problem 14"

(Solution)
(Solution)
 
Line 10: Line 10:
 
Now, given a member of <math>S(n)</math> <math>S(n, i)</math> (the <math>i</math>th element in <math>S(n)</math>) let <math>P(n, i)</math> be the number of distinct permutations of that said <math>n</math>-tuple, and let <math>D(n, i)</math> be the number of subsets of positive integers in the ordered tuple <math>S(n, i)</math> such that the sum of the elements in that subset is equal to <math>4</math>. For this case we are aiming to find<cmath>2 \sum P(3, i) D(3, i),</cmath>since for each basic <math>n</math>-tuple there are <math>2</math> ways to set up the Elm trees without affecting the <math>n</math>-tuple. We can make a chart here (ignoring the ordered triples with <math>D(i) = 0</math>):
 
Now, given a member of <math>S(n)</math> <math>S(n, i)</math> (the <math>i</math>th element in <math>S(n)</math>) let <math>P(n, i)</math> be the number of distinct permutations of that said <math>n</math>-tuple, and let <math>D(n, i)</math> be the number of subsets of positive integers in the ordered tuple <math>S(n, i)</math> such that the sum of the elements in that subset is equal to <math>4</math>. For this case we are aiming to find<cmath>2 \sum P(3, i) D(3, i),</cmath>since for each basic <math>n</math>-tuple there are <math>2</math> ways to set up the Elm trees without affecting the <math>n</math>-tuple. We can make a chart here (ignoring the ordered triples with <math>D(i) = 0</math>):
  
<math>\begin{tabular}{|c|c|c|} \hline
+
<cmath>\begin{tabular}{|c|c|c|} \hline
 
Basic ordered triple & P(i) & D(i) \\ \hline
 
Basic ordered triple & P(i) & D(i) \\ \hline
 
(1, 3, 5) & 6 & 1 \\ \hline
 
(1, 3, 5) & 6 & 1 \\ \hline
Line 16: Line 16:
 
(2, 2, 5) & 3 & 1 \\ \hline
 
(2, 2, 5) & 3 & 1 \\ \hline
 
(2, 3, 4) & 6 & 1 \\ \hline
 
(2, 3, 4) & 6 & 1 \\ \hline
\end{tabular}</math>
+
\end{tabular}</cmath>
  
 
Thus, a total of <math>2(6 \cdot 1 + 3 \cdot 2 + 3 \cdot 1 + 6 \cdot 1) = 42</math> ways for this case.
 
Thus, a total of <math>2(6 \cdot 1 + 3 \cdot 2 + 3 \cdot 1 + 6 \cdot 1) = 42</math> ways for this case.
Line 22: Line 22:
 
Note that for this case each basic <math>4</math>-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 <math>D(i) = 0</math>):
 
Note that for this case each basic <math>4</math>-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 <math>D(i) = 0</math>):
  
<math>\begin{tabular}{|c|c|c|c|} \hline
+
<cmath>\begin{tabular}{|c|c|c|c|} \hline
 
Basic ordered quadruple & P(i) & D(i) \\ \hline
 
Basic ordered quadruple & P(i) & D(i) \\ \hline
 
(1, 1, 2, 5) & 12 & 1 \\ \hline
 
(1, 1, 2, 5) & 12 & 1 \\ \hline
Line 29: Line 29:
 
(1, 2, 3, 3) & 12 & 2 \\ \hline
 
(1, 2, 3, 3) & 12 & 2 \\ \hline
 
(2, 2, 2, 3) & 4 & 3 \\ \hline
 
(2, 2, 2, 3) & 4 & 3 \\ \hline
\end{tabular}</math>
+
\end{tabular}</cmath>
  
 
Thus, we have a total of <math>12(1+3+2+2) + 4\cdot 3 = 108</math> ways for Case 3.
 
Thus, we have a total of <math>12(1+3+2+2) + 4\cdot 3 = 108</math> ways for Case 3.

Latest revision as of 14:32, 6 January 2021

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