16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Nautilus Sep 2 '15 at 8:32
  • $\begingroup$ Or to feel the rotation itself? $\endgroup$ – Nautilus Sep 2 '15 at 8:47
  • $\begingroup$ Similar puzzle: puzzling.stackexchange.com/questions/43 $\endgroup$ – f'' Sep 2 '15 at 11:14
  • $\begingroup$ 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? $\endgroup$ – Ivo Beckers Sep 2 '15 at 14:46
  • $\begingroup$ 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? $\endgroup$ – Ivo Beckers Sep 2 '15 at 14:54
11
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ It seems your initial assumption is wrong, there is a third case with two different "columns" or "rows" of glasses. $\endgroup$ – dmg Sep 2 '15 at 8:37
  • $\begingroup$ 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. $\endgroup$ – Hackiisan Sep 2 '15 at 8:48
  • $\begingroup$ 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. $\endgroup$ – dmg Sep 2 '15 at 10:25
  • $\begingroup$ @dmg Re known majority oritentation: We know that there is at least 2 whites. Hench black can not be the majority orientation. $\endgroup$ – Taemyr Sep 2 '15 at 10:45
  • 1
    $\begingroup$ @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. $\endgroup$ – Taemyr Sep 2 '15 at 18:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wa Kai Sep 2 '15 at 7:03
  • $\begingroup$ @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. $\endgroup$ – CodeNewbie Sep 2 '15 at 7:05
  • $\begingroup$ Yep it seems I misunderstood it. Else it wouldn't be solvable for a 3:1 orientation at the beginning. $\endgroup$ – Wa Kai Sep 2 '15 at 7:12
  • $\begingroup$ Everything you said is accurate but I specified that the solution must solve the problem in a finite number of turns. $\endgroup$ – Dsel Sep 2 '15 at 16:47
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – gabbo1092 Dec 6 '18 at 20:57
  • $\begingroup$ @Kevin Please hide your answers in spoilers. Also, this doesn't appear to ber an answer but rather a comment on another post. $\endgroup$ – rhsquared Dec 7 '18 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.