17

I didn't invent this myself, I heard it a long time ago and it stuck with me.

Four glasses are placed on the corners of a square rotating table. Some of the glasses are facing upwards and some upside-down. Your goal is to arrange the glasses so that they are all facing up or all facing down. Here are the rules:

  1. You must keep your eyes closed at all times. (No tricks or lateral thinking, this is a pure logic puzzle)
  2. In a single turn, any two glasses may be inspected. After feeling their orientation, you may reverse the orientation of either, neither, or both glasses.
  3. After each turn, the table is rotated through a random angle.
  4. At any point, if all four glasses are of the same orientation a bell will ring.

Find a solution to ensure that all glasses have the same orientation (either up or down) in a finite number of turns. The algorithm must not depend on luck.

Edit: The bell will not ring mid-turn, it will only ring if the glasses are all of the same orientation at the end of your turn.

Dsel
  • 341
  • 2
  • 13
  • 1
    Is it allowed to choose between two orthogonal or diagonal glasses by feeling the edges and corners or remembering the length of a single edge and using it? – Nautilus Sep 02 '15 at 08:32
  • Or to feel the rotation itself? – Nautilus Sep 02 '15 at 08:47
  • Similar puzzle: http://puzzling.stackexchange.com/questions/43/ – f'' Sep 02 '15 at 11:14
  • If you choose to turn both glasses are they turned simultaneously? Or can you turn 1 glass, see if it wins, if not turn the other glass? – Ivo Sep 02 '15 at 14:46
  • 1
    Also, can you pick the second glass based on what you feel by inspecting the first? Or do you say which 2 you want to inspect before inspecting? – Ivo Sep 02 '15 at 14:54
  • @Nautilus No on both questions – Dsel Sep 02 '15 at 16:31
  • @IvoBeckers The bell alerting if you won or not will only ring at the end of a turn, I should have specified this but I'll edit the question now. As for your second question, you can pick the second glass to inspect after you have felt the first. – Dsel Sep 02 '15 at 16:34
  • @Dsel The rule "you can pick the second glass after feeling the first" seems to be rendered pointless by the rule "you can't tell the difference between diagonally opposed and adjacent glasses". If you can't tell the difference, then what information do you have that would allow you to distinguish between the glasses? You're just picking the first one at random, feeling it, and then picking one of the remaining three at random. – Jack M Sep 07 '15 at 12:00
  • Awww, I hate this. This is the 3rd question I almost asked.... – user21233 Sep 21 '16 at 18:34

3 Answers3

11

I have solution that can guarantee the end goal being reached in a maximum of four five steps. (Many thanks for @dmg and @Taemyr for their comments to fix this solution.) The trick is to:

Reduce the cups into the following configuration:
$\begin{bmatrix} \circ & \bullet \\ \bullet & \circ \end{bmatrix} $
where turning any two cups along the diagonal will satisfy the end goal

For a constructive proof, we first consider the following two three CASES:

CASE 1) the orientation of a single cup is different from the others, e.g. $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix} $ or $\begin{bmatrix} \bullet & \circ \\ \bullet & \bullet \end{bmatrix} $
CASE 2a) two cups are in each orientation along the diagonal, e.g. $\begin{bmatrix} \circ & \bullet \\ \bullet & \circ \end{bmatrix} $
CASE 2b) two cups are in each orientation along two sides, e.g. $\begin{bmatrix} \circ & \bullet \\ \circ & \bullet \end{bmatrix} $

Step 1

Take two cups along the diagonal.
- If they are different, flip $\circ$ to $\bullet$. If this doesn't sound the bell, we either have $\begin{bmatrix} \circ & \bullet \\ \bullet & \circ \end{bmatrix}$ or $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix}$, with the majority orientation being $\circ$. In either case, proceed to step 2.
- If they are the same, flip both. If this doesn't sound the bell, we either have $\begin{bmatrix} \bullet & \circ \\ \bullet & \bullet \end{bmatrix}$ or $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix}$. Either way, the majority orientation is known, and we can proceed to step 3.

Step 2

Take two cups along the diagonal.
- If they are different, we now know we have $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix}$. Flip $\bullet$ to $\circ$ to win.
- If they are the same, flip both. If this doesn't sound the bell, we now know we have $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix}$. Proceed to Step 3.

Step 3

At this point, we have already figured out what the majority orientation is, so we assume we have $\begin{bmatrix} \circ & \bullet \\ \circ & \circ \end{bmatrix} $ WLOG. Then:
Take two cups along the diagonal.
- If the cups are different, flip $\bullet$ to $\circ$ to win.
- If the cups are both $\circ$, flip one of them. We now know we have $\begin{bmatrix} \circ & \bullet \\ \circ & \bullet \end{bmatrix}$.

Step 4

Take two adjacent cups along an edge and flip both.
- If the cups chosen are the same, we win.
- If they are different, we now know we have $\begin{bmatrix} \circ & \bullet \\ \bullet & \circ \end{bmatrix} $

Step 5

Take two cups along a diagonal and flip both. We win!

Hackiisan
  • 1,806
  • 11
  • 25
  • 1
    It seems your initial assumption is wrong, there is a third case with two different "columns" or "rows" of glasses. – dmg Sep 02 '15 at 08:37
  • Oh! You are quite right. Fortunately, we can simply patch the above solution by extending the first "easy out" 2-step solution to be exactly symmetric with the 4-step solution. That is, for that branch, we either have $\begin{bmatrix} \circ & \bullet \ \bullet & \circ \end{bmatrix}$ or $\begin{bmatrix} \circ & \bullet \ \circ & \circ \end{bmatrix}$ with the majority orientation known. In either case, we can proceed to the worst case Step 2 in the solution above. – Hackiisan Sep 02 '15 at 08:48
  • Hmm, I'm not sure about the "majority orientation known" part. Could you elaborate a bit? It seems that in step 3 you are assuming that there are 3 whites and 1 black, but that is not necessary the case. – dmg Sep 02 '15 at 10:25
  • @dmg Re known majority oritentation: We know that there is at least 2 whites. Hench black can not be the majority orientation. – Taemyr Sep 02 '15 at 10:45
  • @dmg However I agree with you on that there is insufficent information to proceed. He seems to ignore the potential for a step one to produce a 2/2 split from step 2 on. – Taemyr Sep 02 '15 at 10:59
  • Great answer, my original solution to this puzzle required 5 moves in the worst case. However I believe yours does work contrary to what some of the comments say. For now you have my up-vote. Id like to see if @Taemyr or dmg can prove that this solution does not work. If they can't, and if a better answer isn't posted, you'll get the check. – Dsel Sep 02 '15 at 16:42
  • @dmg please see above, I couldn't tag you – Dsel Sep 02 '15 at 16:43
  • I think it takes five moves sometimes. If on your first turn you flip a single cup, you could be in the goal state (diagonals match) or the state with one cup different from the rest. How do you resolve this in 3 more moves? I.e. what do you do in step two when the diagonals match? The intsructions work for the other case (i.e. one cup different) but not for if the diagonals match. – Trenin Sep 02 '15 at 17:54
  • 1
    @Dsel $\begin{bmatrix} \circ & \bullet \ \circ & \circ \end{bmatrix} $ ->$\begin{bmatrix} \circ & \bullet \ \bullet & \circ \end{bmatrix} $->$\begin{bmatrix} \bullet & \bullet \ \bullet & \circ \end{bmatrix} $->$\begin{bmatrix} \circ & \bullet \ \circ& \circ \end{bmatrix} $->$\begin{bmatrix} \bullet & \bullet \ \circ& \bullet\end{bmatrix} $ This is fixable, but requires an extra step. I proposed an edit, but it was rejected. – Taemyr Sep 02 '15 at 18:07
  • @Taemyr I agree with you, thanks for pointing that out. Hopefully Hackiisan posts an edit – Dsel Sep 03 '15 at 00:47
  • @ Taemyr Thanks for the correction, I agree with you as well. Let's see if I can override the decision on your edit. – Hackiisan Sep 03 '15 at 01:09
1

Since at any turn, two glasses are inspected, the best bet would be to identify one corner and inspect the glass at that corner and the glass on its opposite corner.

Stick to one outcome, all up or all down (I am going ahead with downward arrangement). At the first turn, turn over any glass that isn't facing down. If the other two glasses are facing downward, then you're done.

After the table is then rotated randomly, repeat this process. If you find that the glasses you touch are already facing downward, it could be that you are touching the same glasses as before. Assuming that the rotations of the table are truly random, there is a 0.5 probability of picking one combination of glasses. The probability of touching the same two glasses each time is (0.5)n. So the probability of not having the glasses all down diminishes with each turn.

CodeNewbie
  • 11,753
  • 2
  • 45
  • 87
  • As far as i understand rule #2 is that you are allowed to change the orientation of 0 or 2 glasses in the process, not of 1. Have i misunderstood the rule? So if the glasses got different orientations you would run into a dead lock. – Wa Kai Sep 02 '15 at 07:03
  • @WaKai: you may reverse the orientation of either, neither, or both glasses. either (1 of 2), neither (0 of 2) or both (2 of 2) glasses. – CodeNewbie Sep 02 '15 at 07:05
  • Yep it seems I misunderstood it. Else it wouldn't be solvable for a 3:1 orientation at the beginning. – Wa Kai Sep 02 '15 at 07:12
  • Everything you said is accurate but I specified that the solution must solve the problem in a finite number of turns. – Dsel Sep 02 '15 at 16:47
-1

This solution is incorrect because it doesn't account for case 2b since flipping two diagonals of 2b causes it to remain the same orientation.

Therefore step 2 is an invalid assumption since the majority orientation is not the only possible outcome.

Solution is 6 steps.

  1. Two Diagonals
  2. Two Adjacent
  3. Two Diagonals (Flip 1 coin back if no bell)
  4. Two Diagonals
  5. Two Adjacent
  6. Two Diagonals

This now takes into account case 2b

Kevin
  • 1
  • 1
  • With the marked correct solution in the case of 2B, step 1) any diagonal you grab will lead you to the option of 3 in an L in one orientation and one remaining step 2) will then either win or lead to another 3 in an L and one remaining and continue through the steps to be solved – gabbo1092 Dec 06 '18 at 20:57
  • @Kevin Please hide your answers in spoilers. Also, this doesn't appear to ber an answer but rather a comment on another post. – rhsquared Dec 07 '18 at 04:33