Decreasing integers on the blackboard There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the blackboard (you can choose which one) by the integer $m-1$.
For example, if you have numbers $(3,0,1)$ on the blackboard, a move can change them to $(2,2,1)$ or $(2,0,2)$ or $(3,0,0)$ or $(0,0,0)$.
What is the maximum possible number $f(n,k)$ of moves you can perform? An asymptotic answer would be good enough (I think it could be $O(kn^2)$).

I can prove an exact answer for $n=3$ which I can extend to an algorithm for $n\geq 4$.
The number of steps seems to correspond to ronno's table.  
[1] Best Algorithm for $n=3$
Let $n=3$ and we start with $(k,k,k)$.
Consider the algorithm:
A series of $M(1,2): (k,k,k)\to (0,0,k)$.
$M(3,2): (0,0,k)\to (0,k-1,k-1)$
A series of $M(1,2): (0,k-1,k-1)\to (0,0,k-1)$.
$M(3,2): (0,0,k-1)\to (0,k-2,k-2)$
$\dots$  
This will give me $\dfrac{(k+1)(k+2)}{2}-1=\dfrac{k^2+3k}{2}$ moves.  
I claim that it is the maximum via induction.
Clearly this is true for $k=0$.
Now consider $(k+1,k+1,k+1)$.
The algorithm tells me that $\dfrac{(k+1)^2+3(k+1)}{2}=\dfrac{k^2+5k+4}{2}$ is a lower bound.  
The first move must give me $(k,k,k+1)$.
If I next make it $(k,k,k)$, the maximum I can get is $2+\dfrac{k^2+3k}{2}=\dfrac{k^2+3k+4}{2}<\dfrac{k^2+5k+4}{2}$.
Hence I can only possibly beat the lower bound by making my next move $(k-1,k-1,k)$.
It is clear that using this argument, I have to reach $(0,0,k+1)$.
For otherwise on the $r+1$-th step I will get $(k-r,k-r,k+1)\to (k-r,k,k)$.
Then the maximum moves is $r+1+\dfrac{k^2+3k}{2}=\dfrac{k^2+3k+2+2r}{2}$, which is always $\leq \dfrac{k^2+5k+4}{2}$ since $r\leq k+1$.  
[2] Extending to $n \geq 4$
The most "natural" generalization of this algorithm for $n\geq 4$ is to:
(1) Reduce to $(0,0,0,k,\dots,k)$ via $n=3$ algorithm.
(2) $(0,0,0,k,\dots,k)\to (0,0,k-1,k-1,\dots,k)$.
(3) $(0,0,k-1,k-1,\dots,k)\to (0,k-2,k-2,k-1,\dots,k)$.
(4) Repeat $n=3$ algorithm on $(0,k-2,k-2)$.
(5) Repeat procedure. For instance the next "start" would be $(0,k-3,k-3,k-2,\dots,k)$.  
It should be possible to derive a formula, but I have no idea how to do it in a short way.  
Edit 1: The first few formulas are
$n=3: \dfrac{k(k+3)}{2}$, $n=4: \dfrac{k(k^2 + 3 k + 14)}{6}$, $n=5: \dfrac{k(k^3+2k^2+23k+70)}{24}$.  
In general the algorithm seems to give about $O(k^{n-1})$.  
The computation is using:
$$g(n,k)=k+\sum_{i=1}^{k-1} g(n-1,i)$$
$$f(n,k)=\sum_{i=2}^{n} g(i,k)$$
with initial condition $g(2,k)=k$, where $f(n,k)$ is the solution we want.
$g(n,k)$ is the number of steps for $(0,0,\dots,0,k)$.
