Difference between revisions of "2013 AIME II Problems/Problem 9"
IMOJonathan (talk | contribs) |
|||
Line 28: | Line 28: | ||
{{MAA Notice}} | {{MAA Notice}} | ||
− | [[Category: | + | [[Category:Advanced Combinatorics Problems]] |
Revision as of 12:06, 20 April 2014
Problem 9
A board is completely covered by
tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let
be the number of tilings of the
board in which all three colors are used at least once. For example, a
red tile followed by a
green tile, a
green tile, a
blue tile, and a
green tile is a valid tiling. Note that if the
blue tile is replaced by two
blue tiles, this results in a different tiling. Find the remainder when
is divided by
.
Solution
Firstly, we consider how many different ways possible to divide the board.
We ignore the cases of 1 or 2 pieces since we need at least one tile of each color.
- Three pieces:
,
,
, etc,
ways in total
- Four pieces:
- Five pieces:
- Six pieces:
- Seven pieces:
Secondly, we consider how many ways to color them:
- Three pieces:
- Four pieces:
- Five pieces:
- Six pieces:
- Seven pieces:
Finally, we combine then together: .
So the answer is .
See Also
2013 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.