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 m/n, where m and n are relatively prime positive integers. Find m+n.
Solution:
Number the squares as shown. For i=1,2,4, and 5 , let Qi be the event that i is the upper left corner of a 2-by-2 red square, and let p(E) be the probability that event E will occur. By the Inclusion-Exclusion Principle, the probability that the grid does have at least one 2 -by-2 red square is
147258369
−+−p(Q1)+p(Q2)+p(Q4)+p(Q5)p(Q1∩Q2)−p(Q1∩Q4)−p(Q2∩Q5)−p(Q4∩Q5)−p(Q1∩Q5)−p(Q2∩Q4)p(Q1∩Q2∩Q5)+p(Q1∩Q2∩Q4)+p(Q1∩Q4∩Q5)+p(Q2∩Q4∩Q5)p(Q1∩Q2∩Q4∩Q5)
or
4(21)4−[4(21)6+2(21)7]+4(21)8−(21)9=51295
The probability that the grid does not have at least one 2-by-2 red square is therefore 1−95/512=417/512, so m+n=929.
The problems on this page are the property of the MAA's American Mathematics Competitions