blind bartender

13 posts in this topic

Posted · Report post

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?
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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 by plasmid
1

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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 ??

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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 by BMAD
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.