# Difference between revisions of "2008 iTest Problems/Problem 65"

## Problem

Just as the twins finish their masterpiece of symbol art, Wendy comes along. Wendy is impressed by the explanation Alexis and Joshua give her as to how they knew they drew every row exactly once. Wendy puts them both to the test. "Suppose the two of you draw symbols as you have before, stars in pairs and boxes in threes." Wendy continues, "Now, suppose that I draw circles with $X$'s in the middle." Wendy shows them examples of such rows: $$\begin{array}{ccccccccccccccc}\vspace{10pt}*&*&*&*&\otimes&*&*&\otimes&*&*&*&*&\blacksquare&\blacksquare&\blacksquare\\\vspace{10pt}\blacksquare&\blacksquare&\blacksquare&*&*&*&*&\otimes&*&*&\otimes&*&*&*&*\\\vspace{10pt}\otimes&\blacksquare&\blacksquare&\blacksquare&\otimes&\otimes&*&*&\otimes&*&*&\otimes&\blacksquare&\blacksquare&\blacksquare\end{array}$$

How many rows are drawn?

## Solution

We will use casework similar to problem 64 but using multinomial coefficients (instead of binomial coefficients) to account for the three different types of patterns: boxes come in triplets, stars come in doublets and circle/x come in singlets.

The decompositions of 15 in (#triplets,#doublets,#singletons) are:

(5,0,0) ; (4,0,3) ; (4,1,1) ; (3,3,0) ; (3,2,2) ; (3,1,4) ; (3,0,6) ; (2,4,1) ; (2,3,3) ; (2,2,5) ; (2,1,7) ; (2,0,9); (1,6,0) ; (1,5,2) ; (1,4,4) ; (1,3,6) ; (1,2,8) ; (1,1,10) ; (1,0,12) ; (0,7,1) ; (0,6,3) ; (0,5,5) ; (0,4,7) ; (0,3,9) ; (0,2,11) ; (0,1,13) ; (0,0,15);

The Multinomial Coefficient $\binom{(a+b+c)}{a,b,c}$ is defined as $\frac{(a+b+c)!}{a!b!c!}$ and represents the number of ways that each (triplet,doublet,singlet) group can be drawn in the sand.

The final calculation is: $\binom{5}{5,0,0}$ $+\binom{7}{4,0,3}+\binom{6}{4,1,1}$ $+\binom{6}{3,3,0}+\binom{8}{3,2,3}+\binom{8}{3,1,4}+\binom{9}{3,0,6}$ $+\binom{7}{2,4,1}+\binom{8}{2,3,3}+\binom{9}{2,2,5}+\binom{10}{2,1,7}+\binom{11}{2,0,9}$ $+\binom{7}{1,6,0}+\binom{8}{1,5,2} +\binom{9}{1,4,4}+\binom{10}{1,3,6} +\binom{11}{1,2,8} +\binom{12}{1,1,10}+\binom{13}{1,0,12}$ $+\binom{8}{0,7,1} +\binom{9}{0,6,3} +\binom{10}{0,5,5} +\binom{11}{0,4,7} +\binom{12}{0,3,9} +\binom{13}{0,2,11} +\binom{14}{0,1,13} +\binom{15}{0,0,15}$ $=1+35+30+20+560+280+84+105+560+756+360+55+7$ $+168+630+840+495+132+13+8+84+252+330+220+78+14+1$ $=6118$