2001 AIME II Problems/Problem 9

Revision as of 15:51, 30 October 2007 by Azjps (talk | contribs) (wik)

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 $\frac {m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Solution

We can use complementary counting, counting all of the colorings that have at least one red $2\times 2$ square.

  • For at least one red $2 \times 2$ square:
There are four $2 \times 2$ squares to choose which one will be red. Then there are $2^5$ ways to color the rest of the squares. $4*32=128$
  • For at least two $2 \times 2$ 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 $2^3$ 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 $2^2$ ways to color the other squares. $32+8=40$
  • For at least three $2 \times 2$ squares:
Choosing three such squares leaves only one square left, with four places to place it. This is $2 \cdot 4 = 8$ ways.
  • For at least four $2 \times 2$ squares, we clearly only have one way.

By the Principle of Inclusion-Exclusion, there are (alternatively subtracting and adding) $128-40+8-1=95$ ways to have at least one red $2 \times 2$ square.

There are $2^9=512$ ways to paint the $3 \times 3$ square with no restrictions, so there are $512-95=417$ ways to paint the square with the restriction. Therefore, the probability of obtaining a grid that does not have a $2 \times 2$ red square is $\frac{417}{512}$, and $417+512=\boxed{929}$.

See also

2001 AIME II (ProblemsAnswer KeyResources)
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