Disks, balls, and walls: Analysis of a combinatorial game.(English)Zbl 0693.90110

The six authors of this paper investigate the following combinatorial situation. At time $$t=0$$ there is a vector $$a(0)\in N^ Z$$ with $$a_ i(0)=2n+1$$ for $$i=0$$ and $$a_ i(0)=0$$ for all other integers i. A move changes a vector a into a vector b with $b_ i:=[1/2a_{i+1}]+[1/2a_{i-1}]+a_ i-2[1/2a_ i]$ where [a] denotes the largest natural number $$\leq a$$. They prove that after finitely many moves the vector with coordinates $$a_ i=1$$ for -n$$\leq i\leq n$$ and $$a_ i=0$$ elsewhere is reached. Their main concern is to find bounds for the number of moves M(n) needed to reach this end position. They prove that $$1/2n(n+1)\leq M(n)\leq (1/6\pi^ 2-1)+7n$$ and $$M(n)=cn^ 2+O(n)$$ where.33$$\leq c\leq.65.$$
By writing down the vectors a(t) for $$t\geq O(n)$$ the authors discover that the pattern of numbers exhibits a regular division in triangular regions in which the same alternation of numbers occurs. The vertical boundaries of these regions they call “walls” and the diagonal boundaries give the orbit of a “ball” moving between two “walls”. They give a set of homogeneous linear differential equations approximating the movement of the “walls”. In this way they get an upper bound for M(n).
Reviewer: J.A.M.Potters

MSC:

 91A99 Game theory

Keywords:

combinatorial game
Full Text: