# Technical Report CS0675

 TR#: CS0675 Class: CS Title: ROTATING-TABLE GAMES AND DERIVATES OF WORDS Authors: R. Bar-Yehudah, T. Etzion, S. Moran PDF - Revised CS0675.revised.pdf 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$ an $\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 invert the glasses that are in in locations originally pointed out 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 {\em derivative} of a $\sigma$-ary word of length $n$. In particular, it is related to the {\em depth} of such a 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. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0675), rather than to the URL of the PDF files directly. The latter URLs may change without notice.