2008 iTest Problems/Problem 64

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 .