# 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
@JackBauer I just wanted to make you aware of this discussion on meta. – Martin Sleziak Dec 4 '15 at 12:41
@MartinSleziak, thank you – Jack Bauer Dec 4 '15 at 21:54

For the follow-up you have to assume that success will be announced after each try if you manage. We assume that a malevolent adversary controls the rotation, but you can flip a single coin, an opposite pair, or an adjacent pair at your option. You just can't keep track of anything except relative position between flips. You start knowing they are not all heads or all tails. Flip two opposite coins. If that doesn't work, you either have an odd number of heads or two adjacent heads. Flip two neighboring coins. If that doesn't work, you either have two opposite heads or an odd number of heads. Flip two opposite coins. If that doesn't work, you have an odd number of heads. Note that so far, we have always flipped an even number, so the parity hasn't changed. Flip one coin. If that doesn't work, you have two heads and two tails. Flip two opposite coins. If that doesn't work, you have two neighboring heads. Flip two adjacent. If that doesn't work, you have two opposite heads. Flip two opposite. Guaranteed to work.

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.

-