Difference between revisions of "2008 iTest Problems/Problem 64"
Rockmanex3 (talk | contribs) (Solution to Problem 64) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 17: | Line 17: | ||
Since the twins drew all the possible rows, there are <math>7+20+1 = \boxed{28}</math> rows that the twins drew. | Since the twins drew all the possible rows, there are <math>7+20+1 = \boxed{28}</math> rows that the twins drew. | ||
| + | ==Solution 2 (Recursion)== | ||
| + | Let <math>f(n)</math> be the amount of valid ways to arrange pairs and trios of symbols. Note that this is equal to <math>f(n-2)+f(n-3)</math>, because both <math>n-2</math> and <math>n-3</math> conveniently allow us to add a final pair or trio to get <math>n</math> symbols. Using binomial recursive expansion, we obtain <math>f(15) = f(3)+4f(4)+6f(5)+4f(6)+f(7)</math>. Since <math>f(2) = f(3) = f(4) = 1</math>, this can be simplified further to <math>1+4+6(1+1)+4(1+1)+(1+2) = \boxed{28}</math>. | ||
| + | |||
| + | ~sigma | ||
| + | |||
| + | Note: Recursive binomial expansion is just a fancy way of generalizing a pattern of recursive functions of the form <math>f(n)=f(n-k)+f(n-k-1)</math>. | ||
==See Also== | ==See Also== | ||
{{2008 iTest box|num-b=63|num-a=65}} | {{2008 iTest box|num-b=63|num-a=65}} | ||
[[Category:Introductory Combinatorics Problems]] | [[Category:Introductory Combinatorics Problems]] | ||
Latest revision as of 20:31, 4 March 2022
Problem
Alexis and Joshua are walking along the beach when they decide to draw symbols in the sand. Alex draws only stars and only draws them in pairs while Joshua draws only squares in trios. "Let's see how many rows of 
adjacent symbols we can make this way," suggests Josh. Alexis is game for the task and the two get busy drawing. Some of their rows look like
![\[\begin{array}{ccccccccccccccc}\vspace{10pt}*&*&*&*&*&*&*&*&*&*&*&*&\blacksquare&\blacksquare&\blacksquare\\\vspace{10pt}\blacksquare&\blacksquare&\blacksquare&*&*&*&*&*&*&*&*&*&*&*&*\\\vspace{10pt}\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&*&*&*&*&*&*&\blacksquare&\blacksquare&\blacksquare\\\vspace{10pt}\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare&\blacksquare\\\vspace{10pt}*&*&*&*&*&*&\blacksquare&\blacksquare&\blacksquare&*&*&*&*&*&*\end{array}\]](http://latex.artofproblemsolving.com/9/2/e/92e9e43bb103c5309a950410b052102742be8339.png)
The twins decide to count each of the first two rows above as distinct rows, even though one is the mirror image of the other. But the last of the rows above is its own mirror image, so they count it only once. Around an hour later, the twins realized that they had drawn every possible row exactly once using their rules of stars in pairs and squares in trips. How many rows did they draw in the sand?
Solution
We will use casework on the number of triplets drawn in order to count the number of rows drawn.
- If
triplet is drawn, then there are 
pairs needed. There is a total of 
rows in this case. - If
triplets are drawn, then there are pairs needed. There is a total of 
rows in this case. - If
triplets are drawn, then there are 
pairs needed. There is only row in this case.
triplet is drawn, then there are 
pairs needed. There is a total of 
rows in this case.
triplets are drawn, then there are 
rows in this case.
triplets are drawn, then there are 
pairs needed. There is only Since the twins drew all the possible rows, there are 
rows that the twins drew.
Solution 2 (Recursion)
Let 
be the amount of valid ways to arrange pairs and trios of symbols. Note that this is equal to 
, because both 
and 
conveniently allow us to add a final pair or trio to get 
symbols. Using binomial recursive expansion, we obtain 
. Since 
, this can be simplified further to 
.
~sigma
Note: Recursive binomial expansion is just a fancy way of generalizing a pattern of recursive functions of the form 
.
See Also
| 2008 iTest (Problems) | ||
| Preceded by: Problem 63 |
Followed by: Problem 65 | |
| 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 | ||
