What is the value of this "game" (counters rebalancing)? This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer.

Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.


  1. Given as many steps as you like, can many positive valued counters can you reach?
  
  2. How many positively valued counters are reachable after $T\cdot M - 1$ steps?




For question (1), here's a a detailed buildup for $\approx T\log(M)$ positive counters:


While you have less than $T-1$ counters at value $M$:


Increment the minimal index counter whose value is strictly less than $M$.



(This has to converge as the sum of the counters are bound to increase every $T$ steps.)


Let $r = T$.
While ($c_0&gt;1$)

a.  while ($c_0&gt;c_r$)


Increment $c_r$


b. $r = r + 1$


Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$.
This means the loop will halt when $m_r &lt; 1$ (give or take integrality and end-of-game-strategies).

This gives us 
$$M(1-\frac{1}{T})^{r-T+1} &lt; 1$$ 
$$(1-\frac{1}{T})^{r-T+1} &lt; M^{-1}$$
$$({r-T+1}) \log (1-\frac{1}{T}) &lt; -\log M$$
$${r-T+1}  &lt; \frac{-\log M}{\log (1-\frac{1}{T})}$$
$$r  &lt; \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$
$$r  &lt; \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 &lt; T(\log M + 1) -1$$

Is it possible to do better? Can anyone prove this is optimal?
Here is an upper bound for question 2.   

Theorem: After $TM$ steps, you can have at most $T \log M$ positive counters. 

Notation: we assign each step a number, ending with the $0$th step, and starting with the $(-TM+1)$th step.

Observation: in the optimal strategy, if you increment a counter, you do not let it return to $0$.

Proof: Let us assign a value of $1$ to each time you increment a counter in the last $T$ steps; $\frac{1}{2}$ to each time you increment a counter in the previous $T$ steps; $\frac{1}{3}$ to each time you increment a counter in the $T$ steps before that, etc. That is, if you increment a counter between step $-kT+1$ and $-(k-1)T$, it gets a value of $\frac{1}{k}$. 
We need a lemma that we will prove later.

Lemma: for a counter to be positive, it must have had a total value of at least $1$ assigned to it. 

With the lemma, the proof is easy:  the total value we have to assign is $T \sum_{i=1}^M \frac{1}{i} \approx T \log M$, and each positive counter requires us to have assigned total value of at least $1$ to it.

Proof of Lemma: Look at the first time you made that counter positive. If that was between $-kT$ and $-(k-1)T$, then it has been decremented at least $k-1$ times, and so you need to have incremented it $k$ times to have it end up positive. But each of these increments assigns it a value of at least $\frac{1}{k}$.

And here is an upper bound for question 1. Let's use the same overall proof strategy as before.  Again, we assign a value of $\frac{1}{k}$ when we increment a counter on a step between $-kT+1$ and $-(k-1)T$. We also assign a value of $\frac{1}{M}$ when we increment a counter on a step between $-2MT$ and $-MT$, and a value of $0$ if we increment a counter before that. By the same reasoning as before, any counter that was $0$ at step $-2MT$ must be assigned a value of at least $1$. But now, if a counter was positive at step $-2MT$, it still must have been assigned a total value of at least $1$, since it must have been incremented $M$ times to end up positive. Now, the total value we have to assign is $T\log M + T$, so we can have at most $T (\log M + 1)$ positive counters.