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)$).
 A: That's another answer that comes from all ideas in other answers.
Consider a blackboard $B$ with $n$ numbers $a_1,a_2,\dots,a_n$, such that $a_i\le a_{i+1}$.
Let $W$ the weight function defined by 
$$W(B)=\sum_{i=1}^n \sum_{k=1}^{i-1}\binom{a_i}{k} $$
Let's make a move in $B$. So we choose $1\le i\le n$, and $1\le j\le n$ (with $j\neq i$), and transform $a_i$ (and $a_j$) into $a_{i}-1$ to obtain the blackboard $B'$ with $n$ value $b_1,b_2,\dots,b_n$ ($b_i\le b_{i+1}$ : We order the values again)


*

*if $a_j\ge a_i$, then both value are reduced. By trivial induction, $b_i\le a_i$ (and for some $i>1$, we have $b_i<a_i$) and $W(B')<W(B)$.

*if $a_j<a_i$, we can consider (without loss of generality) that $a_i>a_{i-1}$. Hence $B'$ will be such that :


*

*for $i< k\le n$ : $b_k=a_k$

*$b_{i-1}=b_i=a_i-1$ (that's former $a_i$ and $a_j$)

*for $j\le k<i-1$ : $b_k=a_{k+1}$ (we just move former $a_j$ from index $j$ to index $i-1$)

*for $k<j$ : $b_k=a_k$
Hence : 
$$W(B)-W(B')=\sum_{k=j}^{i}\sum_{l=1}^{k-1}\binom{a_k}{l}-\binom{b_k}{l}$$
For $k=i$, we have :
$$\left(\sum_{l=1}^{i-1}\binom{a_i}{l}-\binom{a_i-1}{l}\right)=\sum_{l=1}^{i-1}\binom{a_i-1}{l-1}=1+\sum_{l=1}^{i-2}\binom{b_{i-1}}{l}$$
Hence (I let the attentive reader understand the cancellations that come from $b_k=a_{k+1}$) $$W(B)-W(B')=1+\sum_{l=1}^{j-1}\binom{a_j}{l}+\sum_{k=j+1}^{i-1}\binom{a_k}{k-1}>0$$
Note that now, if you take $j=1$ and $a_i$ ($i>1$) the smallest $a_k>0$, you will have
$$W(B)-W(B')=1$$
So $W(B)$ is the maximum number of moves that you can play into $B$.
$$f(n,k)=\sum_{i=1}^{n-1} (n-i)\binom{k}{i} $$
A: 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)$.
