@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.",
}