@Article{BarEtz93, author = "R. Bar Yehuda and T. Etzion and S. Moran", title = "Rotating-Table Games and Derivatives of Words", journal = "Theoretical Computer Science", volume = "108", pages = "311--329", year = "1993", abstract = "We consider two versions of a game for two players, $A$ and $B$. The game consists of manipulations of words of length $n$ over an alphabet of size $\sigma$, for arbitrary $n$ and $\sigma$. For $\sigma~=~2$ the game is described as follows: Initially, player $A$ puts $n$ drinking glasses on a round table, some of which are upside down. Player $B$ attempts to force player $A$ to set all the glasses in the upright position. For this, he instructs player $A$ to invert some of the glasses. Before following the instruction, player $A$ has the freedom to rotate the table, and then to inverts the glasses that are in the locations originally pointed by player $B$. In one version of the game player $B$ is blindfolded, and in the other he is not. We show that player $B$ has winning strategies for both games iff $n$ and $\sigma$ are powers of the same prime. In both games we provide optimal winning strategies for $B$. The analysis of the games is closely related to the concept of the $derivative$ of a $\sigma$-ary word of length $n$. In particular, it is related to the $depth$ of such word, which is the smallest $k$ such that the $k$-th derivative of the word is the all-zero word. We give tight upper bounds on the depth of $\sigma$-ary words of length $n$, where $\sigma$ and $n$ are powers of the same prime.", }