# Coin Arrangement Puzzle

Disclaimer: I'm not sure how math related this puzzle is (it could potentially be), but I thought it was an interesting puzzle, and I also don't know how to solve it so I wanted to see if anyone had any ideas.

You have a board divided in quarters and a coin is in each spot. You do not know whether each is facing heads or tails upwards. In each turn, you can choose flip any number of coins. Specify a sequence of turns that guarantees that at some point all coins will be facing the same direction.

Follow up: Between each of your turns, the board is rotated an arbitrary amount amount (90, 180, 270 degrees). Specify a sequence of moves that guarantees that at some point all coins will be facing the same direction.

-
Math is involved because the solution exploits the binary system. It can be extended to a circle of 2^n coins and to have them all heads up (instead of just matching). I don't think the follow-up can be done except for 2^n coins. Without the rotation, you do it for n coins flipping one coin per turn in n-1 tries-look up Gray codes to help you. –  Ross Millikan Jun 29 '12 at 4:43

If success is all heads instead of all the same, put flip all four at the start and after every step of the above.

-
Wow nice. Thanks. –  Matt Jun 29 '12 at 5:03

Take the top right corner as fixed. you'll be flipping the other 3 coins to match it. The idea is that these 3 other coins can be thought of as a binary sequence. numbering them as $1,2,3$ (in any order), assume they start at zero and do moves that make you count from $0$ to $7$ in binary. so:

(0) 000

flip 1 (1) 001

flip 1 flip 2 (2) 010

flip 1 (3) 011

flip 1 flip 2 flip 3 (4) 100

...

and so on. Gray codes would work here as well; anything that will take you through the sequence. Since you enumerate all combinations of flipped/unflipped, one must involve all of them facing the same way.

My first guess would be that no solution exists in the case where the board is moved at random, since it seems entirely possible (though unlikely) to end up not ever touching two of the tiles. I would be very happy to be proven wrong though. Was the question about the expected time till all coins are facing the same direction?

-
Sorry, I think I miswrote the question. The original question said "arbitrary way" rather than "random way". Although...I'm not sure that really helps... –  Matt Jun 29 '12 at 3:56
it does help, so long as the rotation is the same every time (but we don't know which). Don't have a solution off the top of my head, but I think that's what it's asking. –  Robert Mastragostino Jun 29 '12 at 4:10

In your "follow up" you add a very important condition: that the table is rotated "arbitrarily". This word matters: if you said "randomly" we might try a randomized algorithm (just keep flipping coins until you're done, which you must be in the limit). But "arbitrary" implies that perhaps it's not random and there is an adversary trying to cause you to fail.

This topic is central to the theory of algorithms and "worst-case analysis." In any case, Ross's answer works, but he assumes that you will know when you're done (a condition you did not stipulate, but is required).

A variant of this puzzle: Suppose you have wine glasses instead of coins (you can feel their orientation and flip neither, one, or both each turn). You must devise an algorithm which is deterministic and which the adversary knows ahead of time that is still guaranteed to work.

-