Geometrical optics and chessboard pebbling (Q5938928): Difference between revisions

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.