Difference between revisions of "2013 AIME II Problems/Problem 9"
m |
m |
||
| Line 6: | Line 6: | ||
We ignore the cases of 1 or 2 pieces since we need at least one tile of each color. | We ignore the cases of 1 or 2 pieces since we need at least one tile of each color. | ||
| − | + | * Three pieces: <math>5+1+1</math>, <math>4+2+1</math>, <math>4+1+2</math>, etc, <math>\dbinom{6}{2}=15</math> ways in total | |
| − | + | * Four pieces: <math>\dbinom{6}{3}=20</math> | |
| − | + | * Five pieces: <math>\dbinom{6}{4}=15</math> | |
| − | + | * Six pieces: <math>\dbinom{6}{5}=6</math> | |
| − | + | * Seven pieces: <math>\dbinom{6}{6}=1</math> | |
Secondly, we consider how many ways to color them: | Secondly, we consider how many ways to color them: | ||
| − | + | * Three pieces: <math>3^3-3\times 2^3+3=6</math> | |
| − | + | * Four pieces: <math>3^4-3\times 2^4+3=36</math> | |
| − | + | * Five pieces: <math>3^5-3\times 2^5+3=150</math> | |
| − | + | * Six pieces: <math>3^6-3\times 2^6+3=540</math> | |
| − | + | * Seven pieces: <math>3^7-3\times 2^7+3=1806</math> | |
Finally, we combine then together: <math>15\times 6+20\times 36+15\times 150+6\times 540+1\times 1806= 8106</math>. | Finally, we combine then together: <math>15\times 6+20\times 36+15\times 150+6\times 540+1\times 1806= 8106</math>. | ||
Revision as of 15:57, 6 April 2013
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:
, 
, 
, etc, 
ways in total
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 | ||
