blind bartender

[BMAD]

The following game is played between a customer and a bartender. The customer places four glasses on a revolving tray, arranged in a circle. Each glass is either right-side-up or upside down. The bartender is blindfolded and cannot see which way the glasses are placed, but the goal is to turn all the glasses the same direction.

In each round, the tray is spun, and the bartender is allowed to touch only two glasses, turning over either or both of them. But the bartender does not know the orientation when he touches his glasses. After each round, the bartender is told if all glasses are oriented the same and the game is over. What is the best strategy for the bartender? Is there a maximum number of moves, after which the bartender can be certain all the glasses are identically oriented?

[plasmid]

Very neat problem. The answer is certainly unintuitive.

There are three possible orientations that the glasses could be in that will not end the game.

DIAGONALS) Two glasses that are diagonal from each other are in one orientation, and the two other glasses that are diagonal from each other are in the other orientation.

ADJACENTS) Two glasses that are next to each other are in one orientation, and the two other glasses are in the opposite orientation.

SINGLETON) One glass is in one orientation and three glasses are in the opposite orientation.

We can therefore describe the game as in one of three states: state DIAGONALS, state ADJACENTS, or state SINGLETON.

By turning over one (random) glass, the bartender will....

... if it's in state DIAGONALS, switch it to state SINGLETON.

... if it's in state ADJACENTS, switch it to state SINGLETON.

... if it's in state SINGLETON, switch it to state DIAGONALS or state ADJACENTS or win.

By turning over two glasses that are adjacent to each other, the bartender will...

... if it's in state DIAGONALS, switch it to state ADJACENTS.

... if it's in state ADJACENTS, switch it to state DIAGONALS or win.

... if it's in state SINGLETON, keep it in state SINGLETON.

By turning over two glasses that are diagonal from each other, the bartender will ...

... if it's in state DIAGONALS, definitely win.

... if it's in state ADJACENTS, keep it in state ADJACENTS.

... if it's in state SINGLETON, keep in in state SINGLETON.

Now for the solution

1) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

If you were in state ADJACENTS before this move, you will stay in state ADJACENTS.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

2) Turn over two adjacent glasses

You could not be in state DIAGONALS before this move (all prior scenarios would leave you in state ADJACENTS or SINGLETON).

If you were in state ADJACENTS before this move, you will go to state DIAGONALS or win.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

3) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

You could not be in state ADJACENTS before this move.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

4) Turn over one glass.

You could not be in state DIAGONALS before this move.

You could not be in state ADJACENTS before this move.

Since you must be in state SINGLETON before this move, you will go to state DIAGONALS or ADJACENTS.

5) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

If you were in state ADJACENTS before this move, you will stay in state ADJACENTS.

You could not be in state SINGLETON before this move.

6) Turn over two adjacent glasses

You could not be in state DIAGONALS before this move.

If you were in state ADJACENTS before this move, you will go to state DIAGONALS or win.

You could not be in state SINGLETON before this move.

7) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

You could not be in state ADJACENTS before this move.

You could not be in state SINGLETON before this move.

Edit: renamed states for clarity

Edited September 30, 2013 by plasmid

[superprismatic]

If he always picked two glasses which have one between them (diagonally opposite glasses if the are arranged 90 degrees apart) and turns them both over, then he will always accomplish the task in two moves.

[phil1882]

let's say the arrangment is

u

u d

d

if the bartender flips top an bottom, that gives

d

u d

u

and then if he does the other diagonal, that gives.

d

d u

u

[phil1882]

rotate between one random cup, and flipping both of diagonal cups.

let's say the customer knows the bartenders strategy, and wants to keep the game going.

customer starts

u

u d

d

bartender flips one random.

u

u d

u

customer keeps orentation as is., bartender flips top and bottom.

d

u d

d

customer moves the up cup to the top.

u

d d

d

now bartender has 1/4 chance of winning this turn, and 1/4 chance of setting himself up to win next turn.

this would be the worst case scenario.

[superprismatic]

let's say the arrangment is

u

u d

d

if the bartender flips top an bottom, that gives

d

u d

u

and then if he does the other diagonal, that gives.

d

d u

u

I took the statement " Each glass is either right-side-up or up side down" to mean that all the glasses were all in the same orientation to start with. I thought it must have been there to emphasize that no glasses where placed on their sides, which would, of course, be stupid. But, that makes it too easy, I suppose. I haven't yet considered the case where of an arbitrary beginning setup. Thanks for pointing that out, phil.

[BMAD]

let's say the arrangment is

u

u d

d

if the bartender flips top an bottom, that gives

d

u d

u

and then if he does the other diagonal, that gives.

d

d u

u

I took the statement " Each glass is either right-side-up or up side down" to mean that all the glasses were all in the same orientation to start with. I thought it must have been there to emphasize that no glasses where placed on their sides, which would, of course, be stupid. But, that makes it too easy, I suppose. I haven't yet considered the case where of an arbitrary beginning setup. Thanks for pointing that out, phil.

If all the glasses were already in the same orientation (all up or all down), the game would be over before it started.

[superprismatic]

let's say the arrangment is

u

u d

d

if the bartender flips top an bottom, that gives

d

u d

u

and then if he does the other diagonal, that gives.

d

d u

u

I took the statement " Each glass is either right-side-up or up side down" to mean that all the glasses were all in the same orientation to start with. I thought it must have been there to emphasize that no glasses where placed on their sides, which would, of course, be stupid. But, that makes it too easy, I suppose. I haven't yet considered the case where of an arbitrary beginning setup. Thanks for pointing that out, phil.

If all the glasses were already in the same orientation (all up or all down), the game would be over before it started.

But I assumed that the bartender had to change at least one glass on his first move. Then the spin would cause a problem for him.

[DeGe]

The bartender uses a simple logic: If the numbers of upsides/downsides are odd, then invert 1 glass otherwise invert 2 glasses

So if the configuration is 1-3 or 3-1 up-down, he inverts one glass

If the configuration is 2-2 he inverts 2 glasses

The glasses he selects to invert is either G1 (for odd configuration) or G1 and G2 (for even configuration) after each rotation

G1

G4 G2

G3

By doing so, in 1-3 configuration, he will either make the config 4-0 or 2-2 after the first rotation with a probability of 25% and 75% respectively.

Then each time, he inverts the glasses when they are in an even configuration, the new configuration would be 4-0; or remain 2-2 (with the new configuration as u-u-d-d or u-d-u-d). He has 1/2 probability of making it a 4-0 configuration if the previous configuration was uudd and 0 probability if it was udud.

Effectively, after every alternate inversion of even glasses, he will have 50% probability of making it 4-0.

[radio1]

Very neat problem. The answer is certainly unintuitive.

There are three possible orientations that the glasses could be in that will not end the game.

DIAGONALS) Two glasses that are diagonal from each other are in one orientation, and the two other glasses that are diagonal from each other are in the other orientation.

ADJACENTS) Two glasses that are next to each other are in one orientation, and the two other glasses are in the opposite orientation.

SINGLETON) One glass is in one orientation and three glasses are in the opposite orientation.

We can therefore describe the game as in one of three states: state DIAGONALS, state ADJACENTS, or state SINGLETON.

By turning over one (random) glass, the bartender will....

... if it's in state DIAGONALS, switch it to state SINGLETON.

... if it's in state ADJACENTS, switch it to state SINGLETON.

... if it's in state SINGLETON, switch it to state DIAGONALS or state ADJACENTS or win.

By turning over two glasses that are adjacent to each other, the bartender will...

... if it's in state DIAGONALS, switch it to state ADJACENTS.

... if it's in state ADJACENTS, switch it to state DIAGONALS or win.

... if it's in state SINGLETON, keep it in state SINGLETON.

By turning over two glasses that are diagonal from each other, the bartender will ...

... if it's in state DIAGONALS, definitely win.

... if it's in state ADJACENTS, keep it in state ADJACENTS.

... if it's in state SINGLETON, keep in in state SINGLETON.

Now for the solution

1) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

If you were in state ADJACENTS before this move, you will stay in state ADJACENTS.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

2) Turn over two adjacent glasses

You could not be in state DIAGONALS before this move (all prior scenarios would leave you in state ADJACENTS or SINGLETON).

If you were in state ADJACENTS before this move, you will go to state DIAGONALS or win.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

3) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

You could not be in state ADJACENTS before this move.

If you were in state SINGLETON before this move, you will stay in state SINGLETON.

4) Turn over one glass.

You could not be in state DIAGONALS before this move.

You could not be in state ADJACENTS before this move.

Since you must be in state SINGLETON before this move, you will go to state DIAGONALS or ADJACENTS.

5) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

If you were in state ADJACENTS before this move, you will stay in state ADJACENTS.

You could not be in state SINGLETON before this move.

6) Turn over two adjacent glasses

You could not be in state DIAGONALS before this move.

If you were in state ADJACENTS before this move, you will go to state DIAGONALS or win.

You could not be in state SINGLETON before this move.

7) Turn over two diagonal glasses.

If you were in state DIAGONALS before this move, you will win.

You could not be in state ADJACENTS before this move.

You could not be in state SINGLETON before this move.

Edit: renamed states for clarity

Hmmm... does your "checkmate in 7" work if all four glasses are initially in the same state, or would that make it a "checkmate in 8", or ??

[phil1882]

if all 4 glasses are up or all 4 down, the game is over at the start.

[radio1]

if all 4 glasses are up or all 4 down, the game is over at the start.

I see from BMAD's earlier respose that this is his intended interpretation, but to me the wording of the puzzle doesn't make that clear. As stated, the puzzle seems to have the bartender blindfolded and engaged in a minimum of one "round" of turning over either 1 or 2 glasses, as only "After each round, the bartender is told if all glasses are oriented the same and the game is over.".

Fun puzzle though either way -- and the logic in plasmid's solution extends to either interpretation.

Thanks to all.

-radio1

[BMAD]

Nice point radio1. I guess the question would be, would the start of round 1 mean the end of round zero and hence the bartender would be told that the glasses are not all in the same orientation. or would the start of round 2 be the first time the bartender is informed.

To me, in a practical sense, i would tell the bartender that i am mixing up four glasses and he will have to correctly orient them while blindfolded (telling him the rules of the game), so essentially, i am telling him at round zero that the glasses are not in the same orientation.

But either way, you are right in that Plasmid's solution still works.

Edited October 2, 2013 by BMAD