Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 AIME II Problems/Problem 9"

(Added solution)
m (→‎Solution 1)
(5 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 <math>i\ge2</math> since they all give no solutions. So our equation becomes:
+
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 58: Line 59:
  
 
==Solution 3==
 
==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 (each piece one of <math>x</math> colors) and then use PIE.
+
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
 
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
Line 69: Line 70:
 
In the given problem, we have <math>n=7</math>. By PIE, we have
 
In the given problem, we have <math>n=7</math>. By PIE, we have
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
&\quad\chi(7, 3) - {3 \choose 2} \, \chi(7, 2) + {3 \choose 1} \, \chi(7, 1) \\
+
&\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) \\
 
&= 3 \cdot 4^6 - 3(2 \cdot 3^6) + 3(1 \cdot 2^6) \\
 
&= 8106 \rightarrow \boxed{106}.
 
&= 8106 \rightarrow \boxed{106}.
 
\end{align*}</cmath>
 
\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==
 
{{AIME box|year=2013|n=II|num-b=8|num-a=10}}
 
{{AIME box|year=2013|n=II|num-b=8|num-a=10}}

Revision as of 09:45, 27 October 2020

Problem 9

A $7\times 1$ board is completely covered by $m\times 1$ 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 $N$ be the number of tilings of the $7\times 1$ board in which all three colors are used at least once. For example, a $1\times 1$ red tile followed by a $2\times 1$ green tile, a $1\times 1$ green tile, a $2\times 1$ blue tile, and a $1\times 1$ green tile is a valid tiling. Note that if the $2\times 1$ blue tile is replaced by two $1\times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000$.

Solution 1

Firstly, we consider how many different ways possible to divide the $7\times 1$ board. We ignore the cases of 1 or 2 pieces since we need at least one tile of each color.

  • Three pieces: $5+1+1$, $4+2+1$, $4+1+2$, etc, $\dbinom{6}{2}=15$ ways in total (just apply stars and bars here)
  • Four pieces: $\dbinom{6}{3}=20$
  • Five pieces: $\dbinom{6}{4}=15$
  • Six pieces: $\dbinom{6}{5}=6$
  • Seven pieces: $\dbinom{6}{6}=1$

Secondly, we use Principle of Inclusion-Exclusion to consider how many ways to color them:

  • Three pieces: $3^3-3\times 2^3+3=6$
  • Four pieces: $3^4-3\times 2^4+3=36$
  • Five pieces: $3^5-3\times 2^5+3=150$
  • Six pieces: $3^6-3\times 2^6+3=540$
  • Seven pieces: $3^7-3\times 2^7+3=1806$

Finally, we combine them together: $15\times 6+20\times 36+15\times 150+6\times 540+1\times 1806= 8106$.

So the answer is $\boxed{106}$.

Solution 1.1 (Faster/Streamlined 1)

This solution is basically solution 1 with more things done at once. The game plan:

$\sum_{i=0}^{7} ($the amount of ways to divide the board into $i$ pieces$) \cdot ($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 $3^i-3\cdot2^i+3$. 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:

$\sum_{i=3}^{7} (\dbinom{6}{i})\cdot(3^i-3\cdot2^i+3)$

Write it all out, keep the numbers small with mod 1000, and you'll eventually arrive at your answer of $\boxed{106}$.

~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 $2^{n-1}$ because if you draw out the $n$ spaces, you can decide whether each of the borders between the tiles are either there or not there. There are $n-1$ borders so there are $2^{n-1}$ tilings. Define a one-tiling of an mx1 as $f_1(m)$

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 $2f_1(n)$

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 $f_2(n+1)=2f_1(n)+3f_2(n)$

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 $f_2(n)$ 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 $4f_3(n)$

So in total we have $f_3(n+1)=3f_2(n)+4f_3(n)$.

Finally, we just sorta bash through the computation to get $f_3(7)=8\boxed{106}$

Solution 3

Let $n$ be the length of the board and $x$ be the number of colors. We will find the number of ways to tile the $n \times 1$ 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 $k$ pieces is ${n-1 \choose k-1}$. There are $x^k$ ways to color each of these divisions. Therefore, the total number of ways to divide and color the board is \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*}

In the given problem, we have $n=7$. By PIE, we have \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*}

The above formula for $\chi(n, x)$ can also be derived directly as follows:

  • The first square can be colored in one of $x$ ways.
  • Proceeding left to right, at each of the remaining $n-1$ squares, we have $x+1$ options:
    • $x$ 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.
    • $1$ way to expand the current tile by attaching a square of the current color.

This results in $x(x+1)^{n-1}$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_II_Problems/Problem_9&oldid=135916"