Problem: (AIME) 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: The probability is equal to $1 - P(\text{there is a 2-by-2 red square})$. Now, to compute $P(\text{there is a 2-by-2 red square})$, we must compute the numerator, which is the number of ways we can have a 2-by-2 red square on the 3x3 grid. Let $A$ be the set of setups where there is a 2-by-2 red square in the bottom left corner, $B$ be the set where it is in the bottom right corner, $C$ be the set where it is in the top right corner, and $D$ be the set where it is in the top left corner. By the principle of inclusion exclusion, the number of ways we can have a 2-by-2 red square on the 3-by-3 grid is $ \begin{aligned} k := & |A| + |B| + |C| + |D| \\ - & (|A \cap C| + |A \cap B| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|) \\ + & (|A \cap B \cap C| + |A \cap C \cap D| + |A \cap B \cap D| + |B \cap C \cap D| ) \\ - & |A \cap B \cap C \cap D| \end{aligned} \implies \begin{aligned} k = &4 \cdot 2^5 \\ - & (4 \cdot 2^3 + 2 \cdot 2^2) \\ + & 4 \cdot 2 \\ - & 1 \\ = & 95 \end{aligned} $ then the $P(\text{there is a 2-by-2 red square}) = \frac{k}{2^9}$. Hence, $\frac{m}{n} = 1- \frac{95}{512} = \frac{417}{512} \implies m + n = 929$.