Difference between revisions of "2001 AIME II Problems/Problem 9"
(→Problem) |
|||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| + | We can use [[complementary counting]], counting all of the colorings that have at least one red square. | ||
| + | |||
| + | Counting this directly is messy, so we use [[PIE]]: | ||
| + | |||
| + | For at least one red 2*2 square: | ||
| + | |||
| + | There are four 2*2 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 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> | ||
| + | |||
| + | We proceed with similar ways with three and four red squares, to get that there are 8 ways to get three red squares, and one way to get four red squares. We then alternatively add and subtract: | ||
| + | |||
| + | <math>128-40+8-1=95</math> | ||
| + | |||
| + | There are <math>2^9=512</math> ways to paint the 3*3 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 2-by-2 red square is <math>\frac{417}{512}</math>, and <math>417+512=\boxed{929}</math>. | ||
== See also == | == See also == | ||
* [[2001 AIME II Problems]] | * [[2001 AIME II Problems]] | ||
Revision as of 15:23, 30 October 2007
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.
Counting this directly is messy, so we use PIE:
For at least one red 2*2 square:
There are four 2*2 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. 
We proceed with similar ways with three and four red squares, to get that there are 8 ways to get three red squares, and one way to get four red squares. We then alternatively add and subtract:
There are 
ways to paint the 3*3 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 2-by-2 red square is 
, and 
.
