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