Flipping the Glasses

In the last post, I mentioned a simple logic puzzle that I’d stumbled over while wandering around the interweb. Start with four glasses, in a row, all upright. The goal is, through a series of moves, to turn them all upside down. On each move, you flip three of the four glasses — up if down or down if up.

The goal is to end up with all four glasses upside-down in the least number of moves possible. It’s not hard to find the solution by trial and error, but it turns out there’s an underlying trick that not only solves it but solves it regardless of the number of glasses (where each move flips N-1).

Bonus: these solutions even look pretty — or at least symmetrical.

We’ll start with the original four-glass puzzle and then expend to the general case for any number of glasses. One punchline up front, it turns out to be any number of even glasses. There are no solutions for odd numbers of glasses.

We’ll start with four glasses (N=4), in a row, all upright:

State 0: Initial state, all upright.

The only rule is that we flip three of them each move. With all upright, it doesn’t really matter, they’re all the same, so we’ll flip the first three:

Move 1: We’ll flip the first three glasses.

Which gives us:

State 1: Three down and one up after one move.

The question of which three to flip is more challenging this time. Clearly, if we flip the same first three, we’ll end up where we started, so that’s no useful.

The only alternative is to flip the upright glass on the right and then two of the upside-down glasses on the left:

Move 2: The one (different) glass from right plus two from the left.

Which gives us:

State 2: Two down and two up after two moves.

I’ll mention that this set of moves follows the protocol of the underlying trick for solving the puzzle. I’ll cover it in more detail below, but it basically consists of flipping as many glasses on the right as are different from the glasses on the left and then taking the remaining flips from the glasses on the left. In both cases, start with the glasses on the outside and work in.

Note that flipping the two on the left, plus one on the right, would put us back in state one, with three down and one up. Following out protocol, though, we want to flip the two on the right and one more from the left:

Move 3: The two from the right plus one from the left.

Which gives us:

State 3: One down and three up after three moves.

Which, ah ha, obviously just needs one more move to reach the final state (of all glasses upside-down). This is the final state necessary — one glass already upside-down and N-1 glasses (three, in this case) to flip.

It’s the only final state that does lead to a solution, which means the state that leads to it is the only state leading to leading to a solution, and so on back to the initial state. Thus, these are the minimal moves required.

We flip the last three:

Move 4: Flip the last three (and none from the left).

And that gives us:

State 4: All glasses are upside-down.

The final state, our goal. It took four moves, and it turns out that it always takes as many moves as there are glasses. The pattern of moves may not be readily apparent in the small set of glasses above, so let’s consider some bigger sets of glasses.

§

Before I show you an example with ten glasses (N=10), consider the pattern in the examples above. As mentioned, the rule is to flip as many glasses on the right (starting from the right side) as are different from the glasses on the left. Since a move requires flipping N-1 glasses, flip as many glasses on the left (starting from the left side) as required to add up to N-1 glasses flipped.

On the first move, no glasses on the right are different, all the glasses are the same: upright. So, we flip zero glasses from the right and take all N-1 glasses from the left. Which is why we flip the left three glasses on the first move.

On later moves, there are glasses on the right that are different from glasses on the left — either being upright or upside down — so we flip all the glasses on the right that are different. Note how this grows from zero the first time to three the last time. Each move flips one more glass from the right and one less glass from the left.

On the final move, there are three (N-1) glasses on the right that are different from the one remaining glass on the left. So, this time we take all N-1 glasses there and zero from the left.

Lastly, note how flipping N-1 this means one glass is not flipped each move. That glass starts on the far right and moves one position left each move until it’s on the far left. You can think of the pattern as flipping all the glasses each move except for this lone moving glass.

Regardless of how you view the protocol, it takes N moves to flip N glasses.

§

With that in mind, here are the ten moves required to flip ten glasses:

The 10 Glasses Solution. [click for big]

To make the pattern a bit easier to see, the upright glasses are red, and the upside-down ones are blue. Note how the penultimate move has nine (N-1) glasses ready for the final move (and is symmetrical with the first move — in fact, there is a forward-backward symmetry through the entire progression).

Also note how you can always find a single lower glass that matches the glass above it — the one that didn’t get flipped.

§

For what it’s worth, the algorithm looks generically something like this:

--Glasses Puzzle Solver!

-- Start with the number of glasses...
N = 12

-- Define a row of N glasses...
Glasses = [0]*N

-- Print the starting position...
print(Glasses)

-- Function to flip a given glass...
function flip_glass (index) begin
    Glasses[ix] == not Glasses[ix]
end

-- Make N moves to turn all glasses upside-down...
for move = 1 to N begin

    -- Flip glasses on the right...
    if 1 < move then begin
        for right = 1 to move-1 begin
            flip_glass(N-right)
        end
    end

    -- Flip glasses on the left..
    if move < N then begin
    for left = 1 to N-move begin
        flip_glass(left)
        end
    end

    -- Print the move...
    print(Glasses)

--Done!
end

Which is basically the same protocol described above. Rather than actually examining the glasses on the right to see which ones differ from glasses on the left, the algorithm recognizes that the number of glasses flipped on the right starts with zero and grows to N-1 while the number of glasses flipped on the left starts with N-1 and decreases to zero.

In fact, it is that simple. On the right, start with zero (glasses flipped) and increase to N-1, one glass per move. On the left, start at N-1 (glasses flipped) and decrease to zero, one glass per move. These are exactly anti-symmetrical (one increases while the other decreases), and both require N moves.

§

That’s all there is for now. I’ll leave you with a 42-glass version:

Click for a 3360×5762-pixel version!

Stay flipped, my friends! Go forth and spread beauty and light.

∇