Geometrical optics and chessboard pebbling

✍ Scribed by C. Knessl

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 461 KB
• Volume: 14
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/s0893-9659(00)00163-4

✦ Synopsis

Recently

Chung. Graham, Morrison and Odlyzko [l]

studied some combinatorial and asymptotic enumeration aspects of chessboard pebbling.

In this problem, we start with a single pebble, placed at the origin (0,O) of an infinite chessboard. At each step we remove a pebble from (i,j) and repIace it with two pebbles at positions (a + 1,j) and (i.j + I). provided the latter are unoccupied. After m steps there will be m+ 1 pebbles on the board, in various configurations. Some subsets of the lattice first quadrant are unavoid~ie, as they must always contain at least one pebble.

We study asymptotically the number f(Rf of minimal unavoidable sets that consist of k lattice points, as Ic -+ co. We also analyze a related double sequence f&r), using various asymptotic approaches, including the ray method of geometrical optics.