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.

To the list of the CS technical reports of 1991

To the main CS technical reports page