Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v\_0$, $v\_1$, ..., $v\_{k-1}$ and exactly $k$ arcs $v\_0 \to v\_1$, $v\_1 \to v\_2$, ..., $v\_{k-2} \to v\_{k-1}$, $v\_{k-1} \to v\_0$. (That is, $D$ is a directed cycle on $k$ vertices.) Let $V$ be the set of vertices of $D$. A *chip configuration on $D$* will mean a map $f : V \to \mathbb{N}$. Visually, we represent a chip configuration by imagining that $f\left(v\right)$ "chips" (or coins or whatever tokens) are placed at each vertex $v \in V$. If $v$ is a vertex of $D$, then *kicking $v$* will mean an operation which takes a chip configuration $f$ on $D$ satisfying $f\left(v\right) \geq n$, and returns another chip configuration $f'$ on $D$ which is defined as follows:


$f'\left(v\right) = f\left(v\right) - n$;


$f'\left(w\right) = f\left(w\right) + 1$ for every vertex $w$ such that $v \to w$ is an edge of $D$ (note that there exists only one such vertex $w$ for our graph $D$);


$f'\left(w\right) = f\left(w\right)$ for all remaining vertices $w$.


(In visual language, $f'$ is obtained from $f$ by removing $n$ chips from the vertex $v$ and adding one chip at the vertex that follows $v$ on the cycle.)


Notice that kicking $v$ is similar to the "firing $v$" operation from [chip-firing (aka sandpile) theory](http://arxiv.org/abs/0801.3306v4); indeed, it can be seen as a particular case of the latter if we add a new vertex to $D$, proclaim it the sink, and add $n-1$ arcs from each $v \in V$ to this sink.


A *kicking operation* will mean an operation which is kicking $v$ for some $v \in V$.


If $J$ is a subset of $V$, then a chip configuration $f$ is called *$J$-flooding* if every $v \in J$ satisfies $f\left(v\right) > 0$.


If $f$ is a chip configuration on $D$, then $\left|f\right|$ will mean the sum $\sum\limits\_{v \in V}f\left(v\right)$.


**Conjecture 1.** If $f$ is a chip configuration on $D$ satisfying $\left|f\right| \geq n^{k-1} + n^{k-2} + \cdots + 1$, then one can transform $f$ into a $V$-flooding chip configuration by a sequence of kicking operations.


**Conjecture 2.** If $J$ is a subset of $V$, and if $f$ is a chip configuration on $D$ satisfying $\left|f\right| \geq n^{k-1} + n^{k-2} + \cdots + n^{k-\left|J\right|}$, then one can transform $f$ into a $J$-flooding chip configuration by a sequence of kicking operations.


I have proven Conjecture 1 for all $k \leq 4$ and Conjecture 2 for all $k \leq 3$ by casework; at least the bound of Conjecture 1 is sharp. I am wondering if the conjectures are true in general. The motivation was a [number theory problem from Norway's Abelkonkurransen 1998-99 (final problem 2b)](https://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=83640) which I tried to generalize back in 2006. The actual number theory problem, even in my generalization, is rather easy, as divisibility of integers boils down to comparing the exponents of prime powers in them; but it appears to me that there is much more substance to the combinatorial generalization that is Conjecture 1 above. Conjecture 2 was my attempt to make Conjecture 1 more amenable to induction by generalizing it even further; but so far it has just resulted in two conjectures rather than one.


The next question will probably surprise noone:


**Question 3.** If $D$, instead of being a cycle, is an arbitrary strongly connected digraph, what can we say about the smallest $N \in \mathbb{N}$ such that every chip configuration $f$ on $D$ satisfying $\left|f\right| \geq N$ can be transformed into a $V$-flooding chip configuration by a sequence of kicking operations?



Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)
It now looks to me that conjecture 2 is only easier.


We induct on $|J|$. Base $|J|=1$, say, $J=\{k\}$. If $f(k)>0$ there is nothing to prove, so assume that $f(k)=0$. We have $n^{k-1}$ coins in vertices $1,\dots,k-1$ (there may be more coins, but we use only $n^{k-1}$) and perform operations until $f(k)$ becomes positive or we can not proceed. In the second case note that $I=f(1)+nf(2)+\dots+n^{k-2}f(k-1)$ remains invariant under our operations, and, since $f(i)\leq n-1$ (we can not proceed), we have $I\leq (n-1)(1+n+\dots+n^{k-2})=n^{k-1}-1$, though initially $I$ was not less then $n^{k-1}$. A contradiction. 


Assume that for lesser values of $|J|$ the statement holds, and prove it for $J$. At first, we may suppose that $f(j)=0$ for all $j\in J$, else reserve a coin in $j$, replace $J$ to $J\setminus j$ (do not touch reserved coin, so $|f|$ decreases by 1) and induct on $|J|$. The set $V$ of vertices is a union of disjoint segments $\Delta=\{t-p,t-p+1,\dots,t\}$, where $\Delta\cap J=\{t\}$. Of course, $p\leq k-|J|$ for any such a segment. If $f(t-p)+f(t-p+1)+\dots+f(t-1)\geq n^p$, we may make $f(t)$ positive by our operations by above argument, the cost is at most $n^p\leq n^{k-|J|}$ (at most $n^p-1$ coins are lost and 1 coin in $t$ must be preserved). Do it, remove $t$ from $J$ (do not forget to preserve a coin in $t$) and induct on $|J|$. If not, then summing by all segments we see that $|f|$ is too small.


