Geometrical optics and chessboard pebbling

Recently Chung, Graham, Morrison and Odlyzko [1] studied some combinatorial and asymptotic enumeration aspects of chessboard pebbling. In this problem , we start with a single pebble, placed at the origin (0, 0) of an infinite chessboard. At each step we remove a pebble from (i, j) and replace it wit h two pebbles at positions (i + 1, j) and (i, j + 1), provided the latter a re unoccupied. After rn steps there will be m + 1 pebbles on the board, in various configurations. Some subsets of the lattice first quadrant are unav oidable, as they must always contain at least one pebble. We study asymptot ically the number f(k) of minimal unavoidable sets that consist of Ic latti ce points, as k --> infinity. We also analyze a related double sequence f(k , r), using various asymptotic approaches, including the ray method of geom etrical optics. (C) 2001 Elsevier Science Ltd. All rights reserved.