Difference between revisions of "2001 AIME II Problems/Problem 9"
(→Problem) |
m (→Solution 2) |
||
(20 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Each unit square of a 3-by-3 unit-square grid is to be colored either blue or red. For each square, either color is equally likely to be used. The probability of obtaining a grid that does not have a 2-by-2 red square is <math>\frac {m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>. | + | Each unit [[square]] of a 3-by-3 unit-square grid is to be colored either blue or red. For each square, either color is equally likely to be used. The [[probability]] of obtaining a grid that does not have a 2-by-2 red square is <math>\frac {m}{n}</math>, where <math>m</math> and <math>n</math> are [[relatively prime]] positive integers. Find <math>m + n</math>. |
− | == Solution == | + | == Solution 1== |
+ | We can use [[complementary counting]], counting all of the colorings that have at least one red <math>2\times 2</math> square. | ||
+ | |||
+ | *For at least one red <math>2 \times 2</math> square: | ||
+ | :There are four <math>2 \times 2</math> squares to choose which one will be red. Then there are <math>2^5</math> ways to color the rest of the squares. <math>4*32=128</math> | ||
+ | *For at least two <math>2 \times 2</math> squares: | ||
+ | :There are two cases: those with two red squares on one side and those without red squares on one side. | ||
+ | :The first case is easy: 4 ways to choose which the side the squares will be on, and <math>2^3</math> ways to color the rest of the squares, so 32 ways to do that. For the second case, there will be only two ways to pick two squares, and <math>2^2</math> ways to color the other squares. <math>32+8=40</math> | ||
+ | *For at least three <math>2 \times 2</math> squares: | ||
+ | :Choosing three such squares leaves only one square left, with four places to place it. This is <math>2 \cdot 4 = 8</math> ways. | ||
+ | *For at least four <math>2 \times 2</math> squares, we clearly only have one way. | ||
+ | |||
+ | By the [[Principle of Inclusion-Exclusion]], there are (alternatively subtracting and adding) <math>128-40+8-1=95</math> ways to have at least one red <math>2 \times 2</math> square. | ||
+ | |||
+ | There are <math>2^9=512</math> ways to paint the <math>3 \times 3</math> square with no restrictions, so there are <math>512-95=417</math> ways to paint the square with the restriction. Therefore, the probability of obtaining a grid that does not have a <math>2 \times 2</math> red square is <math>\frac{417}{512}</math>, and <math>417+512=\boxed{929}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | We consider how many ways we can have 2*2 grid | ||
+ | |||
+ | <math>(1)</math>: All the grids are red--<math>1</math> case | ||
+ | |||
+ | <math>(2)</math>: One unit square is blue--The blue lies on the center of the bigger square, makes no 2*2 grid <math>9-1=8</math> cases | ||
+ | |||
+ | <math>(3)</math>: Two unit squares are blue--one of the squares lies in the center of the bigger square, makes no 2*2 grid, <math>8</math> cases. | ||
+ | Or, two squares lie on second column, first row, second column third row; second row first column, second row third column, 2 extra cases. <math>\binom 9 2-8-2=26</math> cases | ||
+ | |||
+ | <math>(4)</math> Three unit squares are blue. We find that if a 2*2 square is formed, there are 5 extra unit squares can be painted. But cases that three squares in the same column or same row is overcomunted. So in this case, there are <math>4\cdot (\binom 5 3)-4=36</math> | ||
+ | |||
+ | <math>(5)</math> Four unit squares are blue, no overcounted case will be considered. there are <math>4\cdot \binom 5 4=20</math> | ||
+ | |||
+ | <math>(6)</math> Five unit squares are blue, <math>4</math> cases in all | ||
+ | |||
+ | Sum up those cases, there are <math>1+8+26+36+20+4=95</math> cases that a 2*2 grid can be formed. | ||
+ | |||
+ | In all, there are <math>2^9=512</math> possible ways to paint the big square, so the answer is <math>1-\frac{95}{512}=\frac{417}{512}</math> leads to <math>\boxed{929}</math> | ||
+ | |||
+ | ~bluesoul | ||
+ | |||
+ | ==Solution 3 (Case Work)== | ||
+ | |||
+ | <cmath>\begin{array}{|c|c|c|} | ||
+ | \hline | ||
+ | C_{11} & C_{12} & C_{13}\\ | ||
+ | \hline | ||
+ | C_{21} & C_{22} & C_{23}\\ | ||
+ | \hline | ||
+ | C_{31} & C_{32} & C_{33}\\ | ||
+ | \hline | ||
+ | \end{array}</cmath> | ||
+ | |||
+ | Case 1: The 3-by-3 unit-square grid has exactly <math>1</math> 2-by-2 red square | ||
+ | |||
+ | Assume the 2-by-2 red square is at <math>C_{11}, C_{12}, C_{21}, C_{22}</math>. To make sure there are no more 2-by-2 red squares, <math>C_{31} \text{and} C_{32}</math> can't both be red and <math>C_{13} \text{and} C_{23}</math> can't both be red. Meaning that there are <math>2^2-1=3</math> coloring methods for <math>C_{31} \text{and} C_{32}</math> and <math>C_{13} \text{and} C_{23}</math>. <math>C_{33}</math> can be colored with either colors. However, the coloring method where <math>C_{23}, C_{32}, C_{33}</math> are all red needs to be removed. For exactly one 2-by-2 red square at <math>C_{11}, C_{12}, C_{21}, C_{22}</math>, there are <math>3 \cdot 3 \cdot 2 -1=17</math> coloring methods. As there are <math>4</math> locations for the 2-by-2 red square on the 3-by-3 unit-square grid, there are <math>17 \cdot 4 = 68</math> coloring methods. | ||
+ | |||
+ | |||
+ | Case 2: The 3-by-3 unit-square grid has exactly <math>2</math> 2-by-2 red squares | ||
+ | |||
+ | Case 2.1: <math>2</math> 2-by-2 red squares take up <math>6</math> unit grids | ||
+ | |||
+ | Assume the <math>2</math> 2-by-2 red squares are at <math>C_{11}, C_{12}, C_{21}, C_{22}, C_{31}, C_{32}</math>. To make sure there are no more 2-by-2 red squares, <math>C_{13} \text{and} C_{23}</math> can't both be red. Meaning that there are <math>2^2-1=3</math> coloring methods for <math>C_{13} \text{and} C_{23}</math>. <math>C_{33}</math> can be colored with either colors. However, the coloring method where <math>C_{13}, C_{23}, C_{33}</math> are all red needs to be removed. For exactly <math>2</math> 2-by-2 red squares at <math>C_{11}, C_{12}, C_{21}, C_{22}, C_{31}, C_{32}</math>, there are <math>3 \cdot 2 -1=5</math> coloring methods. As there are <math>4</math> locations for the <math>2</math> 2-by-2 red squares on the 3-by-3 unit-square grid, there are <math>5 \cdot 4 = 20</math> coloring methods. | ||
+ | |||
+ | Case 2.2: <math>2</math> 2-by-2 red squares take up <math>7</math> unit grids | ||
+ | |||
+ | Assume the <math>2</math> 2-by-2 red squares are at <math>C_{11}, C_{12}, C_{21}, C_{22}, C_{23}, C_{32}, C_{33}</math>. To make sure there are no more 2-by-2 red squares, <math>C_{13}</math> and <math>C_{31}</math> can't be red. Meaning that there is <math>1</math> coloring method for <math>C_{13}</math> and <math>C_{31}</math>. For exactly <math>2</math> 2-by-2 red squares at <math>C_{11}, C_{12}, C_{21}, C_{22}, C_{23}, C_{32}, C_{33}</math>, there is <math>1</math> coloring method. As there are <math>2</math> locations for the <math>2</math> 2-by-2 red squares on the 3-by-3 unit-square grid, there are <math>1 \cdot 2 = 2</math> coloring methods. | ||
+ | |||
+ | Hence, if the 3-by-3 unit-square grid has exactly <math>2</math> 2-by-2 red squares, there are <math>20+2 = 22</math> coloring methods. | ||
+ | |||
+ | |||
+ | Case 3: The 3-by-3 unit-square grid has exactly <math>3</math> 2-by-2 red squares | ||
+ | |||
+ | Assume the <math>3</math> 2-by-2 red squares are at <math>C_{11}, C_{12}, C_{13}, C_{21}, C_{22}, C_{23}, C_{32}, C_{33}</math>. To make sure there are no more 2-by-2 red squares, <math>C_{33}</math> can't be red. Meaning that there is <math>1</math> coloring method for <math>C_{33}</math>. For exactly <math>3</math> 2-by-2 red squares at <math>C_{11}, C_{12}, C_{13}, C_{21}, C_{22}, C_{23}, C_{32}, C_{33}</math>, there is <math>1</math> coloring method. As there are <math>4</math> locations for the <math>3</math> 2-by-2 red squares on the 3-by-3 unit-square grid, there are <math>1 \cdot 4 = 4</math> coloring methods. | ||
+ | |||
+ | |||
+ | Case 4: The 3-by-3 unit-square grid has exactly <math>4</math> 2-by-2 red squares | ||
+ | |||
+ | If the 3-by-3 unit-square grid has exactly <math>4</math> 2-by-2 red squares, all <math>9</math> unit grids are red and there is <math>1</math> coloring method. | ||
+ | |||
+ | |||
+ | In total, there are <math>68+22+4+1=95</math> coloring methods with 2-by-2 red squares. | ||
+ | <cmath>\frac{m}{n}=1-\frac{95}{2^9}=\frac{417}{512}</cmath> | ||
+ | |||
+ | <cmath>m+n=417+512=\boxed{\textbf{929}}</cmath> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=2001|n=II|num-b=8|num-a=10}} | |
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 14:39, 30 June 2024
Problem
Each unit square of a 3-by-3 unit-square grid is to be colored either blue or red. For each square, either color is equally likely to be used. The probability of obtaining a grid that does not have a 2-by-2 red square is , where
and
are relatively prime positive integers. Find
.
Solution 1
We can use complementary counting, counting all of the colorings that have at least one red square.
- For at least one red
square:
- There are four
squares to choose which one will be red. Then there are
ways to color the rest of the squares.
- For at least two
squares:
- There are two cases: those with two red squares on one side and those without red squares on one side.
- The first case is easy: 4 ways to choose which the side the squares will be on, and
ways to color the rest of the squares, so 32 ways to do that. For the second case, there will be only two ways to pick two squares, and
ways to color the other squares.
- For at least three
squares:
- Choosing three such squares leaves only one square left, with four places to place it. This is
ways.
- For at least four
squares, we clearly only have one way.
By the Principle of Inclusion-Exclusion, there are (alternatively subtracting and adding) ways to have at least one red
square.
There are ways to paint the
square with no restrictions, so there are
ways to paint the square with the restriction. Therefore, the probability of obtaining a grid that does not have a
red square is
, and
.
Solution 2
We consider how many ways we can have 2*2 grid
: All the grids are red--
case
: One unit square is blue--The blue lies on the center of the bigger square, makes no 2*2 grid
cases
: Two unit squares are blue--one of the squares lies in the center of the bigger square, makes no 2*2 grid,
cases.
Or, two squares lie on second column, first row, second column third row; second row first column, second row third column, 2 extra cases.
cases
Three unit squares are blue. We find that if a 2*2 square is formed, there are 5 extra unit squares can be painted. But cases that three squares in the same column or same row is overcomunted. So in this case, there are
Four unit squares are blue, no overcounted case will be considered. there are
Five unit squares are blue,
cases in all
Sum up those cases, there are cases that a 2*2 grid can be formed.
In all, there are possible ways to paint the big square, so the answer is
leads to
~bluesoul
Solution 3 (Case Work)
Case 1: The 3-by-3 unit-square grid has exactly 2-by-2 red square
Assume the 2-by-2 red square is at . To make sure there are no more 2-by-2 red squares,
can't both be red and
can't both be red. Meaning that there are
coloring methods for
and
.
can be colored with either colors. However, the coloring method where
are all red needs to be removed. For exactly one 2-by-2 red square at
, there are
coloring methods. As there are
locations for the 2-by-2 red square on the 3-by-3 unit-square grid, there are
coloring methods.
Case 2: The 3-by-3 unit-square grid has exactly 2-by-2 red squares
Case 2.1: 2-by-2 red squares take up
unit grids
Assume the 2-by-2 red squares are at
. To make sure there are no more 2-by-2 red squares,
can't both be red. Meaning that there are
coloring methods for
.
can be colored with either colors. However, the coloring method where
are all red needs to be removed. For exactly
2-by-2 red squares at
, there are
coloring methods. As there are
locations for the
2-by-2 red squares on the 3-by-3 unit-square grid, there are
coloring methods.
Case 2.2: 2-by-2 red squares take up
unit grids
Assume the 2-by-2 red squares are at
. To make sure there are no more 2-by-2 red squares,
and
can't be red. Meaning that there is
coloring method for
and
. For exactly
2-by-2 red squares at
, there is
coloring method. As there are
locations for the
2-by-2 red squares on the 3-by-3 unit-square grid, there are
coloring methods.
Hence, if the 3-by-3 unit-square grid has exactly 2-by-2 red squares, there are
coloring methods.
Case 3: The 3-by-3 unit-square grid has exactly 2-by-2 red squares
Assume the 2-by-2 red squares are at
. To make sure there are no more 2-by-2 red squares,
can't be red. Meaning that there is
coloring method for
. For exactly
2-by-2 red squares at
, there is
coloring method. As there are
locations for the
2-by-2 red squares on the 3-by-3 unit-square grid, there are
coloring methods.
Case 4: The 3-by-3 unit-square grid has exactly 2-by-2 red squares
If the 3-by-3 unit-square grid has exactly 2-by-2 red squares, all
unit grids are red and there is
coloring method.
In total, there are coloring methods with 2-by-2 red squares.
See also
2001 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.