Chessboard pebbling is a puzzle on an infinite square grid whose cells are indexed by nonnegative
integers 
.
A move removes a pebble from 
and places one pebble in each of 
and 
, provided both destination cells are empty. In one version,
the initial pebbles occupy 
, 
, and 
. The task is to empty all three of these cells after finitely
many moves (Stankova 2012).
Assign cell 
the weight 
.
The total weight of occupied cells is an invariant,
since 
.
Initially this total is 
. The geometric series
gives the weight of the entire board as
 |
The cells outside the initial three therefore have total weight 2. Every finite set of these cells has strictly smaller weight, since all omitted terms are positive. Hence no finite sequence of moves can empty the three initial cells (Stankova 2012).
Another version begins with a single pebble at 
. Every reachable configuration must retain a pebble in
a cell with 
(Chung et al. 1995, pp. 114-115). Indeed, the invariant
total is now 1, whereas the total weight of all cells with 
is only
 |
The pebbling number belongs to graph pebbling, whose pebbling move removes two pebbles from a graph vertex and places one on an adjacent vertex, discarding the other (Milans and Clark 2006). This differs from the splitting rule above. Conway's soldiers is another reachability puzzle on an infinite checkerboard.
