Can You Devise a Winning Strategy for This Blindfolded Cup Flipping Game?

[Ben1587]

1) There is a round table divided into 4 equal quadrants, with one cup in each quadrant. The quadrants are labeled with letters (A, B, C, D) that do not move. Initially, each cup is randomly face-up or face-down. You are blindfolded and put in front of the table. On each turn of the game, you instruct a genie to flip the cups in whichever positions you choose (e.g., you may say "flip the cups in A and B"), possibly choosing no cups or possibly all four. The genie complies. At this point, if all the cups on the table are face-up, the genie will tell you that you have won the game and are free to go. If not, he rotates the cups randomly (possibly not rotating them) and you play another turn. Give a strategy to win this game in a finite number of moves (the solution is not unique).

the outcome of "rotation" the four cups is one of the four possible positions: the cups originally at (A,B,C,D) can be at (A,B,C,D), (B,C,D,A), (C,D,A,B), or (D,A,B,C). It is not an arbitrary permutation.

2) Suppose that instead of 4, there are n divisions and cups. For which n is it possible to guarantee a win? Prove your answer is correct.

Any?
Thanks

 

[Wong]

this question seems difficult...oh I cannot come up with a solution but I would like to share some of my ideas.

One may represent the "state" of a cup by 1 or -1, with 1 meaning face up and -1 meaning face down. So the state of the four cups altogether may be represented by (-1^a, -1^b, -1^c, -1^d). Note that we may endow the state with a natural operation by *element-wise multiplication*. Note that this operation is equivalent to asking somebody to flip some of the cups. Under this operation the states form a group with identity (1, 1, 1, 1). If we assume that the genie performs no rotation throughout (this is essentially a much less complicated version), then the question becomes given an unknown state "a" we want to find p_n*p_n-1*...p_1*a such that at some point p_m-1...p_1*a = e, m<=n where e is the identity. But this is always possible because we may label the group element by k_1...k_n and let p_i = k_i*k^(-1)_(i-1). Then the inverse of "a" should be one the the k_i's and so at some point a should be reduced to the identity.

For the case with rotation, the argument I think would be much more involved...

 

[MathematicalPhysicist]

perhaps you should write down the situations you have for example:
(1-face up 0-face down)
A-1 B-1 C-1 D-0
A-1 B-1 C-0 D-0
A-0 B-1 C-0 D-0
A-0 B-0 C-0 D-0
let's say we start with D as the counter we first don't flip (im firstly tying to solve it without rotation) D only the other 3 and then C we don't flip only the othres:
A-0 B-0 C-0 D-0
A-0 B-0 C-1 D-0
A-1 B-0 C-1 D-0
A-1 B-1 C-1 D-0
now it's C's turn not to be flipped:
A-1 B-1 C-0 D-1
A-1 B-1 C-1 D-1
A-0 B-1 C-1 D-1
A-0 B-0 C-1 D-0
now B's turn (as you can see in the second case his already won the game):
A-0 B-1 C-1 D-0
A-1 B-1 C-0 D-0
A-1 B-0 C-0 D-0
now A:
A-0 B-0 C-0 D-1
A-1 B-0 C-1 D-1
A-1 B-1 C-1 D-1
as you can see the 2 and fourth sequence were finished after even times respectively because the number of 1's and 0's were even both.
now because we chose everyone of them to solve the other sequnces we need the number of moves to be odd greater than 4 (obviously) in the thith move we flip every one:
A-1 B-1 C-1 D-0
A-0 B-1 C-0 D-0
in the sixth move we flip D:
A-1 B-1 C-1 D-1
A-0 B-1 C-0 D-1
and in the last we seventh move we choose those who are even or odd places:
1) A-1 B-1 C-1 D-1
or 2) A-0 B-0 C-0 D-0
and in the eigth we flip them all once more.

now try to build a short strategy that will include them all and you answered it (i don't think the rotation changes the answer but i might be wrong ).

 

[Wong]

umm...I think you missed out one case i.e. A-1 B-0 C-1 D-0. You may not get it from A-1 B-1 C-0 D-0.

Also the gist of the problem is that we do *not* know the rotation in each turn (as we are blindfolded). So you may not control which *specific* cup to flip (cup A, B, C or D). So I think your answer does not work with rotations.

 

[NateTG]

On notation: it's easy enough to read A as face up, a as face down. So that ABCD is the desired state and abcd is all cups face down.

Also:
Can you handle 1, 2 or 3 cups?

It may be beneficial to assume a sadistic rotation rather than a random one since they are effectively the same.

Technically, as the problem is written, you can simply look at the table, identify which cups to flip, and win in the first round, since the blindfold is put on after the cups are arranged.

Otherwise here is an answer:

Flip none,
flip all,
flip A and C,
flip all,
flip A and B,
flip all,
flip A and C,
flip all,
flip A,
flip all,
flip A and C,
flip all,
flip A and B,
flip all,
flip A and C,
flip all.

 

[Ben1587]

The 2nd part of the question is where I'm having difficulties

 

[NateTG]

The 2nd part of the question is where I'm having difficulties

Can you prove that the answer I gave above works?
Can you prove that odd numbers > 1 are impossible?

 

[Wong]

On notation: it's easy enough to read A as face up, a as face down. So that ABCD is the desired state and abcd is all cups face down.

Also:
Can you handle 1, 2 or 3 cups?

It may be beneficial to assume a sadistic rotation rather than a random one since they are effectively the same.

Technically, as the problem is written, you can simply look at the table, identify which cups to flip, and win in the first round, since the blindfold is put on after the cups are arranged.

Otherwise here is an answer:

Flip none,
flip all,
flip A and C,
flip all,
flip A and B,
flip all,
flip A and C,
flip all,
flip A,
flip all,
flip A and C,
flip all,
flip A and B,
flip all,
flip A and C,
flip all.

You are great! I checked your answer and found that no "sub-chains" inside your chain of actions multiply to give an identity. It really "generates" the whole 16 possible configurations of the cups irrespective of rotations!

How did you think of that? Did you think of the answer immediately because of your cleverness, or is it some related to some theories in mathematics?

When I first think about the question, I classify the actions into different classes, where actions related by a rotation are identified. (i.e. flip AB is the same as flip BC, flip AC the same as flip BD). Then I try to form a "multiplcation table" (not the same as that in algebra) to see what action(s) is/are equivalent to a combination of two actions (i.e. [flip A refers to the class "identified" by rotations, so {flip A} = {flip D}] flip A then flip AB would be either equivalent to flip A or flipABC. Flip A then flip all is equivalent to flip ABC). Then the question becomes is it possible to construct a "chain" of actions of length 2^4 such that no sub-chain would multiply to give an identity? (that is all the possible configurations would be realized)

That are some of my silly ideas. May you please give me some hints about what motivates you to construct the answer?

 

[MathematicalPhysicist]

umm...I think you missed out one case i.e. A-1 B-0 C-1 D-0. You may not get it from A-1 B-1 C-0 D-0.

Also the gist of the problem is that we do *not* know the rotation in each turn (as we are blindfolded). So you may not control which *specific* cup to flip (cup A, B, C or D). So I think your answer does not work with rotations.

i know that my answer isn't complete as nate put the correct answer, but as i assumed you only need to consider these four possibilities and that the rotation doesn't affect the situation that those cups' state doesn't change their place does but you don't need to consider it.

 

[NateTG]

That are some of my silly ideas. May you please give me some hints about what motivates you to construct the answer?

Well, since the process must be guaranteed to terminate, you can assume a sadisitc rotation. Then I tried to prove that is was impossible to solve the problem, but failed in some edifying ways...

Which led to a case-by-case solution:
I split the situation into six cases:
A rotation of ABCD
A rotation of abcd
A rotation of Abcd
A rotation of AbCd
A rotation of ABcd
and
A rotation of ABCd

and eliminated the ones that were easy to deal with.

In retrospect, it's more elegant to look at it as:
The starting position is one of the following cases, in order of increasing difficulty.
A rotation of ABCD (1)
A rotation of abcd (1)
A rotation of AbCd (2)
A rotation of ABcd (4)
A rotation of ABCd or Abcd (8)

If you keep track of what happens to the cases as the process goes on, you might notice a pattern.

 

[Ben1587]

The answer to part one is right. I verified that with my teacher. Still confused about the 2nd part.

 

[Wong]

Well, since the process must be guaranteed to terminate, you can assume a sadisitc rotation...

What do you mean by a "sadistic rotation"? In my mind I always think that since the genie performs a random rotation at each step, that if you ask the genie to "flip AB" he might as well flip BC, flip CD, or flip DA because of the random rotation (given that the cups are labelled such that their labels do not change even when their positions are changed by a rotation).

Would you please explain what do you mean by "a sadistic rotation" and how it simplifies matters?

 

[NateTG]

Would you please explain what do you mean by "a sadistic rotation" and how it simplifies matters?

Sometimes it's easier to think of the worst possible rotation instead of all rotations. It helps my thought process.