Pebbling in hypercubes
Pebbling in hypercubes
复制标题
DOI：
10.1137/0402041
复制
发表时间：
1989-11
影响因子：
0.8
通讯作者：
F. Chung
中科院分区：
文献类型：
--
作者：
F. Chung
本文考虑了超立方体上的以下博弈，首先由Lagarias和Saks提出。假设$2^n$ pebbles分布在一个n-立方体的顶点上（有$2^n$个顶点）。一个pebbling步骤是从某个顶点移除两个pebbles，然后在相邻的顶点放置一个pebbles。我们感兴趣的问题是确定是否有可能通过重复使用从任何2^n $ pebbles开始的pebbling步骤将一个pebbles移动到指定的顶点。这个问题得到了肯定的回答，证明了几个更强和更一般的结果。
This paper considers the following game on a hypercube, first suggested by Lagarias and Saks. Suppose $2^n$ pebbles are distributed onto vertices of an n-cube (with $2^n$ vertices). A pebbling step is to remove two pebbles from some vertex and then place one pebble at an adjacent vertex. The question of interest is to determine if it is possible to get one pebble to a specified vertex by repeatedly using the pebbling steps from any starting distribution of $2^n$ pebbles. This question is answered affirmatively by proving several stronger and more general results.