Bay Area Mathematical Olympiad

Solution:

Assume that the squares have unit length. Consider, at any time during the game, the perimeter of the region of empty squares (this region may or may not be connected). For example, suppose that at some time 64 squares are empty. If the empty squares are packed together forming an $8 \times 8$ square, the perimeter will equal $4 \cdot 8=32$. On the other hand, if none of the 64 empty squares are adjacent to one another, the perimeter will equal $4 \cdot 64=256$ (each square has perimeter 4).
At the start of the game, there are $k=59$ empty squares. At this point the perimeter is at most $4k$. Now consider what happens as different coins are removed.

In order for a penny to be removed, it has to be surrounded on all 4 sides by empty squares. The following diagram illustrates the situation. The shaded squares are empty, the squares containing "$X$" are occupied by arbitrary coins, and "$P$" of course denotes a penny. The thick lines indicate the perimeter.

$\longrightarrow$

Before the removal, the perimeter included the boundary of the square containing the penny. After the removal, this boundary is gone. Thus, whenever a penny is removed, the perimeter decreases by 4.

$\longrightarrow$

In this case, the perimeter decreases by 2. Thus, no matter what, after a nickel is removed, the perimeter decreases by at least 2.
By similar reasoning (draw diagrams!) we conclude that if a dime is removed, the perimeter does not increase (it also could decrease by 2 or 4), and when a quarter is removed, the perimeter may increase, but by at most 2 (it also could not change or decrease by 2 or 4).

Now we will show that it is impossible for the board to evolve so that no coins are left. Note that this would cause the perimeter to equal $4 \cdot 20=80$. Suppose that at the start, $p$ pennies, $n$ nickels, $d$ dimes, and $q$ quarters were removed (so $p+n+d+q=k$). Let $t=10$. If the board evolved so that all the remaining coins were removed, then $t^{2}-p$ pennies would be removed, decreasing the perimeter by exactly $4\left(t^{2}-p\right)$. Likewise, $t^{2}-n$ nickels would be removed, but this will decrease the perimeter by at least $2\left(t^{2}-n\right)$. The $t^{2}-d$ dimes that would be removed decrease the perimeter by at least zero. And finally, $t^{2}-q$ quarters are removed and these could make the perimeter increase by at most $2\left(t^{2}-q\right)$. Recall that the starting value for the perimeter is at most $4k$. Thus, if all coins were removed, the final value of the perimeter would be at most
$$4k-4\left(t^{2}-p\right)-2\left(t^{2}-n\right)+2\left(t^{2}-q\right)=4k-4t^{2}+4p+2n-2q.$$
But $4p+2n-2q$ is certainly less than or equal to $4(p+n+d+q)=4k$, so the final value of the perimeter is at most
$$4k-4t^{2}+4k=8k-4t^{2}=8 \cdot 59-4 \cdot 10^{2}=72,$$
Contradicting the fact that the perimeter must equal 80.

Solution 2:

Define $P$ to be perimeter of empty region (as defined in the previous solution) and let $q, d, n$ be respectively the number of quarters, dimes, and nickels on the board at a given time. Then the quantity
$$P-4q-2d+2n$$
is a monovariant: it is non-increasing (no matter how the coins are legally removed). The initial value of this quantity is at most 72, yet the value of the empty board is 80. Hence the board will never be empty.

Solution 3:

For simplicity, give each coin the value 1, 2, 3, 4 (pennies, nickels, dimes, quarters) according to the minimum number of adjacent squares that are required for their removal. If $x$ is a configuration of coins let $f(x)$ denote the sum of the coins plus the number of pairs of adjacent empty squares on the board. If $x'$ is a configuration obtained from $x$ by (legally) removing some coin, then $f(x') \geq f(x)$ by the rules (e.g., removing a dime decreases the total coin value by 3 but increases the number of orthogonally adjacent pairs by at least 3). In other words, $f(x)$ is a monovariant. A simple count shows that $f$ (empty) $=760$ and
$$f(\text{initial})=764=100 \cdot 1+100 \cdot 2+100 \cdot 3+41 \cdot 4$$
since the smallest initial $f()$ is obtained by removing 59 pennies (and not creating any adjacent squares). Since we can't move upwards from 764 and end up at 760 the desired sequences of moves doesn't exist.