Pay Lives to Touch Glasses
Here is one of my all-time favorite problems.
Puzzle. Four glasses are placed on the four corners of a square rotating table; each glass is either right-side up or upside down. You need to turn them all in the same direction, either all facing up or all down. You may do so by grasping any two glasses and turning either none, one of them, or both over.
There are two catches: 1) You are blindfolded, and 2) the table is spun after each round. Assuming a bell rings when you have them all facing the same way, how do you do it?
When I first heard this problem, the person who tortured me with it forgot to mention the bell. The problem was impossible: there was no feedback. Then, the bell was mentioned. It was an aha moment: you get information, but only a confirmation that the problem is solved. I tried to think about the puzzle backwards. What could be my last step? Assume that I know that the glasses alternate around the table: up, down, up, down. Then, as my last step, I can reach for the diagonal glasses and turn them over.
This is how you might start thinking about this puzzle. You can find the rest of the solution on the puzzle’s Wikipedia page.
Here is a wonderful variation, proposed by Michael Hotiner from Ukraine, that appeared ten years ago at a puzzle competition. This variation is not cheap; the players must pay with their lives, albeit virtual ones.
Puzzle setup. Consider a computer game where at level M, there is an M-sided rotating table with glasses at each corner. The setup is similar to the four-glasses puzzle above. The player is blindfolded, and the table rotates between rounds. As soon as level M is over, if all the glasses face one direction, the bell rings, and the player moves to the next level, M+1.
At each round, the player can decide on the number N of glasses to touch. Upon deciding, they have to pay N! lives for that round. Then, the player can touch the glasses one by one, choosing the next glass depending on how the previous glasses are oriented. After all the glasses are touched, the player can decide which ones to turn upside down.
Let’s see what happens at the very beginning of this game. The game starts at level 1, with only one glass. The round is solved before it starts. The cost is 0. The bell rings, and the game immediately goes to level 2.
Consider level 2. If the bell doesn’t ring immediately, the glasses face different directions. The cheapest way to proceed is to choose N = 1 and turn any glass. The cost is 1.
Consider level 3. A player can solve it in one round by touching all three glasses and turning them the same way. The cost is 3! = 6. There is a cheaper method that costs 4 lives in two rounds. In the first round, the player can touch any two glasses and turn both of them up. If the bell doesn’t ring, then the third glass is upside down. In the next round, the player can touch two glasses. If one is upside down, that glass should be turned up. If both glasses are right side up, then the player should turn both of them over to finish the round.
Share:Puzzle tasks.
- Find a way to pass level 3 using only three lives.
- Find the cheapest way to pass level 4.
- Find the cheapest way for level 6.
- Find a way to pass level 5 using only 30 lives.
Sanandan Swaminathan:
Interesting puzzles. Let U denote a glass facing up, and D denote a glass facing down.
1) Find a way to pass level 3 using only three lives.
If the three glasses were UUU or DDD, the bell would ring immediately with no lives lost. If the bell doesn’t ring, it means that the glasses are in state UUD, UDU, DUU, DDU, DUD or UDD. For the first round, choose N = 1. Touch any one glass, and flip it (up to down or down to up). The state transition would be as follows:
UUD would become UUU or UDD or DUD depending on which single glass we touched (and compulsorily flipped).
UDU -> UDD or UUU or DDU.
DUU -> DUD or DDU or UUU.
DDU -> DDD or DUU or UDU.
DUD -> DUU or DDD or UUD.
UDD -> UDU or UUD or DDD.
If the state transitioned to UUU or DDD, the bell would ring, and we would pass level 3 having used up 1! = 1 life. If the bell doesn’t ring, the list of the state transitions after the first round can be whittled down to the following:
UUD -> UDD or DUD
UDU -> UDD or DDU.
DUU -> DUD or DDU.
DDU -> DUU or UDU.
DUD -> DUU or UUD.
UDD -> UDU or UUD.
Notice in the above list that, if the state before the first round had two U’s and one D, and we flipped a U to D, then the state necessarily changes to two D’s and one U. If we had flipped the single D to U, the bell would have rung. Similarly, if the state before the first round had two D’s and one U, and we flipped a D to U, then the state necessarily changes to two U’s and one D (if we had flipped the single U to D, the bell would have rung). So, if we flipped a U to D and the bell did not ring, we know that we now have two D’s and a U. if we flipped a D to U and the bell did not ring, we know that we now have two U’s and a D.
We can leverage these facts and choose N = 2 for the second round. Touch any two glasses. If they are both U’s, flip them to D’s to get DDD (and the bell will ring). If they are both D’s, flip them to U’s to get UUU. If they are UD or DU, and we had flipped the single glass in the first round from U to D, then change the two glasses just touched from UD or DU to DD. On the other hand, if we had flipped the single glass in the first round from D to U, then change the two glasses just touched from UD or DU to UU. Bell will ring.
Thus, at most we would lose 1! + 2! = 3 lives to pass level 3.
21 February 2023, 4:55 amSanandan Swaminathan:
2) Find the cheapest way to pass level 4.
I can see a way to pass level 4 with a max cost of 8. In the original 4-glass puzzle, it’s permissible to choose “diagonally opposite” glasses for examination. In this puzzle, it is unclear how a blindfolded person will actually touch “diagonally opposite” glasses without running the risk of accidentally touching an “adjacent” glass. The puzzle does say that “the player can touch the glasses one by one, choosing the next glass depending on how the previous glasses are oriented”. So, as in the original problem, I will assume that there is a way, perhaps by instructing the computer that we would like to touch any one glass, and then skip one glass in the clockwise direction and touch the next glass (or some such way to touch diagonally opposite glasses).
Consider a cycle notation for the four glasses, for example UDUD, where the directions of the glasses are marked in clockwise order. If the four glasses were UUUU or DDDD to start with, the bell would ring immediately, and we would pass level 4 with no lives lost. If not, for the first round, choose N = 2. Touch any one glass, and then touch the diagonally opposite glass (skip one glass in the clockwise direction from the first glass touched).
Case a) If the diagonally opposite glasses touched are UU, then flip them to DD. If the other two glasses happen to be DD, we get DDDD and the bell will ring. If not, then the other two glasses are UD or DU (but not UU since that would mean that the initial state was UUUU and the bell would have rung before the first round). We now have a cycle containing three D’s and a U. For the second round, choose N = 3. Touch any three consecutive glasses. If we touch three D’s, flip them all to U’s to get UUUU. If we touch two D’s and a U, flip the single U to D to get DDDD. Either way, the bell will ring.
Case b) Similarly, if the diagonally opposite glasses touched are DD, then flip them to UU. If the other two glasses happen to be UU, we get UUUU and the bell will ring. If not, then the other two glasses are UD or DU (but not DD since that would mean that the initial state was DDDD and the bell would have rung before the first round). We now have a cycle containing three U’s and a D. For the second round, choose N = 3. Touch any three consecutive glasses. If we touch three U’s, flip them all to D’s to get DDDD. If we touch two U’s and a D, flip the single D to U to get UUUU. Either way, the bell will ring.
Case c) If the diagonally opposite glasses touched in first round are UD or DU, make them UU. If the other two glasses happen to be UU, the bell will ring. If not, we necessarily now have a UUUD or a UDUD cycle. For the second round, choose N = 3. Touch any single glass. If it is D, touch the diagonally opposite glass. If that is also D, then we are in a UDUD cycle, so flip both the touched D’s to U’s to get UUUU. If the diagonally opposite glass is U, then we are in a UUUD cycle, so flip the touched D glass to U to get UUUU. On the other hand, if the first glass touched was U, touch its two neighboring/adjacent glasses (on its right and left). If the neighboring glasses are UU, it means we have a UUUD cycle, so flip all three U glasses touched to D to get DDDD. If the neighboring glasses are DD, it means we have a UDUD cycle, so flip the two neighbors (DD) to UU to get UUUU. If the neighboring glasses are UD or DU, it means that we have a UUUD cycle, so flip the D neighbor to U to get UUUU. In all cases, the bell will ring.
Thus, at most we would lose 2! + 3! = 8 lives to pass level 4.
21 February 2023, 11:59 amGennardo:
I’m struggling with the 5 glasses puzzle. The (only possible ??) idea to solve it is to
invest 6 lifes to get 4 of the 5 glasses in the same direction and then giving 24 lifes to touch 4 glasses in the last move.
If the outsider glass is among the four turn it and the bell will ring. If it is not among the 4 glasses turn
all 4 glasses and the bell will ring.
But how can you get 4 glasses in the same direction with 6 lifes ? Touching 1 glass is pointless even as a first move.
So your first (and second but last) move can be touching 3 glasses or you can make 3 moves with touching 2 glasses each.
If you touch 3 glasses and find DDU can you turn then in a way that guarantees 4 glasses in one direction after this move ? No.
So lets try 3 moves with touching 2 glasses. First take two adjacent glasses and make them take the same direction
lets say UU. As a second move take 2 non-adjacent glasses. If they are UU leave anything as it is, if they
are UD turn the D-glass. (if they are DD turn both and you’re done with
28 lifes, but we are in a worst-case scenario) Now you have at least 3 U-glasses because you know you haven’t
touch at least one of the glasses of the first move in the second move. You can have UUUDD or UUDUD but you can already have
undetected 4 U glasses. In the 3rd move you touch 2 glasses again. If they are DD or UD you’re fine. But if they are
UU you can’t do anything reagardless which glasses you took. But can’t you turn these glasses to get
4 D-glasses which would be sufficient? No, because you could have had – undedectable – 4 U-glasses after move 2.
Can you please post the solution here if no one else finds it ?
28 February 2023, 3:19 pmCyberK:
@Gennardo
You might be stuck for the same reason I was – at some point I arrived at a rigorous proof that it can’t be done in 30 lol.
Then I started reading the problem again, I did notice “one by one” from the start and found it a bit weird – once you select which N glasses you will touch, what does it matter in which order you do it since you don’t flip until touching all of them.
But this is where I went astray – you don’t decide the set of N glasses – you just decide on the number N, and which exact glasses you choose can be different depending on what orientation you found the previous one(s) as you go.
I will give a sketch below, I don’t know if there are spoiler tags here, you may want to go back to it before reading below. Frankly, once I realized I need to make use of the above subtlety, it didn’t take me that long to get to the solution.
Also, I don’t think it’s completely pointless to choose 1 glass – similar to solution for problem 1, at the start it could be 1U+4D, 2U+3D, 3U+2D, 4U+1D. If you pick one and it’s D, flip it to U. If the bell doesn’t ring, then 1U+4D is no longer possible, so you do have smaller state space than before.
Another thing, even if you have to preselect which N glasses will be checked and not just a number N, you don’t need to have 4 in the same orientation – if you can determine exactly whether it’s 1U+4D, 2U+3D, 3U+2D, 4U+1D, you can always solve it by choosing any 4 points, the count will tell you what the 5th one must be and you can flip those 4 to be the same. But there’s also no way to know the exact “config” i.e. how many Us and how many Ds in 6 lives.
As for the solution I have – you can do it with selecting 3 and then 4 for a total of 3! + 4! = 30 lives.
2 March 2023, 11:36 pmIn the first round you do 3 glasses, take any 2 adjacent + the only glass non-adjacent to both of them. In this round it’s not important to go one by one. Flip them to all to the same orientation, U or D, doesn’t matter. Let’s say U. After the first round you must have 3U + 2D or 4U + 1D, and the 2 “questionable” glasses are not adjacent to each other. Well, assuming the bell didn’t ring.
In the second round you select 4 as the number of glasses. Start with a random glass – as long as you hit U, just move to the adjacent glass, say clockwise.
If you hit D in the 1st or 2nd inspection, then you only need to check the two nonadjacent glasses and you have enough inspections left. One of them might also be D and you need to flip them to U and the bell will ring.
If you hit D in the 3rd inspection, you already checked one of the nonadjacent in the first inspection, so check the only other nonadjacent, you still have one check left unused. Same as finding D in checks 1 and 2 – you will have one or two Ds that you need to flip to U and the bell will ring.
Notice that you need to hit one of the “questionable” glasses after round 3 in at most 3 checks. So if in the first 3 checks they were all U, that means one of the questionable ones is also U, i.e. you had 4U + 1D. Check the 4th glass, at this point it doesn’t matter which, if it is D, flip it to U and the bell will ring, and if it is U, then the only D is the uninspected one that you can’t touch, so you need to flip all 4 inspected ones from U to D and the bell will ring.
Gennardo:
@ CyberK,
thank you for the solution, you were right, I hadn’t read all conditions before my posting but I read it afterwards. But I still didn’t find a solution.
Here is a solution with 3! + 5! = 126 lives for n=6 (just noticed that the plural ot life ist lives not lifes :-). First touch 3 glasses that form an equilateral triangle and turn them to U. If the bell doesn’t ring, you have either 3-D glasses in an equilateral triangle or 2-D glasses non-opposite and non-adjacent or 1-D glass. As a second move touch up to 3 adjacent glasses. If one of then is D touch the 2 other glasses that form an equilateral triangle. Then you have touched all D-glasses (could be 1, 2 or 3) with at most 5 moves. Turn them and the bell will ring. If all of the 3 glasses are U touch a 4th adjacent glass. If it is D there is only one glass among the two untouched glasses left which can be D. Touch it and turn the one or two D-glass(es) you get and the bell will ring. If the 4th glass is U again there is only one D glass. Touch a 5th glass and turn it if it is D and the bell will ring. If it’s U again turn all the 5 U-glasses and the bell will ring.
Is it always necessary to touch (n-1) glasses in the last step ? I think the answer is yes if you don’t know if you have one or more “outsider” glasses before the last move. Less touches would be necessary if you know you have exactly 2 outsider glasses left in a certain postion but I dont know if you can enforce this.
6 March 2023, 10:48 pmCyberK:
I also got 3!+5! as the best solution for 6, it’s similar to yours and basically a fairly straightforward generalization of my solution for 5 above.
In fact, it’s not hard to generalize my solution for 5 to any M to get a guaranteed cost of (ceiling(M/2))! + (M-1)!
I also don’t see a way of using less than M-1 in the last step – say one uses M-2, you would somehow need to get into a state where those 2 glasses you end up not selecting in the last round must be in the same (and known!) direction and I haven’t figured out a way of accomplishing that by limiting myself to <= M-2 in every round.
7 March 2023, 11:23 amI haven't given it that much thought so I can't rule out that it's not possible either, so the best I have is my upper boundary of (ceiling(M/2))! + (M-1)!.