Difference between revisions of "2013 AIME II Problems/Problem 9"
m (oops) |
m |
||
Line 5: | Line 5: | ||
Firstly, we consider how many different ways possible to divide the <math>7\times 1</math> board. | Firstly, we consider how many different ways possible to divide the <math>7\times 1</math> board. | ||
− | + | # One piece: <math>7</math>,<math>\dbinom{6}{0}=1</math>way in total(since the 3 colors are used at least once, we reject this case) | |
− | + | # Two pieces:<math>6+1</math>,<math>5+2</math>,etc,<math>\dbinom{6}{1}=6</math>ways in total(rejected for the same reason) | |
− | + | # 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> |
So the answer is <math>\boxed{106}</math>. | So the answer is <math>\boxed{106}</math>. |
Revision as of 16:55, 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.
- One piece:
,
way in total(since the 3 colors are used at least once, we reject this case)
- Two pieces:
,
,etc,
ways in total(rejected for the same reason)
- 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 |