Difference between revisions of "2008 iTest Problems/Problem 64"
Line 21: | Line 21: | ||
~sigma | ~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>. | 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== |
Latest revision as of 21: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
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.
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 |