Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
A copy is a replica of something. So there are at least 3 of the same object? Also, define "blackboard". Is it a set? –  Don Larynx Dec 19 '13 at 5:36
9  
@DonLarynx Really, just think of it as a blackboard. You write down the number $k$ a total of $n$ times. That's really all. Please let me know if anything is still unclear. –  PJ Miller Dec 19 '13 at 5:38
2  
@PJMiller In your example, a move could also change the set to (0,0,0), yes? Just to be complete... –  Matthew Conroy Dec 19 '13 at 6:18
2  
We can always make at least $k(n-1)$ steps. Denote by $M(i,j)$ the move consisting in replacing integers number $i$ and $j$ by the value formerly located at $j$, minus one. Starting from the initial position $(k,k,k,k,\ldots ,k)$, and applying successively $M(1,2),M(2,3),M(3,4), \ldots ,M(n-1,n)$, we reach $(k-1,k-1,k-1,k-1,\ldots ,k-1)$ in $n-1$ steps. Iterating this, we eventually reach $(0,0,\ldots,0)$ in $k(n-1)$ steps. –  Ewan Delanoy Dec 19 '13 at 6:44
3  
The maximal number of moves $f(n,k)\le n(2^k-1)$. Proof. For each non-negative number $m$ define its weight $w(m)=2^m-1$. Then $w(m)+w(0)>2w(m-1)$ for each $m\ge 1$. Therefore at each move the total weight of the numbers on the blackboard is decreasing. Hence the maximal number of moves $f(n,k)$ is not greater than the initial total weight $n(2^k-1)$. –  Alex Ravsky Dec 19 '13 at 7:49

4 Answers 4

up vote 5 down vote accepted

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 
share|improve this answer
1  
It seems for me that, unfortunately, we have no proof of the optimality of this greedy algorithm. The problem is that you have proved its local, but not global optimality with respect to the decreasing of the weight (which in your case is equal to the $(T+1)$-base expansion) of the collection of the numbers. In particular it means that there is possible a situation when a move which slightly decreases the weight, makes the position so bad that every possible next move strongly decreases the weight. –  Alex Ravsky Dec 19 '13 at 9:57

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

share|improve this answer
    
It seems that your strategy coincides with the described in this comment. So you can wrote the program calculating the respective values for small $n$ and $k$ and then try to find a general formula for them. Maybe I myself shall wrote this program but I am still hoping to find a more simple way to derive the formula. –  Alex Ravsky Dec 19 '13 at 8:39
1  
@ronno I did the computation for $n=2$ to $n=5$ and the values correspond exactly to your table. AlexRavsky This seems to be related to sum of consecutive powers and I found some guides here. But looking at the series it seems like quite a mess. –  Yong Hao Ng Dec 19 '13 at 10:00
    
It seems that the sum formulas imply $f(n,k)=f(n-1,k)+g(n-1,k)$ and $g(n,k)=g(n,k-1)+g(n-1,k-1)+1$. –  Alex Ravsky Dec 19 '13 at 10:52
    
Moreover, it seems then $f(n,k)=f(n-1,k)+f(n,k-1)-f(n-2,k-1)+1$. –  Alex Ravsky Dec 19 '13 at 10:56
1  
From the recurrence for $f$, a lower bound of $\Omega(k^{n-1})$ seems difficult, since asymptotically $k^{n-1} \gg k^{n-2}$. –  ronno Dec 19 '13 at 11:28

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

share|improve this answer

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) 
share|improve this answer
1  
I happened to notice that going down columns, when $n=3$ the first difference (i.e, $5-2,9-5,14-9,\ldots$) is $3,4,5,\ldots$, while for $n=4$, the first difference is $5,8,12,17,\ldots$ but the second difference is $3,4,5,\ldots$. For $n=5$, the first difference is $7,12,20,32,49\ldots$, the second difference is $5,8,12,17,\ldots$, and the third difference is $3,4,5,\ldots$. This is pure observation, though, without proof or even checking all the numbers. –  Barry Cipra Dec 25 '13 at 17:58
1  
Just to summarize (and simplify) the observation of my previous comment, the first difference for column $n$ appears to be the second difference for column $n+1$. –  Barry Cipra Dec 25 '13 at 18:15
1  
Ah, I see my observation agrees with Edit 1 in Yong Hao Ng's answer. –  Barry Cipra Dec 25 '13 at 18:54
1  
@PJMiller yes it's $f(n,k)$. I made my program available in the answer for you. –  Xoff Dec 25 '13 at 20:19
1  
@BarryCipra Yes it seems that : $$f(n+1,k+1)=f(n+1,k)+f(n,k)+n $$ –  Xoff Dec 25 '13 at 20:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.