Difference between revisions of "2008 iTest Problems/Problem 65"
(Created page with "How many rows are drawn? We will use casework similar to problem 64 but using multinomial coefficients (instead of binomial coefficients) to account for the three different t...") |
m |
||
| Line 1: | Line 1: | ||
| + | ==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 <math>X</math>'s in the middle." Wendy shows them examples of such rows: | ||
| + | |||
| + | <cmath>\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} </cmath> | ||
| + | |||
| + | |||
| + | |||
How many rows are drawn? | How many rows are drawn? | ||
| + | |||
| + | |||
| + | == Solution == | ||
We will use casework similar to problem 64 but using multinomial coefficients (instead of binomial coefficients) to account | We will use casework similar to problem 64 but using multinomial coefficients (instead of binomial coefficients) to account | ||
| Line 24: | Line 35: | ||
<math> +\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}</math> | <math> +\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}</math> | ||
| − | <math>=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</math> | + | <math>=1+35+30+20+560+280+84+105+560+756+360+55+7</math> |
| + | |||
| + | <math>+168+630+840+495+132+13+8+84+252+330+220+78+14+1</math> | ||
| + | |||
| + | <math>=6118</math> | ||
| + | |||
| + | |||
| + | ==See Also== | ||
| + | {{2008 iTest box|num-b=64|num-a=66}} | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Latest revision as of 04:21, 28 January 2019
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 
'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}\]](http://latex.artofproblemsolving.com/5/b/9/5b9abd785c6472ad2645a892669263a46ee53845.png)
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 
is defined as 
and represents the number of ways that each (triplet,doublet,singlet) group can be drawn in the sand.
The final calculation is:
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 | ||
