This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten.
I am interested in really good upper bounds on the length of a certain finite sequence. I will define the sequence and then show what is, I think, a pretty good upper bound on its length. A colleague of mine suggested that one should be able to do better, and I realize that I don't know much about what kind of tools ought to be brought to bear on this type of elementary, but nontrivial problem.
By $\mathbb{N}$ I mean the natural numbers: $\{0,1,2,\ldots\}$. Let $d$ be a positive integer, and consider the "$d$-decimation function"
$D_d: N \mapsto N - \lceil \frac{N}{d} \rceil$.
You can think about this function as follows (and this is how it arises in my intended application): we have $N$ discrete objects and we place each into one of $d$ boxes. Then we are allowed to remove all the objects from any one box. If we want to minimize the number of objects remaining, we simply choose the box which has the most (or tied for the most) objects. By the Pigeonhole Principle at least one box must have $\frac{N}{d}$ objects. But because everything is integer-valued, there must in fact be a box with at least $\lceil \frac{N}{d} \rceil$ objects, hence if we empty that box we are left with at most $D_d(N)$ objects.
Now we redistribute the remaining objects in the (still $d$ -- we don't remove the box, just empty it) boxes and repeat. Thus for $i \geq 1$ define
$D_d^i = D_d \circ \ldots \circ D_d: \mathbb{N} \rightarrow \mathbb{N}$, the $i$-fold composition. Because $D_d(N) < N$ for all $N \geq 1$, for each $N \in \mathbb{Z}^+$ there is some $i$ such that $D_d^i(N) = 0$. We define the d-decimation length of $N$ to be the least such $i$ and denote it by $\ell_d(N)$. I want really good upper bounds on $\ell_d(N)$.
Some quick comments:
- For all $N \in \mathbb{Z}^+$ we have $D_1(N) = 0$, so $\ell_1(N) = 1$.
- For all $N \leq d$ we have $D_d(N) = N-1$, so $\ell_d(N) = N$ if $d \geq N$.
So the interesting case is $2 \leq d < N$: let's assume that.
I will now give the upper bound that I know. It comes from the fact that
$D_d(N) = N - \lceil \frac{N}{d} \rceil \leq N - \frac{N}{d} = (1-\frac{1}{d})N$,
so
$D_d^i(N) \leq N (1-\frac{1}{d})^i$.
Since $e^x$ is convex, it lies above its tangent line, thus $1+x \leq e^x$ for all $x$, with strict inequality for all $x \neq 0$. Using this we get
$N (1-\frac{1}{d})^i < N e^{\frac{-i}{d}}$
If we choose $i$ such that
$N e^{\frac{-i}{d}} < d$, then $D_d^i(N) < d$, so $D_d^{i+d-1} = 0$ and $\ell_d(N) \leq i + d-1$. An easy calculation shows that we can take
$i = \lceil d \log \frac{N}{d} \rceil$,
so $\ell_d(N) \leq \lceil d \log \frac{N}{d} \rceil + d-1 < d (1+\log \frac{N}{d})$.
I would like to do better than this. My colleague says that one can get instead
$\ell(d) \leq d(\gamma + \epsilon + \log \frac{N}{d})$,
where $\gamma = 0.577\ldots$ is the Euler-Mascheroni constant and $\epsilon$ approaches $0$ as $\min(d,\frac{N}{d})$ approaches infinity. (I certainly believe him; I just don't understand how to get this.) He also suggests a better bound involving partial sums of the harmonic series which is valid in all cases. More than anything, I would like to see how someone who knows what they are doing attacks this kind of problem.
Your colleague is correct. The letter $L$ will denote where we are now, $D$ is your $D.$ Then $H_k$ is the harmonic sum including $1/k.$
If $D \geq L,$ each step will subtract exactly $1,$ so there are at most $D$ steps.
If $2D \geq L > D,$ each step will subtract exactly $2,$ so there are at most $D/2$ steps to reach $D \geq L,$ so at most $D H_2$ steps to reach $0.$
If $3D \geq L > 2D,$ each step will subtract exactly $3,$ so there are at most $D/3$ steps to reach $2D \geq L > D,$ so at most $D H_3$ steps to reach $0.$
If $4D \geq L > 3D,$ each step will subtract exactly $4,$ so there are at most $D/4$ steps to reach $3D \geq L > 2D,$ so at most $D H_4$ steps to reach $0.$
If $5D \geq L > 4D,$ each step will subtract exactly $5,$ so there are at most $D/5$ steps to reach $4D \geq L > 3D,$ so at most $D H_5$ steps to reach $0.$
...................
If $wD \geq L > (w-1)D,$ each step will subtract exactly $w,$ so there are at most $D/w$ steps to reach $(w-1)D \geq L > (w-2)D,$ so at most $D H_w$ steps to reach $0.$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$