Logic Puzzle: Inverting the glasses

Four glasses are placed on the four corners of a square rotating table. Each glass is either upright (up) or upside-down (down). You have to turn all the glasses in same direction (either all up or all down). There are following conditions

1. You are blindfolded,
2. At one time you can only change two glasses (and you cannot touch other two glasses).
3. The table spins after each time you change the glasses.

When all the glasses comes in one direction, then a bell rings and the game stops?

Solution:

Following steps can confirm that all the four glasses will be in the same direction.
Step-1: Choose a diagonally opposite pair of glasses and turn both glasses up.
Step-2: Choose two adjacent glasses and if one of them is down then turn it up (the other one is already up as a result of the previous step). So both the adjacent glasses that we have chosen are up now.

If the bell does not ring then the fourth glass (not touched in step-1 and step-2) is down.

Step-3: Choose a diagonally opposite pair of glasses.

• If one of them is down then turn it up and the bell will ring (because only one glass was down from step-2).
• If both are up, then turn one of the two glasses down.

Now two out of four glasses are down, and both of them must be adjacent. So the situation is that out of four glasses 2 adjacent glasses are up and other 2 are adjacent glasses are down.

Step-4: Choose two adjacent glasses.

• If both of them are down, make them up and the bell will ring (because other two are also up).
• If both of them are up, make them down and the bell will ring (because other two are also down).
• If both are in opposite direction, then reverse these direction (the one that is up, make it down and vice-versa).

Now out of the 4 glasses 2 opposite are in up direction and two opposite are in down direction.

Step-5: On the fifth turn choose a diagonally opposite pair of glasses and reverse both. The bell will ring for sure.
Hence, we are able to solve the problem in a finite number of steps deterministically.
Variation-1:

The interviewer may ask you whether you can generalize the solution for n glasses (by moving 2 glasses at a time).

If n=2, it is trivial and can be solved in one step.

If n=3,  we can solve the problem in 2 steps (pick two adj. glasses and turn both of them up, if bell does not ring then in second step pick 2 adj. glasses again, if one of them is down then turn it up and bell will ring, if both of them are up then turn both of them down and the bell will ring)

For five or more glasses there is no algorithm that guarantees the bell will ring in a finite number of turns.

Variation-2:

A further variation can be that instead of 2 you can examine k glasses out of n.

I leave it to you to solve it 🙂

Wiki says: An algorithm can be found to ring the bell in a finite number of turns as long as k ≥ (1 − 1/p)n where p is the greatest prime factor of n.