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

Anderson, Richard; Lovász, László; Shor, Peter; Spencer, Joel; Tardos, Eva; Winograd, Shmuel

Am. Math. Mon. 96, No. 6, 481-493 (1989).

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