Difference between revisions of "2013 AIME II Problems/Problem 9"
m |
m |
||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
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. | ||
+ | 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> | |
− | # 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 | + | # Five pieces: <math>\dbinom{6}{4}=15</math> |
− | # Four pieces:<math>\dbinom{6}{3}=20</math> | + | # Six pieces: <math>\dbinom{6}{5}=6</math> |
− | # Five pieces:<math>\dbinom{6}{4}=15</math> | + | # Seven pieces: <math>\dbinom{6}{6}=1</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: | ||
Line 21: | Line 20: | ||
# Seven pieces: <math>3^7-3\times 2^7+3=1806</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 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:
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 |