Geometrical optics and chessboard pebbling (Q5938928)
From MaRDI portal
scientific article; zbMATH DE number 1631144
Language | Label | Description | Also known as |
---|---|---|---|
English | Geometrical optics and chessboard pebbling |
scientific article; zbMATH DE number 1631144 |
Statements
Geometrical optics and chessboard pebbling (English)
0 references
7 August 2001
0 references
Since recently chessboard pebbling has been studied extensively in telecommunication. In this game, played on the infinite board \(\{(i,j)\}\) (\(i,j\) natural numbers), a set of pebbles are expanding toward infinity. In every step a cell \((i,j),\) containing pebble(s), is selected and the pebble moves over to the cells \((i,j+1)\) and \((i+1,j).\) A set of cells is called unavoidable if it meets every reachable configuration (in a given number of steps). This paper studies the (asymptotic) number of minimal unavoidable sets with a given number of cells. Using recurrence relations and a certain generating function, it solves the recurrence asymptotically applying integral representations. The proofs are given on two ways: by applications of the Ray method and of the saddle point method.
0 references
chessboard pebbling
0 references
asymptotics
0 references
integral representation
0 references
Ray method
0 references
saddle point method
0 references
pebble
0 references