Difference between revisions of "2001 AIME II Problems/Problem 9"
(→Solution) |
|||
(One intermediate revision by one other user 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 == | ||
− | We can use [[complementary counting]], counting all of the colorings that have at least one red square. | + | 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 by 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 | + | 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>. |
− | + | == See also == | |
− | + | {{AIME box|year=2001|n=II|num-b=8|num-a=10}} | |
− | |||
− | |||
− | |||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
− | + | {{MAA Notice}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Latest revision as of 19:35, 4 July 2013
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
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 by 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 .
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.