2012 AMC 10A Problems/Problem 20

The following problem is from both the 2012 AMC 12A #15 and 2012 AMC 10A #20, so both problems redirect to this page.

Problem 20

A square is partitioned into unit squares. Each unit square is painted either white or black with each color being equally likely, chosen independently and at random. The square is then rotated clockwise about its center, and every white square in a position formerly occupied by a black square is painted black. The colors of all other squares are left unchanged. What is the probability the grid is now entirely black?

Solution 1

First, look for invariants. The center, unaffected by rotation, must be black. So automatically, the chance is less than 1/2. Note that a 90 degree rotation requires that black squares be across from each other across a vertical or horizontal axis.

As such, 2 squares directly across from each other must be black in the 4 edge squares. Since there are 2 configurations for this to be possible (top and bottom, right and left), this is a chance of

However, by PIE, subtract the chance all 4 are black and both configurations are met: . Through symmetrical reasoning, the corners also have a chance of having a configuration that yields all black corners.

Then, the chance that all squares black is the union of all these probabilities is

Psst. Great article for PIE. -> https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion 

~BJHHar

Solution 2

First, there is only one way for the middle square to be black because it is not affected by the rotation. Then we can consider the corners and edges separately. Let's first just consider the number of ways we can color the corners. There is case with all black squares. There are four cases with one white square and all work. There are six cases with two white squares, but only the with the white squares diagonal from each other work. There are no cases with three white squares or four white squares. Then the total number of ways to color the corners is . In essence, the edges work the same way, so there are also ways to color them. The number of ways to fit the conditions over the number of ways to color the squares is

Solution 3

We proceed by casework. Note that the middle square must be black because when rotated 90 degrees, it must keep its position. Now we have to deal with the following cases:
Case 1: 0 white squares. There is exactly way to color the grid this way.
Case 2: 1 white square. Note that the white square can be anywhere on the grid except for the middle square because when rotating 90 degrees it can never land on itself. Thus, there are cases.
Case 3: 2 white squares. We have ways to color two white squares without restrictions (the middle square must be black, giving us 8 squares to choose from). However, we must subtract the ways in which two white squares differ by a rotation of 90 degrees about the middle of the square. There are a total of 8 cases we must subtract (these are not too hard to see). Thus, there are ways from this.
Case 4: 3 white squares. Since we can not change the middle square, there are ways to color this. However, we must consider the cases where at least two squares differ by a rotation of 90 degrees. We can count this with PIE: by the Principle of Exclusion, the number of cases we want to exclude is the number of cases where 2 squares differ by a rotation of 90 degrees and minus when there are 3 squares such that two of them differ by rotation of 90 and 1 of them differs by rotation of 180, because of the overcount from our first case. From case 2, there are 8 causes such that two squares differ by a rotation of 90. There are also 6 other places we can place the third square (it can't be the middle of the two that we already colored), for a total of 48 ways. We have to subtract the second case. Note that there are 8 ways in which we can arrange two squares differing by 180 degrees. Out of these, each one has two ways to put another square such that two differ by 90 degrees and 1 pair differs by 180. However, this is overcounted by a factor of 2, so there are actually 8*2/2=8 ways. Thus, we have ways in this case.
Case 5: 4 white squares. Note that two of them have to be on one of the 4 corner squares, and two of them have to be on one of the 4 edge squares. Each solution yields two combinations, for a total of 2*2=4.
Adding up our cases yields ways. There are 512 ways to color the square without restrictions. Thus, the answer is

See Also

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.