Decreasing integers on the blackboard

Question

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)$).

Answer 1

As @Alex noted, the following proves the local optimality of his and @Yong's algorithm in some measure. In fact the measure I use cannot prove global optimality on general states, since the score for $(5,5,1,0,0)$ is $56$ while that for $(5,4,4,4,4)$ is $58$. In two optimal steps each, the sequences reach $(5,4,4,0,0)$ and $(5,4,4,2,2)$ respectively, where it's easy to see that the second is at least two steps better.

5,4,4,4,4    5,5,1,0,0
5,4,4,3,3    5,4,4,1,0
5,4,4,2,2    5,4,4,0,0

Let $T$ be $k+1$. $a_i$'s. First observation, if we are picking $i$ and $j$, then we should always replace them by the bigger of $a_i-1$ and $a_j-1$. Write down the numbers in decreasing order and read them as an $(T+1)$ base expansion so that $a_i$ corresponds to $a_i(T+1)^i$. So then $j>i$.

Now after the operation, the $a_j-1$ that replaces $a_i$ moves to $j-1\ge i$, and everything in between is shifted to the right. Then the operation to be done is subtract $\delta \ge (T+1)^j - T\times(T+1)^k >0 $. Note that by construction, either $a_j-1 \ge a_i$ or $a_j = a_i$.

So first of all, the base $(T+1)$ number decreases. We can see what makes this decrease the smallest. We have the bounds $$(T+1)^{j-1} \leq \delta \le (T+1)^j$$

So for a given $i$, $j$ should be as low as possible.

If $a_i =0$, this means $j$ should be the smallest such that $a_j>0$, and then $i$ does not matter.

Otherwise, $j = i+1$, and then the same bounds tell us that $i$ should be as low as possible.

Some upper bounds are below.

---

First, starting from any state of the blackboard, we can make only finitely many moves. To see this, first note that in any move, we cannot increase the maximum. Now, we induct on number of terms on the board.

Note that once a maximal term occurs as $i$ or $j$ in a move $M(i,j)$ as in Ewan's comment and answer, it cannot get back to its original value again, since if $T$ is the maximum value, then every replacement is with at most $T-1$. Now, it is enough to show that the maximum has to decrease in a finite number of moves. Assume on the contrary that there is an infinite sequence of moves that preserves the maximum. Then, some maximal value not be used in a move at all. But by induction, there are only finitely many possible moves that can be made on the rest of the terms.

This also tells us that there cannot be any periodic set of states, so that the total possible number of states ($-1$) is an upper bound. The number of states is the number of non-increasing sequences of length $n$ where every term is $\le k$. This is given by $\binom{k+n}{k}-1$. A slightly better upper bound is below.

Now, suppose that for a multiset of size $n$, with maximum $T$, the maximum number of moves possible (over all such multisets) is $f(T,n)$. Obviously, $$f(T,2 ) = T$$. By the same argument as above, $$f(T,n+1) \le f(T,n)+f(T-1,n) +1 $$ By induction, $f(T,n) \le \binom{T+n-1}{T} - 1 \le (T+1)^n-1$ but this seems to have room for improvement.

@AlexRavsky's upper bound is much better for a fixed $k$, while this is better for a fixed $n$.

Here are some actual values for the $k,n$ defined in the problem, and the best of the two upper bounds above, $\binom{k+n-1}{n-1}-1$ and $n(2^k-1)$:

k\n|   2   3   4   5   6   7   8          k\n|   2   3   4   5   6   7   8  
---+-----------------------------         ---+-----------------------------
 1 |   1   2   3   4   5   6   7           1 |   1   2   3   4   5   6   7
 2 |   2   5   8  11  14  17  20           2 |   2   5   9  14  18  21  24
 3 |   3   9  16  23  30  37  44     <     3 |   3   9  19  34  42  49  56
 4 |   4  14  28  43  58  73  88     =     4 |   4  14  34  69  90 105 120
 5 |   5  20  45  75 106 137               5 |   5  20  55 125 186 217 
 6 |   6  27  68 124 186                   6 |   6  27  83 209 378 
 7 |   7  35  98 196                       7 |   7  35 119 329 

Answer 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)$.

Answer 3

I made a small program to compute the value $f(n,k)$ for small $n$ and $k$.

$$\begin{array}{l|cc} k^\mbox{$\;\;n$}& 2& 3& 4 & 5& 6 & 7 & 8 & 9 & 10 & 11\\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 2 & 5 & 8 & 11 & 14 & 17 & 20 & 23 & 26 & 29 \\ 3 & 3 & 9 & 16 & 23 & 30 & 37 & 44 & 51 & 58 & 65 \\ 4 & 4 & 14 & 28 & 43 & 58 & 73 & 88 & 103 & 118 & 133 \\ 5 & 5 & 20 & 45 & 75 & 106 & 137 & 168 & 199 & 230 & 261 \\ 6 & 6 & 27 & 68 & 124 & 186 & 249 & 312 & 375 & 438 & 501 \\ 7 & 7 & 35 & 98 & 196 & 315 & 441 & 568 & 695 & 822 & 949 \\ 8 & 8 & 44 & 136 & 298 & 516 & 762 & 1016 & 1271 & 1526 & 1781 \\ 9 & 9 & 54 & 183 & 438 & 819 & 1284 & 1785 & 2295 & 2806 & 3317 \\ 10 & 10 & 65 & 240 & 625 & 1262 & 2109 & 3076 & 4088 & 5110 & 6133 \\ 11 & 11 & 77 & 308 & 869 & 1892 & 3377 & 5192 & 7172\\ \end{array} $$

It seems that values from ronno are good. Note that it seems that for $n\ge k$, $f(n+1,k)=f(n,k)+2^k-1$

And $f(n,n)$ seems to be A058877 = $n(2^{(n-1)}-1)$

---

Here is the program I made (python 3.3). It could be improved ! Because I used recursive calls to write it quickly, but it's not that good in python.

import functools
import sys

@functools.lru_cache(maxsize=None)
def val(t) :
    res=[]
    pi= -1 
    for i in range(len(t)) :
        if t[i]>0 and t[i] != pi :
            pj= -1
            for j in range(len(t)) :
                if j != i and t[j] != pj :
                    newt=list(t)
                    newt[i]-=1
                    newt[j]=newt[i]
                    newt.sort()
                    res.append(val(tuple(newt)))
                    pj=t[j]
        pi=t[i]
    return(0 if res==[] else 1+max(res)) 


def vval(k,n) :
    return(val((k,)*n))

def main(m) :
    sys.setrecursionlimit(100000)
    for k in range(1,m) :
        print(k,end=" ")
        for n in range(2,m) :
            print("&",vval(k,n), end=" ")
            sys.stdout.flush()
        print("\\\\")

main(12) 

Answer 4

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} $$