The handless (blindfolded ?) barman and his prankster intern

The problem

A handless barman has $$$n = 2^k$$$ glass placed in circle on a tray. Some of them are upside-down, some of them are right side up. He want every glass to be right side up, but he is handless. He needs the help of his intern. The barman can ask the intern to flip the glass in some set of positions. But the intern is a prankster ! He will rotate the tray (circularly shifting the positions of the glass) before performing the flips. The intern stops the game when every glass is right side up. Find a strategy for the barman to achieve this.

This problem can be instantiated in many ways, depending on the information the barman has (if he sees the glass / if he is totally blindfolded / if he knows the number of glass in right side up position).

You can see how it is linked with problem C of GCJ 2022 1B.

I want to add my polynomial point of view of this type of problem.

Solution when the barman isn't blindfolded

The barman sees the glass, how to solve the problem in $$$n$$$ rounds ?

Solution when the barman is blindfolded

The barman is blindfolded, how to solve the problem in $$$2^n - 1$$$ rounds ?

Solve(i) {
    if(i == n) return;
    Solve(i + 1)
    play (1 + X)^i
    Solve(i + 1);
}

I hope it's understandable. Of course, when we know more information, we can speed up this search by skipping sub-trees.

Generalizations

We can easily prove that when $$$n$$$ is not a power of $$$2$$$, the barman can't win. We can try to solve the problem with a group $$$G$$$ different than $$$\mathbb{Z} / n \mathbb{Z}$$$ (circular rotations) for the transformations performed by the intern : we want to study the nilpotent elements of the group algebra $$$F_2[G]$$$. For example, we can solve the problem on a giant tray, on which we have placed small trays in circle, on which we have placed the glass.

Fun story

Exactly three days before round 1B, I explained this polynomial approach to the Network and Optimization team in CWI. It's one of my favorite problems since it relates a combinatorics game with algebra and number theory. In fact, I have only presented the unblindfolded case to the N&O team, and only mentioned the blindfolded case. A member of the team did the GCJ 1B and was really frustrated of this :p He only told it to me today, it's why I come after the storm.