\documentstyle[11pt,epic,eepic,leqno]{article} \input amssym.def \input amssym.tex \input psfig \setlength{\textwidth}{6.2in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} \setlength{\headheight}{0in} \newcommand{\aTf}{{\rm (a)} \atop f_0 (k)} \newcommand{\bTf}{{\rm (b)} \atop f_0 (k-1)} \newcommand{\cTf}{{\rm (c)} \atop f_0 (k-1)} \newcommand{\dTf}{{\rm (d)} \atop f_1 (k-2)} \newcommand{\La}{\Lambda} \newcommand{\Dt}{\Delta} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\af}{\alpha} \newcommand{\be}{\beta} \newcommand{\ep}{\epsilon} \newcommand{\vp}{\varphi} \newcommand{\vt}{\vartheta} \newcommand{\om}{\omega} \newcommand{\Om}{\Omega} \newcommand{\Th}{\Theta} \newcommand{\tht}{\theta} \newcommand{\Sg}{\Sigma} \newcommand{\In}{\infty} \newcommand{\dr}{\Rightarrow} \newcommand{\dt}{\delta} \newcommand{\ga}{\gamma} \newcommand{\sig}{\sigma} \newcommand{\zt}{\zeta} \newcommand{\et}{\eta} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\lc}{\lceil} \newcommand{\rc}{\rceil} \newcommand{\lt}{\left(} \newcommand{\rt}{\right)} \newcommand{\dd}{\ldots} \newcommand{\df}{\displaystyle\frac} \newcommand{\fr}{\frac} \newcommand{\dis}{\displaystyle} \newcommand{\ds}{\displaystyle\sum} \newcommand{\rda}{\Rightarrow} \newcommand{\half}{\mbox{\footnotesize {\raisebox{.6ex}{1}/\raisebox{-.6ex}{2}}}} \newcommand{\eith}{\mbox{\footnotesize {\raisebox{.6ex}{1}/\raisebox{-.6ex}{8}}}} \newcommand{\eqn}[1]{(\ref{#1})} \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\vsp}{\vspace{.1in}} \newcommand{\pf}{\noindent{\bf Proof.~}} \newcommand{\eeq}{\end{equation}} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \def\binom#1#2{{#1}\choose{#2}} \makeatletter % put a period after section or subsection number in header \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} % put a period after theorem and theorem-like numbers \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \makeatletter \def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} \makeatother \makeatletter \def\subsection{\@startsection {subsection}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} \makeatother \newtheorem{fact}{Fact} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newenvironment{claim}{\begin{trivlist}\item[]{\bf Claim.}}{\end{trivlist}} \newenvironment{theo}{\begin{trivlist}\item[]{\bf Theorem}\em}{\end{trivlist}} \thispagestyle{empty} \begin{document} \begin{center} {\Large {\bf Pebbling a chessboard}} \\ \vspace{\baselineskip} {\em Fan Chung} \\ \vspace{0.25\baselineskip} Bell Communications Research \\ Morristown, New Jersey 07960 \\ e-mail:~~frkc@bellcore.com \\ \vspace{\baselineskip} {\em Ron Graham} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~rlg@research.att.com \\ \vspace{1\baselineskip} {\em John Morrison} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~jam@research.att.com \\ \vspace{1\baselineskip} {\em Andrew Odlyzko} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~amo@research.att.com \\ \vspace{1.5\baselineskip} {\bf ABSTRACT} \\ \vspace{1.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \hspace*{.25in} This note studies a pebbling problem introduced by M. Kontsevich. One starts with an infinite chessboard covering the first quadrant, with a single pebble located in the extreme lower left cell. Moves consist of replacing a pebble in cell $(i,j)$ by two pebbles in cells $(i+1,j)$ and $(i,j+1)$, provided neither of those positions is occupied. It is shown how to determine which configurations are reachable, and asymptotics of the number of reachable configurations are determined. \clearpage \large\normalsize \renewcommand{\baselinestretch}{1} \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\Large {\bf Pebbling a chessboard}} \\ \vspace{\baselineskip} {\em Fan Chung} \\ \vspace{0.25\baselineskip} Bell Communications Research \\ Morristown, New Jersey 07960 \\ \vspace{\baselineskip} {\em Ron Graham} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~rlg@research.att.com \\ \vspace{1\baselineskip} {\em John Morrison} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~jam@research.att.com \\ \vspace{1\baselineskip} {\em Andrew Odlyzko} \\ \vspace{.25\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ e-mail:~~amo@research.att.com \\ \vspace{1.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp The following puzzle has attracted some attention recently. We first learned of it through Martin Gardner \cite{G92}. A version of it appeared in Omni magazine in 1993 \cite{Morris}. However, it was proposed over 10 years ago by Kontsevich \cite{K}, and a partial analysis of it was published shortly thereafter by Khodulev \cite{Kh}. We begin with an infinite ``chessboard'' $B$ covering the first quadrant. The cells of the board are labelled by integer coordinates $(i,j)$ with $i,j \ge 0$. Initially, a single ``pebble'' is located in cell $(0,0)$ (the lower left corner; see Figure~1). \begin{figure}[htb] \centerline{\psfig{file=ch1.ps,width=1.5in}} \caption{The starting configuration on the board $B$.} \end{figure} The first step or ``move'' consists of replacing this pebble by two pebbles, located at cells $(1,0)$ and $(0,1)$, respectively. In general, a move will consist of removing some pebble, say in cell $(i,j)$, and placing {\em two} pebbles on the board, in positions $(i+1,j)$ and $(i,j+1)$, {\em provided each of these positions is not already occupied}. After $k$ steps the board will have $k+1$ pebbles on it. We call such configurations of pebbles {\em reachable configurations}. We will denote by $R(k)$ the set of reachable configurations with $k$ pebbles, and we set $R := \bigcup\limits_{k \ge 1} R(k)$. In Figure~2, we show the eight possible reachable configurations with at most four pebbles. \begin{figure}[htb] \centerline{\psfig{file=ch2.ps,width=3.5in}} \caption{Reachable configurations with at most four pebbles.} \end{figure} A little experimentation convinces one that in any reachable configuration, some pebble must occupy a cell having coordinates $(i,j)$ with $i+j \le 3$. This fact first seems to have been noted by M. Kontsevich~\cite{K}. We give the ``book'' proof of this in the next section. If $L(k)$ denotes the set (or ``level'') $\{ (i,j) :~ i+j = k \}$ then we can express the above assertion by saying that $L(1) \cup L(2) \cup L(3)$ is {\em unavoidable}, i.e., any reachable configuration must always have some pebble in a cell in $L(1) \cup L(2) \cup L(3)$. In general, an unavoidable set is one which intersects every reachable configuration. Of course if $S$ is unavoidable and $T \supseteq S$ then $T$ is unavoidable. Let us call $S$ a {\em minimal unavoidable} set if $S$ is unavoidable but no proper subset of $S$ is, and let $M(k)$ denote the family of minimal unavoidable sets with $k$ cells. In this note we will characterize the elements of $M(k)$ and give a polynomial time algorithm for recognizing such elements. Many of these results were first proved by Khodulev \cite{Kh}, and we present them here for completeness, since the paper \cite{Kh} is not widely available and contains only sketches of proofs. We will also determine the asymptotic growth rates of $r(k) := |R(k)|$ and $m(k) := |M(k)|$, the sizes of $R(k)$ and $M(k)$, respectively, as $k \to \In$. (These results are all new.) It turns out that the analysis of $r(k)$ and $m(k)$ leads to some interesting problems in asymptotic enumeration. Further results on this problem, including generalizations to arbitrary partially ordered sets, have recently been obtained by Eriksson \cite{Erik}. \section{Properties of unavoidable sets} \begin{lemma} \label{lem1} {\rm \cite{K}} The set $L(1) \cup L(2) \cup L(3)$ of all $(i,j)$ with $i+j \le 3$ is unavoidable. \end{lemma} \pf To each cell $(i,j)$ assign the {\em weight} $2^{-(i+j)}$. Observe that: \begin{itemize} \item[(i)] The total weight covered by pebbles in any reachable configuration is 1. This is so since the starting cell $(0,0)$ has weight 1, and a move does not change the weight of cells covered, i.e., $$2^{-(i+j)} = 2^{- ((i+1)+j)} + 2^{-(i+(j+1))}~.$$ \item[(ii)] The total weight of {\em all} cells in the board is $\sum_{i,j \ge 0} 2^{- (i+j)} =4$. \item[(iii)] The total weight of $L(1) \cup L(2) \cup L(3)$ is 13/4. Thus, the weight of the {\em complement} of $L(3)$ is only 3/4, and since that is less than 1, cannot contain all the pebbles of a reachable configuration. Thus, $L(1) \cup L(2) \cup L(3)$ is unavoidable. \hfill $\blacksquare$ \end{itemize} However, $L(1) \cup L(2) \cup L(3)$ is not a minimal unavoidable set. The following result was proved by Khodulev \cite{Kh}. It was independently conjectured by Martin Gardner \cite{G92}. The proof given here is due to Harold Reiter \cite{R92}. \begin{lemma} \label{lem2} $L(1) \cup L(2)$ is unavoidable. \end{lemma} \pf As before, assign the weight $2^{-(i+j)}$ to the cell $(i,j)$. Observe now that any reachable configuration $C$ has exactly one pebble on each of the boundaries $\{ (i,0) :~ i \ge 0 \}$ and $\{ (0,j) :~ j \ge 0 \}$. Thus, the total weight which $C$ can cover outside of $L(1) \cup L(2)$ is $$2 \cdot 2^{-3} + \sum_{i,j \ge 1 \atop i+j \ge 3} 2^{-(i+j)} =1 ~.$$ This implies that if $C$ is to avoid $L(1) \cup L(2)$, it must cover {\em all} these cells, which is impossible since $C$ is finite. \hfill $\blacksquare$ However, $L(1) \cup L(2)$ is not minimal either, as we will see later. We should observe that for any reachable configuration $C$, the {\em set} of moves needed for reaching $C$ is unique. Only the {\em order} in which these moves are executed can vary in the different ways of reaching $C$. Suppose now that we relax the rules for moves by allowing the replacement of a pebble at $(i,j)$ by pebbles at $(i+1,j)$ and $(i,j+1)$ even when these positions might already be occupied by pebbles. In other words, we allow the accumulation of multiple pebbles in cells during the process of reaching $C$. It might be helpful for this model to imagine that the pebbles first move onto the vertices of an infinite binary tree rooted at $(0,0)$. Then the $2^k$ vertices in the $k^{\rm th}$ level of the tree are identified in the obvious way with the $k+1$ cells in the $k^{\rm th}$ level $L(k) := \{ (i,j) :~ i+j =k \}$ of the board $B$. An easy induction argument now establishes the following result. \begin{lemma} \label{lem3} If a configuration of pebbles (with at most one pebble per cell) can be reached by moves which {\bf allow} accumulations of pebbles in cells, then in fact it can also be reached by the ``standard'' moves, i.e., those which do {\bf not allow} accumulation. \end{lemma} Given a set $X \subset B$, we define the set $M(X)$ of moves recursively as follows. Starting at level 0 and proceeding one level at a time by increasing levels, perform the moves required either to remove {\em all} pebbles from a cell in $X$, or to remove all but at most one of the pebbles from a cell not in $X$. Continue through the last level $L(h(X))$ containing a cell of $X$. \begin{theorem} \label{the1} $X \subset B$ is unavoidable if and only if after executing the moves in $M(X)$, some cell contains at least 3 pebbles. \end{theorem} \pf Let $m(i,j)$ denote the number of pebbles in cell $(i,j)$ after executing $M(X)$. \begin{itemize} \item[(i)] Suppose that $X$ is avoidable and $m(i,j) \ge 3$ for some $(i,j)$. Thus, either $m(i-1, j+1) \ge 2$ or $m(i+1 , j-1) \ge 2$. Assume $m(i-1, j+1) \ge 2$ (the other case is similar). Hence, to reach {\em any} $C \in R$, we must move at least two pebbles off of $(i,j)$, and at least one off of $(i-1, j+1)$. But this will force $(i,j+1)$ to have at least 3 pebbles, and will force $(i, j+1)$ to have at least two. Thus, by induction, we can {\em never} reach an allowable configuration of pebbles (i.e., one in which no cell has more than one pebble), which is a contradiction. \item[(ii)] Suppose $m(i,j) \le 2$ for all $(i,j) \in B$. By the definition of $M(X)$, $$ m(i,j) ~~\mbox{is}~~ \left\{ \begin{array}{l} \le 1~~\mbox{if $(i,j)$ has level $\le h(X)$} \\ ~~ \\ [-.09in] \le 2 ~~\mbox{if $(i,j)$ has level $h(X) +1$} \\ ~~ \\ [-.09in] = 0 ~~\mbox{if $(i,j)$ has level $> h(X) +1$} ~. \end{array} \right. $$ A simple induction argument now shows that the excess pebbles can all be (eventually) moved to achieve a reachable configuration in $R$. Hence $X$ is avoidable. \end{itemize} This completes the proof of Theorem~\ref{the1}. \hfill $\blacksquare$ Note that this result furnishes a polynomial-time algorithm for determining if $X$ is a minimal unavoidable set. \section{Recurrences for minimal unavoidable sets} \hsp Let $f(k)$ denote the number of minimal unavoidable sets consisting of $k$ cells. For $j \ge 0$, define $B(j) = \bigcup\limits_{i > j} L(i)$, the set of cells in levels exceeding $j$. Finally, for $t \ge 0$, define $f_t (k)$ to be the number of minimal unavoidable sets with $k$ cells (i.e., of size $k$) in $B(t)$ where we start with the (multiple) pebble distribution of $1, \overbrace{2,2, \dd ,2}^t , 1$ in $L (t+1)$, and 0 in all $L (s)$, $s > t+1$. As a convention, we take $f_t (k) =0$ for all $k \le 0$. Thus, $f(k) = f_0 (k-1)$ (since $(0,0)$ must be unoccupied), and $f(k) =0$ for $k \le 4$. We list a set of recurrences which suffice to determine all values of $f_t (k)$: \begin{itemize} \item[(i)] $f_0 (k) = 2 f_0 (k-1) + f_1 (k-2)$; \item[(ii)] $f_1 (k) = f_0 (k) + 3 f_1 (k-1) + f_2 (k-2) + 4 \delta (k,2)$ where $$\delta (i,j) = \left\{ \begin{array}{ll} 1 & \mbox{if}~~ i=j ~, \\ ~~ \\ [-.09in] 0 & \mbox{otherwise}~; \end{array} \right. $$ \item[(iii)] For $t \ge 2$, $f_t (k) = f_{t-1} (k) +2 f_t (k-1) + f_{t+1} (k-2) + 2 \delta (k,1) \delta (t,2)$. \end{itemize} To see why these are valid, consider (i). \begin{figure}[htb] \centerline{\psfig{file=ch3.ps,width=6in}} \hspace{.4in}${\rm (a)} \atop f_0 (k)$ \hspace{1.2in}${\rm (b)} \atop f_0 (k-1)$ \hspace{1.35in}${\rm (c)} \atop f_0 (k-1)$ \hspace{1.025in}${\rm (d)} \atop f_1 (k-2)$ \caption{} \end{figure} In Figure~3(a) we have the starting configuration for $f_0 (k)$. We consider the various possibilities as to whether or not various cells in $L(1)$ are in a hypothetical minimal unavoidable set $X$ of size $k$. If $(1,0) \in X$ but $(0,1) \not\in X$ then Figure~3(b) applies and $X$ will consist of $(1,0)$ together with a minimal unavoidable set of size $k-1$ arising from the two pebbles at $(2,0)$ and $(1,1)$. By definition, there are $f_0 (k-1)$ of these. The same argument applies if $(1,0) \not\in X$, $(0,1) \in X$ (Figure~3 (c)). On the other hand, if $(0,1) \in X$ and $(1,0) \in X$ then Figure~3(d) applies, and $f_1 (k-2)$ counts the number of ways of completing $X$. Thus, we have (i). The other recurrences (ii) and (iii) are explained in similar ways. In Table~1, we list some of the small values of $f_t (k)$. \begin{table}[htb] \begin{center} \begin{tabular}{cc|c|c|c|c|c|c|c|c|c|c|c|} \\ \cline{3-13} & 10 & 0 & 2 & 40 & 464 & ~ & ~ & ~ & ~ & ~ & ~ & ~ \\ & 9 & 0 & 2 & 36 & 382 & ~ & ~ & ~ & ~ & ~ & ~ & ~ \\ & 8 & 0 & 2 & 32 & 308 & 2322 & ~ & ~ & ~ & ~ & ~ & ~ \\ & 7 & 0 & 2 & 28 & 242 & 1670 & 10114 & ~ & ~ & ~ & ~ & ~ \\ & 6 & 0 & 2 & 24 & 184 & 1154 & 6466 & ~ & ~ & ~ & ~ & ~ \\ $t$ & 5 & 0 & 2 & 20 & 134 & 758 & 3916 & ~ & ~ & ~ & ~ & ~ \\ & 4 & 0 & 2 & 16 & 92 & 466 & 2216 & 10162 & ~ & ~ & ~ & ~ \\ & 3 & 0 & 2 & 12 & 58 & 262 & 1150 & 4972 & 21296 & ~ & ~ & ~ \\ & 2 & 0 & 2 & 8 & 32 & 130 & 534 & 2206 & 9136 & 37872 & ~ & ~ \\ & 1 & 0 & 0 & 4 & 14 & 54 & 216 & 876 & 3574 & 14628 & 59994 & ~ \\ & 0 & 0 & 0 & 0 & 0 & 4 & 22 & 98 & 412 & 1700 & 6974 & 28576 \\ \cline{3-13} \multicolumn{13}{c}{~} \\ [-.1in] & \multicolumn{1}{c}{~} & \multicolumn{1}{c}{0} & \multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} & \multicolumn{1}{c}{4} & \multicolumn{1}{c}{5} & \multicolumn{1}{c}{6} & \multicolumn{1}{c}{7} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{9} & \multicolumn{1}{c}{10} \\ \multicolumn{13}{c}{~} \\ \multicolumn{2}{c}{~} & \multicolumn{11}{c}{$k$} \end{tabular} \end{center} \caption{Values of $f_t (k)$.} \end{table} \section{Asymptotics of number of minimal unavoidable sets} \hsp The recurrences of the last section are sufficient to determine values of $f(k)$ for small $k$. For large values of $k$, we can obtain asymptotics of $f(k)$ in a simple form: $$f(k) \sim c \gamma^{k-1} ~~~\mbox{as}~~~ k \to \In ~,$$ where $\gamma = 4.147899 \dd$ and $c=0.01676 \dd~$. More precise estimates (including definitions of $\gamma$ and $c$) are stated at the end of this section. Since $\gamma$ and $c$ are algebraic numbers of degree 3, this estimate also shows that there is no simple expression for $f(k)$. The derivation of the asymptotic expansion of $f(k)$ starts with the recurrences of Section~3, and proceeds through two steps. The first step is to derive an explicit expression for the generating function of $f(k)$, and the second is to obtain the asymptotics of the coefficients of that function. The second step is routine, and is sketched only briefly. The first step is the interesting one, since it involves complicated-looking functional relations that yield a surprising answer. In order to analyze the asymptotic behavior of $f(k)$, it is convenient to introduce several auxiliary functions. The definitions are not obvious, and came from experimenting with the recurrences to find out which functions give the best results. First, define the function $s( \cdot , \cdot )$ by \beql{eq1} s(i+j,j) := f_j (i) , ~~~ i,j \ge 0 ~. \eeq Next, define the generating function \beql{eq2} S_i (y) := \sum_{j=0}^i s(i,j) y^j ~. \eeq Thus, for example, $S_3 (y) = 4 y + 2y^2$. For $i \ge 3$, recurrence (iii) of Section~3 is easily seen to be equivalent to the relation \beql{eq3} S_{i+1} (y) = \frac{(1+y)^2}{y} S_i (y) - \frac{1}{y} s(i,0) + ys (i,1) ~. \eeq Finally, set \beql{eq4} S(x,y) := \sum_{i \ge 3} S_i (y) x^i ~. \eeq Note that we are only interested in \begin{eqnarray*} \sum_{k=5}^\In f(k) x^{k-1} & = & \sum_{k=5}^\In f_0 (k-1) x^{k-1} ~=~ \sum_{i=4}^\In s(i,0) x^i \\ & = & \sum_{i=4}^\In S_i (0) x^i ~=~ S(x,0) ~. \end{eqnarray*} The additional variable $y$ is brought in only in order to exploit the structure of recurrences for the $f_t (k)$. From \eqn{eq3} and (i), (ii), (iii) we obtain \beql{eq5} \begin{array}{rll} S(x,y) & = & \ds_{i \ge 3} S_i (y) x^i \\ ~~ \\ & = & x^3 (4y+2y^2) + \df{x(1+y)^2}{y} \ds_{i \ge 3} S_i (y) x^i \\ ~~ \\ & ~ & ~~~~-~ \df{x}{y} S(x,0) + xy \left. \df{\partial S(x,y)}{\partial y} \right|_{y=0}~. \end{array} \eeq Hence \beql{eq6} (y-x(1+y)^2)S(x,y) = x^3 (4y^2 +2y^3) - xS(x,0) + xy^2 \left. \df{\partial S (x,y)}{\partial y} \right|_{y=0} ~. \eeq This is a complicated partial differential equation that at first sight might seem intractable. However, it can be solved explicitly. Differentiating \eqn{eq6} with respect to $y$ and then setting $y=0$, we have \beql{eq7} (1-2x) S(x,0) -x \left. \frac{\partial S (x,y)}{\partial y} \right|_{y=0} =0~. \eeq Therefore, we can eliminate $\left. \frac{\partial S (x,y)}{\partial y} \right|_{y=0}$ to obtain \beql{eq8} (y-x(1+y)^2)S(x,y) = (y^2 (1-2x)-x) S(x,0) +x^3 (4y^2 +2y^3) ~. \eeq On the curve \beql{eq9} y = x(1+y)^2 ~, \eeq the coefficient of $S(x,y)$ in \eqn{eq8} vanishes and we have \beql{eq10} S(x,0) = x^3 (4y^2 + 2y^3) / (x-y^2 (1-2x))~. \eeq Eq.~\eqn{eq9} implies that $$y = (1-2x - (1-4x)^{1/2}) / (2x)$$ for $|x| < 1/4$, and substituting this into \eqn{eq10} gives an explicit representation of $S(x,0)$ as an algebraic function of $x$ for $|x| < 1/4$, \beql{Neq11} S(x,0) = x^2 \frac{(1-4x)^{1/2} (1-3x + x^2) - 1 + 5x - x^2 - 6x^3}{1-7x + 14 x^2 - 9x^3} ~. \eeq (Through \eqn{eq8} this also gives an explicit representation of $S(x,y)$ for $(x,y)$ in a neighborhood of $(0,0)$, but we do not need this, since $S(x,0)$ is all that is needed to derive the asymptotics of $f(k)$.) The final part of our analysis is now straightforward. The explicit form of $S(x,0)$ shows that $S(x,0)$ is analytic in $|x| < 1/4$ except at zeros of the denominator, i.e. at $x =1/ \gamma$, where $\gamma = 4.14789903 \dd$ satisfies \beql{eq11} \gamma^3 - 7 \gamma^2 + 14 \gamma - 9 =0~. \eeq Direct substitution into the formula for $S(x,0)$ then shows that $S(x,0)$ actually does have a simple pole at $x= 1/ \gamma$, but (in view of the preceding discussion) no other singularities in $|x| < 1/4$. By the standard methods \cite{Bender,BenW,GKP,Od}, we can therefore write $$ f(k) = f_0 (k-1) = s(k-1,0) = [x^{k-1}] S(x,0) = c \gamma^{k-1} + O( 4.01^k)~, $$ where \beql{eq12} c = \lim_{x \to 1/\gamma} S(x,0) (1- \gamma x) = 0.016762198 \dd \eeq and satisfies (after some messy but routine computation best done with a symbolic algebra system) \beql{eq13} 7533c^3 + 10726c^2 + 5068 c - 88 =0 ~. \eeq \section{The number of pebble configurations} \hsp In this section we will treat the problem of enumerating the number of distinct reachable configurations with $k$ pebbles. We denote this number by $g(k)$. As was true for the asymptotics of $f(k)$, it is the derivation of an explicit generating function for the $g(k)$ that presents the main challenge here. As before, let us define $g_t (k)$ to be the number of $k$-pebble reachable configurations where we start with the initial pebble distribution of $1, \overbrace{2,2, \dd ,2}^t ,1$ in $L_{t+1}$, and 0 in all $L_s$, $s > t+1$ (and we restrict ourselves to cells just in $B(t) = \bigcup\limits_{s \ge t+1} L_s$). Thus, $g(k) = g_0 (k)$ for $k \ge 2$. Arguing along the same lines as before, it is not hard to derive the following recurrences for the $g_t (k)$: \begin{itemize} \item[(i$'$)] $g_0 (k) = 2 g_0 (k-1) + g_1 (k) + \delta (k,2)$; \item[(ii$'$)] $g_1 (k) = g_0 (k-3) + 2 g_1 (k-2) + g_2 (k-1) + g_1 (k-4)$; \item[(iii$'$)] For $t \ge 2$, $$g_t (k) = g_{t-1} (k-t-2) + 2 g_t (k-t-1) + g_{t+1} (k-t) ~.$$ \end{itemize} Now set \beql{eq14} \begin{array}{rll} h_i (k) & := & g_i (k+i) ~, \\ ~~ \\ [-.09in] H_i (x) & := & \dis\sum_{k=0}^\In h_i (k) x^k ~, \\ ~~ \\ [-.09in] H(x,y) & := & \dis\sum_{i=0}^\In H_i (x) y^i ~. \end{array} \eeq Some values of $h_t (k)$ are shown in Table~2. Straightforward computation using \eqn{eq14} and (i$'$), (ii$'$), (iii$'$) shows \beql{eq15} H(x,y) = x^2 + \lt \frac{1}{y} + 2x + x^2 y \rt H(x,xy) - \frac{1}{y} H(x,0) +x^4 y H_1 (x) ~. \eeq \begin{table}[htb] \begin{center} \begin{tabular}{cc|c|c|c|c|c|c|c|c|c|} ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ \\ ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ \\ $t$ & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ ~ & 1 & 0 & 0 & 0 & 0 & 1 & 2 & 6 & 13 & 33 \\ ~ & 0 & 0 & 0 & 1 & 2 & 4 & 9 & 20 & 46 & 105 \\ \cline{3-11} ~ & \multicolumn{1}{c}{~} & \multicolumn{1}{c}{0} & \multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} & \multicolumn{1}{c}{4} & \multicolumn{1}{c}{5} & \multicolumn{1}{c}{6} & \multicolumn{1}{c}{7} & \multicolumn{1}{c}{8} \\ \multicolumn{11}{c}{~} \\ [-.1in] ~ & \multicolumn{1}{c}{~} & \multicolumn{9}{c}{$k$} \end{tabular} \end{center} \caption{Values of $h_t (k)$.} \end{table} %\clearpage \noindent Since $H_1 (x) = \left. \frac{\partial H (x,y)}{\partial y} \right|_{y=0}$, we have \beql{eq16} yH(x,y) = x^2 y + (1+xy)^2 H(x,xy) - H(x,0) +x^4 y^2 \left. \frac{\partial H (x,y)}{\partial y} \right|_{y=0}~. \eeq Differentiating \eqn{eq16} with respect to $y$, and setting $y=0$ implies \beql{eq17} H(x,0) = x^2 + x \left. \frac{\partial H(x,y)}{\partial y} \right|_{y=0} + 2x H(x,0)~. \eeq Substituting $$ x \left. \frac{\partial H(x,y)}{\partial y} \right|_{y=0} = (1-2x) H(x,0) -x^2$$ into \eqn{eq16} gives \beql{eq18} yH(x,y) = (1+xy)^2 H(x,xy) + (x^3 y^2 - 2x^4 y^2 -1) H(x,0) +x^2 y - x^5 y^2 \eeq which is the basic relation for $H(x,y)$ we will use. This is more difficult to analyze than the corresponding functional equation \eqn{eq8} for $S(x,y)$ but we still can obtain significant information about its asymptotic behavior. To begin, from \eqn{eq14} and \eqn{eq18} we have \begin{eqnarray} \label{eq19} (1-2x) H_0 (x) & = & x H_1 (x) + x^2 \nonumber \\ H_1 (x) & = & x^2 (H_2 (x) + 2 H_1 (x) + H_0 (x)) + x^4 H_1 (x) \nonumber \\ [-.09in] & ~ & \\ [-.09in] \noalign{\mbox{and for $n \ge 2$,}} H_n (x) & = & x^{n+1} (H_{n+1} (x) + 2 H_n (x) + H_{n-1} (x)) ~. \nonumber \end{eqnarray} Therefore, $$ \begin{array}{rll} H_1 (x) & = & \lt \frac{1-2x}{x} \rt H_0 (x) -x ~, \\ ~~ \\ [-.09in] H_2 (x) & = & \lt \frac{1-x^4}{x^2} \rt H_1 (x) - 2 H_1 (x) - H_0 (x) \\ ~~ \\ [-.09in] & = & \df{1}{x^3} (((1-2x^2-x^4) (1-2x)-x^3) H_0 (x) -x^2 (1-2x^2 -x^4)~, \end{array} $$ and for $n \ge 3$, $$ H_n (x) = \frac{1}{x^n} ((1-2x^n) H_{n-1} (x) -x^n H_{n-2} (x))~. $$ It then follows by induction that \beql{eq20} H_n (x) = x^{- {\binom{n+1}{2}}} (q_n (x) H_0 (x) -x^2 p_n (x)) \eeq where \begin{eqnarray*} q_1 (x) & = & 1-2x ~, ~~~ p_1 (x) =1 ~, \\ q_2 (x) & = & (1-2x^2 -x^4) (1-2x)-x^3~, ~~~ p_2 (x) =1 -2x^2 -x^4 \end{eqnarray*} and for $n \ge 3$, \beql{eq21} \begin{array}{rll} q_n (x) & = & (1-2x^n) q_{n-1} (x) -x^{2n-1} q_{n-2} (x) ~, \\ ~~ \\ [-.05in] p_n (x) & = & (1-2x^n) p_{n-1} (x) - x^{2n-1} p_{n-2} (x) \end{array} \eeq (where we can consider \eqn{eq20} as a formal power series identity). From \eqn{eq21} we see that \begin{eqnarray*} q(x) & = & \lim_{n \to \In} q_n (x) ~, \\ p(x) & = & \lim_{n \to \In} p_n (x) \end{eqnarray*} exist as formal power series and that $$[x^k] q(x) = [x^k] q_n (x)~, ~~~ [x^k] p(x) = [x^k] p_n (x)$$ for $n \ge k+1$. Note that by \eqn{eq20}, increasing powers of $x$ divide $q_n (x) H_0 (x) -x^2 p_n (x)$ as $n \to \In$. Thus, we have \beql{eq22} H_0 (x) = \frac{x^2 p(x)}{q(x)} \eeq as a formal power series. From \eqn{eq21} and \eqn{eq22} it now follows (cf.~\cite{F80}) that $H_0 (x)$ can be written as the continued fraction \beql{eq23} H_0 (x) = \frac{x^2}{1-2x - \frac{x^3}{1-2x-x^4 - \frac{x^5}{1-2x^3 - \frac{x^7}{1-2x^4 - \frac{x^9}{1-2x^5 - \frac{x^{11}}{1-2x^6 -\cdots }}}}}} ~. \eeq Although this continued fraction is similar to some studied by Ramanujan (see \cite{A79}, \cite{S68}), it does not seem to have appeared in the literature before. The recurrences \eqn{eq21} imply that $p(x)$ and $q(x)$ are analytic in the disc $\{ x:~ |x| < 1 \}$, and so $H_0 (x)$ is meromorphic for $|x| <1$. To determine the asymptotic behavior of $H_0 (x)$, we need to look at the zeros of $q(x)$. It turns out that in the disc $\{ x:~|x| \le 1/2 \}$, $q(x)$ has only a simple zero at $\beta_1 = 1/ \af$ where $\af = 2.321642199494 \dd$~. This implies \beql{eq24} h_0 (k) = [x^k] H_0 (x) = c_1 \af^k + O(2^k) \eeq where $$ c_1 = \frac{- \beta_1 p ( \beta_1)}{q' ( \beta_1)} ~. $$ In fact, $q(x)$ has zeros of multiplicity one at $$ \begin{array}{rl@{~}l@{}l} \beta_1 & = & & 0.430729593 \dd \\ ~ \\ [-.09in] \beta_2 & = & & 0.685754744 \dd \\ ~ \\ [-.09in] \beta_3 & = & - & 0.704352541 \dd \\ ~ \\ [-.09in] \beta_4 & = & & 0.782572917 \dd \end{array} $$ and no other zeros in $\{ x:~|x| \le 0.8 \}$. A more careful analysis shows that \eqn{eq24} can be improved to \beql{eq25} h_0 (k) = \sum_{j=1}^4 \frac{- p ( \beta_j )}{q' ( \beta_j )} \beta_j^{-k+1} + O ((5/4)^k)~, \eeq and even better approximations can be obtained with more effort. The basic technique for proving \eqn{eq24} is given, for example, in \cite{OW88}. We give a brief sketch here. To begin, computation shows that $q(x)$ starts as follows: $$q(x) = 1-2x -2x^2 +x^3 +x^4 + 7x^5 + 2x^6 + 5x^7 - 4x^8 - 7x^9 - 9x^{10} -14x^{11} - \cdots ~.$$ Let \beql{eq26} Q(x) = 1-2x -2x^2 + x^3 +x^4 + 7x^5 + \cdots + 46x^{19} \eeq consist of the first 20 terms of $q(x)$. It is not hard to verify that $|Q(x)| \ge 1/20$ for $|x| = 1/2$. We want to show that $Q_1(x) = q(x) - Q(x)$ is small on $|x| > 1/2$. For $|x| = 3/4$, computation shows that $| q_5 (x) | \le 10$, $| q_6 (x) | \le 10$. By \eqn{eq21}, $$|q_n (x) | \le \lt 1+2 \lt \frac{3}{4} \rt^n \rt | q_{n-1} (x) | + \lt \frac{3}{4} \rt^{2n-1} |q_{n-2} (x) |~. $$ Therefore, \beql{eq27} |q(x) | \le 30 ~~~\mbox{for}~~~ |x| =3/4~, \eeq which implies for $|y| = 1/2$, $$ \begin{array}{rll} | Q_1 (y) | & \le & \ds_{m=20}^\In | [x^m] q(x) | ~|y|^m \\ ~~ \\ [-.05in] & \le & 30 \ds_{m=20}^\In (2/3)^m ~\le~ 90 \lt \df{2}{3} \rt^{20}~. \end{array} $$ Thus, $|Q_1 (y)| < |Q(y)|$ for $|y| =1/2$, so by Rouch\'{e}'s theorem, $Q(y)$ and $q(y)$ have the same number of zeros in $\{ y : |y| \le 1/2 \}$. However, direct computation shows that $Q(y)$ has exactly one zero in this region, and therefore, so does $q(y)$. Consequently, $\beta_1 = 0.430729593 \dd$ is the only zero of $q(y)$ in $\{ y:~|y| \le 1/2 \}$. The recurrence \eqn{eq21} also gives an effective method for computing the other zeros $\beta_j$, as well as the values of $p ( \beta_j )$, $q' (\beta_j)$ and $c_1 = 0.12268707 \dd$~. It seems unlikely that there is as simple an expression for $g(k)$ as the one we have for $f(k)$. Poles of continued fractions such as that of \eqn{eq23} can seldom be expressed in closed form, and are expected to be usually transcendental. There are few rigorous results or methods. On the other hand, accurate numerical approximations are almost always easy to obtain. \section{Some history and acknowledgements} \hsp It seems \cite{L92} that the original problem of showing that $\bigcup\limits_{i=0}^4 L(i)$ is unavoidable appeared as Question~5 in the Spring 1981 Senior Paper of the Tournament of the Towns (in the former Soviet Union) where it is attributed to M. Kontsevich. The solution was presented at the first World Federation of National Mathematics Competitions Conference held at the Univ. of Waterloo in 1990. (We are indebted to Andy Liu for this bit of scholarship.) We would particularly like to thank Martin Gardner for once again bringing to our attention a beautiful problem which looks deceptively simple and yet offers interesting challenges. We thank M. Kontsevich for informing us of the references \cite{K,Kh}. We are also grateful to H.~Eriksson and D.~E. Knuth for their comments and corrections to an earlier draft. \clearpage \begin{thebibliography}{OW882} %\bibitem[A79]{A79} \bibitem{A79} G. Andrews, An introduction to Ramanujan's ``lost notebook'', {\em Amer. Math. Monthly 86} (1979), 89--108. %\bibitem[Bender]{Bender} \bibitem{Bender} E.~A. Bender, Asymptotic methods in enumeration, {\em SIAM Review 16} (1974), 485--515. %\bibitem[BenW]{BenW} \bibitem{BenW} E.~A. Bender and S. G. Williamson, {\em Foundations of Applied Combinatorics}, Addison-Wesley, 1991. %\bibitem[F80]{F80} \bibitem{Erik} H. Eriksson, Pebblings, to be published. \bibitem{F80} P. Flajolet, Combinatorial aspects of continued fractions, {\em Discrete Math. 32} (1980), 125--161. %\bibitem[G92]{G92} \bibitem{G92} Martin Gardner (personal communication). %\bibitem[GKP]{GKP} \bibitem{GKP} R.~L. Graham, D.~E. Knuth, and O. Patashnik, {\em Concrete Mathematics}, Addison-Wesley, 1989. %\bibitem[Kh]{Kh} \bibitem{Kh} A. Khodulev, Pebble spreading, {\em Kvant}. July 1982, pp.~28--31 and 55. (In Russian.) %\bibitem[K]{K} \bibitem{K} M. Kontsevich, Problem M715, {\em Kvant}. Nov. 1981, p.~21. (In Russian.) %\bibitem[L92]{L92} \bibitem{L92} Andy Liu (personal communication). %\bibitem[Morris]{Morris} \bibitem{Morris} S. Morris, Counter-intuitive puzzle, {\em Omni}, April 1993. (Solution by N. Konstantinov in the August 1993 issue.) %\bibitem[Od]{Od} \bibitem{Od} A.~M. Odlyzko, Asymptotic enumeration methods, in {\em Handbook of Combinatorics}, R.~L. Graham, M.Gr\"{o}tschel, and L. Lov\'{a}sz, eds., North-Holland, 1993, to appear. %\bibitem[OW88]{OW88} \bibitem{OW88} A.~M. Odlyzko and A.~S. Wilf, The editor's corner: $n$ coins in a fountain, {\em Amer. Math. Monthly 95} (1988), 840--843. %\bibitem[R92]{R92} \bibitem{R92} Harold Reiter (personal communication). %\bibitem[S68]{S68} \bibitem{S68} G. Szekeres, A combinatorial interpretation of Ramanujan's continued fractions, {\em Canad. Math. Bull. 11} (1968), 405--408. \end{thebibliography} \clearpage \pagestyle{empty} \setcounter{figure}{0} \begin{figure}[htb] ~~ \\ \vspace{+1in} \centerline{\psfig{file=ch1.ps,width=3in}} \caption{The starting configuration on the board $B$.} \end{figure} \clearpage \begin{figure}[htb] ~~ \\ \vspace{+.5in} \centerline{\psfig{file=ch2.ps,width=6in}} \caption{Reachable configurations with at most four pebbles.} \end{figure} \clearpage \begin{figure}[htb] \begin{center} ~~ \\ \vspace{+1in} %\input ch3a.tex \setlength{\unitlength}{0.0125in} \begin{picture}(400,387)(0,-10) \path(0,266)(0,372) \path(0,337)(105,337) \path(0,302)(105,302) \path(70,266)(70,372) \path(0,266)(105,266) \path(35,266)(35,372) \put(18,315){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(53,281){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \texture{c0c0c0c0 0 0 0 0 0 0 0 c0c0c0c0 0 0 0 0 0 0 0 c0c0c0c0 0 0 0 0 0 0 0 c0c0c0c0 0 0 0 0 0 0 0 } \shade\path(295,266)(295,302)(260,302) (260,266)(295,266) \path(295,266)(295,302)(260,302) (260,266)(295,266) \path(260,266)(260,372) \path(260,337)(365,337)(400,337) \path(260,302)(365,302)(400,302) \path(330,266)(330,372) \path(260,266)(400,266)(365,266) \path(295,266)(295,372) \path(365,267)(365,371) \put(278,315){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(313,314){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(348,280){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(313,280){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 0}}}}} \shade\path(35,46)(35,82)(0,82) (0,46)(35,46) \path(35,46)(35,82)(0,82) (0,46)(35,46) \path(0,46)(0,152) \path(0,117)(105,117)(140,117) \path(0,82)(105,82)(140,82) \path(70,46)(70,152) \path(0,46)(140,46)(105,46) \shade\path(35,266)(35,302)(0,302) (0,266)(35,266) \path(35,266)(35,302)(0,302) (0,266)(35,266) \path(35,46)(35,152) \put(279,131){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \path(105,47)(105,151) \shade\path(295,46)(295,82)(260,82) (260,46)(295,46) \path(295,46)(295,82)(260,82) (260,46)(295,46) \path(260,46)(260,152) \path(260,117)(365,117)(400,117) \path(260,82)(365,82)(400,82) \path(330,46)(330,152) \path(260,46)(400,46)(365,46) \path(295,46)(295,152) \path(365,47)(365,151) \put(55,242){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm (a)}}}}} \put(330,23){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm (d)}}}}} \put(71,23){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm (c)}}}}} \put(331,0){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm $f_1 (k-2)$}}}}} \put(331,223){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm $f_0 (k-1)$}}}}} \put(331,245){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm (b)}}}}} \put(56,221){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm $f_0 (k)$}}}}} \put(71,1){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\twlrm $f_0 (k-1)$}}}}} \put(53,94){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(53,60){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(18,95){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 0}}}}} \put(18,132){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(348,60){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 1}}}}} \put(313,60){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 0}}}}} \put(313,94){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 2}}}}} \put(278,95){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\shortstack{{\elvrm 0}}}}} \end{picture} \end{center} \caption{} \end{figure} \end{document}