2008 iTest Problems/Problem 65

Revision as of 04:21, 28 January 2019 by Timneh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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$


See Also

2008 iTest (Problems)
Preceded by:
Problem 64
Followed by:
Problem 66
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100