Difference between revisions of "2013 AIME II Problems/Problem 9"
(Solution 1.1) |
Winterrain01 (talk | contribs) m (→Solution 1) |
||
(6 intermediate revisions by 2 users not shown) | |||
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 | + | * 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 (just apply stars and bars here) |
* Four pieces: <math>\dbinom{6}{3}=20</math> | * Four pieces: <math>\dbinom{6}{3}=20</math> | ||
* Five pieces: <math>\dbinom{6}{4}=15</math> | * Five pieces: <math>\dbinom{6}{4}=15</math> | ||
Line 29: | Line 29: | ||
<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) | <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 | + | 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 the cases where i=1 or i=2 since they both give no solutions. So our equation becomes: |
<math>\sum_{i=3}^{7} (\dbinom{6}{i})\cdot(3^i-3\cdot2^i+3)</math> | <math>\sum_{i=3}^{7} (\dbinom{6}{i})\cdot(3^i-3\cdot2^i+3)</math> | ||
Line 36: | Line 36: | ||
~Rowechen Zhong | ~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> | ||
Line 56: | Line 57: | ||
Finally, we just sorta bash through the computation to get <math>f_3(7)=8\boxed{106}</math> | Finally, we just sorta bash through the computation to get <math>f_3(7)=8\boxed{106}</math> | ||
+ | |||
+ | ==Solution 3== | ||
+ | Let <math>n</math> be the length of the board and <math>x</math> be the number of colors. We will find the number of ways to tile the <math>n \times 1</math> board with no color restrictions (some colors may be unused) and then use PIE. | ||
+ | |||
+ | By stars and bars, the number of ways to divide the board into <math>k</math> pieces is <math>{n-1 \choose k-1}</math>. There are <math>x^k</math> ways to color each of these divisions. Therefore, the total number of ways to divide and color the board is | ||
+ | <cmath>\begin{align*} | ||
+ | \chi(n, x) &:= \sum_{k=1}^n {n-1 \choose k-1} x^k \\ | ||
+ | &= x\sum_{k=0}^{n-1} {n-1 \choose k} x^k \\ | ||
+ | &= x(x+1)^{n-1}. | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | In the given problem, we have <math>n=7</math>. By PIE, we have | ||
+ | <cmath>\begin{align*} | ||
+ | &\quad {3 \choose 3} \chi(7, 3) - {3 \choose 2} \, \chi(7, 2) + {3 \choose 1} \, \chi(7, 1) \\ | ||
+ | &= 3 \cdot 4^6 - 3(2 \cdot 3^6) + 3(1 \cdot 2^6) \\ | ||
+ | &= 8106 \rightarrow \boxed{106}. | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | The above formula for <math>\chi(n, x)</math> can also be derived directly as follows: | ||
+ | |||
+ | * The first square can be colored in one of <math>x</math> ways. | ||
+ | * Proceeding left to right, at each of the remaining <math>n-1</math> squares, we have <math>x+1</math> options: | ||
+ | ** <math>x</math> ways to begin a new tile, selecting an arbitrary color. Note that this includes the case where we begin a new tile of the same color. | ||
+ | ** <math>1</math> way to expand the current tile by attaching a square of the current color. | ||
+ | |||
+ | This results in <math>x(x+1)^{n-1}</math> overall ways to divide and color the board (without the color use restriction). | ||
==See Also== | ==See Also== |
Latest revision as of 09:45, 27 October 2020
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 (just apply stars and bars here)
- 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 the cases where i=1 or i=2 since they both 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
Solution 3
Let be the length of the board and be the number of colors. We will find the number of ways to tile the board with no color restrictions (some colors may be unused) and then use PIE.
By stars and bars, the number of ways to divide the board into pieces is . There are ways to color each of these divisions. Therefore, the total number of ways to divide and color the board is
In the given problem, we have . By PIE, we have
The above formula for can also be derived directly as follows:
- The first square can be colored in one of ways.
- Proceeding left to right, at each of the remaining squares, we have options:
- ways to begin a new tile, selecting an arbitrary color. Note that this includes the case where we begin a new tile of the same color.
- way to expand the current tile by attaching a square of the current color.
This results in overall ways to divide and color the board (without the color use restriction).
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.