A polynomial insight for problem C, GCJ 1B 2022
Difference between en2 and en3, changed 0 character(s)
# The handless (blindfolded ?) barman and his prankster intern↵
![ ](/predownloaded/1d/6b/1d6bc808a97da6e1432378ecef23ec9594f3e20b.jpg)↵

## 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.↵

![ ](/predownloaded/10/75/10754c5c2e03fe4dcd38b444ad19c1d28f45919b.jpg)↵

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](https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd29b).↵

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 ?↵

<spoiler summary="Solution">↵
The barman use this simple strategy : he asks the intern to flip the set of positions where the glass are upside-down, until every glass is right side up.↵
We'll show that this strategy ends after at most $n$ rounds.↵

Let $A := F_2[X] / (X^n + 1)$.↵

We can model the state of the tray by a polynomial ↵
$$ a_1 + a_2 X + \dots + a_{n}X^{n - 1} \in A$$↵
where $a_i = 1$ if the glass in position $i$ is upside-down and $0$ otherwise.↵
A cyclic shift is the multiplication by a power of $X$, and a set of flips is the addition of a polynomial $Q$.↵

Let $P_0 \in A$ be the starting configuration.↵
We see that, when performing our simple strategy on round $i$, the configuration $P_i$ becomes $P_{i + 1} := (1 + X^{d_i})P_i$, where $d_i$ is the rotation chosen by the intern.↵

Thus, after $n$ rounds, the configuration is :↵
$$P_n = (X^{d_n} + 1) \dots (X^{d_2} + 1)  (X^{d_1} + 1)P_0$$↵
where $d_1, \dots d_n$ are the cyclic shifts indices. We have :↵
$$X^n + 1 = (X + 1)^n$$ ↵
because $n = 2^k$ and↵
$$X^{d_i} + 1 = (X + 1)(X^{d_i - 1} + \dots + X + 1)$$↵

Thus $X^n + 1 = (X + 1)^n$ divides $P_n$ : we have $P_n = 0$, and every glass is right-side up.↵
</spoiler>↵

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

<spoiler summary="Solution Overview">↵
The barman's strategy is `Solve(0)`, where :↵

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

We consider the injective function $f$ :↵
$$P \in A \mapsto (P, P (1 + X), P (1 + X)^2, \dots, P (1 + X)^{n - 1}) \in A^n$$↵
We remark that if we play $(1 + X)^i$ on configuration $P$, the polynomials $f(P)_{n - i}, \dots f(P)_{n - 1}$ do not change since, if $i + j \geq n$ :↵
$$f(P + X^d (1 + X)^i)_j = (P + X^d (1 + X)^i) (1 + X)^j = P (1 + X)^j + X^d (1 + X)^{i + j} = f(P)_j$$↵
Of course, $f(P)_{n - i}$ do change.↵

Thus, playing the $(1 + X)^i$ in a Grey-code way gives $2^n$ different images of $P$ through $f$, thus we explore each one of the $2^n$ configurations of $P$.↵

The $(1 + X)^i$ are in fact the rows of the Sierpinski triangle (Pascal triangle mod $2$).↵
</spoiler>↵

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. 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Arturgo 2022-05-04 16:48:27 0 (published)
en2 English Arturgo 2022-05-04 16:47:31 174
en1 English Arturgo 2022-05-04 16:46:20 4645 Initial revision (saved to drafts)