Difference between revisions of "2013 AIME II Problems/Problem 9"
(→Solution 2 (Recursive): Corrected formula for f_2(n+1)) |
(Solution 1.1) |
||
Line 2: | Line 2: | ||
A <math>7\times 1</math> board is completely covered by <math>m\times 1</math> 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 <math>N</math> be the number of tilings of the <math>7\times 1</math> board in which all three colors are used at least once. For example, a <math>1\times 1</math> red tile followed by a <math>2\times 1</math> green tile, a <math>1\times 1</math> green tile, a <math>2\times 1</math> blue tile, and a <math>1\times 1</math> green tile is a valid tiling. Note that if the <math>2\times 1</math> blue tile is replaced by two <math>1\times 1</math> blue tiles, this results in a different tiling. Find the remainder when <math>N</math> is divided by <math>1000</math>. | A <math>7\times 1</math> board is completely covered by <math>m\times 1</math> 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 <math>N</math> be the number of tilings of the <math>7\times 1</math> board in which all three colors are used at least once. For example, a <math>1\times 1</math> red tile followed by a <math>2\times 1</math> green tile, a <math>1\times 1</math> green tile, a <math>2\times 1</math> blue tile, and a <math>1\times 1</math> green tile is a valid tiling. Note that if the <math>2\times 1</math> blue tile is replaced by two <math>1\times 1</math> blue tiles, this results in a different tiling. Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
− | ==Solution== | + | ==Solution 1== |
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. | We ignore the cases of 1 or 2 pieces since we need at least one tile of each color. | ||
Line 24: | Line 24: | ||
So the answer is <math>\boxed{106}</math>. | So the answer is <math>\boxed{106}</math>. | ||
+ | ==Solution 1.1 (Faster/Streamlined 1)== | ||
+ | This solution is basically solution 1 with more things done at once. The game plan: | ||
+ | |||
+ | <math>\sum_{i=0}^{7} (</math>the amount of ways to divide the board into <math>i</math> pieces<math>) \cdot (</math>the amount of ways to color the respective divisions) | ||
+ | |||
+ | The amount of ways to divide the board is just stars and bars. The colorings are PIE giving <math>3^i-3\cdot2^i+3</math>. Plus, you don't have to worry about <math>i\ge2</math> since they all give no solutions. So our equation becomes: | ||
+ | |||
+ | <math>\sum_{i=3}^{7} (\dbinom{6}{i})\cdot(3^i-3\cdot2^i+3)</math> | ||
+ | |||
+ | Write it all out, keep the numbers small with mod 1000, and you'll eventually arrive at your answer of <math>\boxed{106}</math>. | ||
+ | |||
+ | ~Rowechen Zhong | ||
==Solution 2 (Recursive)== | ==Solution 2 (Recursive)== | ||
3 colors is a lot. How many ways can we tile an n x 1 board with one color? It's going to be <math>2^{n-1}</math> because if you draw out the <math>n</math> spaces, you can decide whether each of the borders between the tiles are either there or not there. There are <math>n-1</math> borders so there are <math>2^{n-1}</math> tilings. Define a one-tiling of an mx1 as <math>f_1(m)</math> | 3 colors is a lot. How many ways can we tile an n x 1 board with one color? It's going to be <math>2^{n-1}</math> because if you draw out the <math>n</math> spaces, you can decide whether each of the borders between the tiles are either there or not there. There are <math>n-1</math> borders so there are <math>2^{n-1}</math> tilings. Define a one-tiling of an mx1 as <math>f_1(m)</math> |
Revision as of 11:58, 27 August 2017
Contents
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 1
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 use Principle of Inclusion-Exclusion to consider how many ways to color them:
- Three pieces:
- Four pieces:
- Five pieces:
- Six pieces:
- Seven pieces:
Finally, we combine them together: .
So the answer is .
Solution 1.1 (Faster/Streamlined 1)
This solution is basically solution 1 with more things done at once. The game plan:
the amount of ways to divide the board into piecesthe amount of ways to color the respective divisions)
The amount of ways to divide the board is just stars and bars. The colorings are PIE giving . Plus, you don't have to worry about since they all give no solutions. So our equation becomes:
Write it all out, keep the numbers small with mod 1000, and you'll eventually arrive at your answer of .
~Rowechen Zhong
Solution 2 (Recursive)
3 colors is a lot. How many ways can we tile an n x 1 board with one color? It's going to be because if you draw out the spaces, you can decide whether each of the borders between the tiles are either there or not there. There are borders so there are tilings. Define a one-tiling of an mx1 as
Now let's look at two colors. Let's see if we can get a two-tiling of an (n+1) x 1 based off a n x 1. There are 2 cases we should consider:
1) The n x 1 was a one-coloring and the block we are going to add consists of the second color. The number of ways we can do this is
2) The n x 1 was a two-color tiling so now we've got 3 cases to form the (n+1) x 1: We can either add a block of the first color, the second color, or we can adjoin a block to the last block in the n x 1.
This gives us
Time to tackle the 3-color tiling. Again, we split into 2 cases:
1) The n x 1 was a two-color tiling, and the block we are adding is of the 3rd color. This gives ways but we have to multiply by 3C2 because we have to pick 2 different colors for the two-color tiling.
2) The n x 1 was a 3-color tiling, and we have to consider what we can do with the block that we are adding. It can be any of the 3 colors, or we can adjoin it to whatever was the last block in the n x 1. This gives
So in total we have .
Finally, we just sorta bash through the computation to get
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.