I got this problem from Rustan Leino, who says it's crossed the desk of Jan van de Snepscheut, but it may have been due to someone else.
I solved it and wrote up my solution.
A square table has a coin at each corner. Design an execution sequence, each of whose steps consists of one of the following operations:
such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.
The following execution sequence works: DIAG, SIDE, DIAG, ONE, DIAG, SIDE, DIAG.
We now explain why. In this explanation, we'll use the term win to mean reaching a state in which all coins match.
Lemma 1. If exactly two coins are heads, then executing DIAG, SIDE, DIAG wins at some point.
Proof. If the two heads are diagonally opposite, then we win as soon as we execute the first DIAG. So, from here on, we'll assume we start with the two heads adjacent to each other.
Since the two heads are adjacent, the first DIAG maintains the condition that there are exactly two heads and they're adjacent. Then, the next SIDE either immediately wins (by flipping the two heads or the two tails), or creates a situation where there are exactly two heads and they're diagonally opposite each other. In this case, the final DIAG wins.
In the initial state, there are either 0, 1, 2, 3, or 4 heads. If there are 0 or 4 heads, we win immediately. If there are 2 heads, then by Lemma 1 we win due to the initial three steps of the sequence. So, from here on, we need only consider the case that we start with 1 or 3 heads.
Each of the first three steps of our sequence flips two coins. Each flip either increases or decreases the number of heads by one, so a step that flips two coins changes the number of heads by -2, 0, or +2. Thus, since we start with an odd number of heads, we finish the first three steps still having an odd number of heads.
Executing ONE flips a single coin, thereby increasing or decreasing the number of heads by one. This makes the number of heads even. If it makes the number of heads 0 or 4, we immediately win. Otherwise, the number of heads is 2, and Lemma 1 tells us that executing the last three steps of the sequence causes us to eventually win.
We've now covered all cases, so the sequence is proven to always eventually win.