1
$\begingroup$

Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $a(n)$ is the number of steps required to get one ball in each box when a step consists of moving to the next box every second ball from the highest-numbered box that has more than one ball.

I conjecture that for $n=2^k$ ($k>0$) we have $$a(n)=\frac{n(n-k+1)}{2}-1$$

To verify given conjecture one may use this PARI prog:

a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]==0, B=n; while(v[B]<2, B--); v[B+1]+=v[B]\2; v[B]-=v[B]\2; A++); A

Is there a way to prove it?

I would also like to know if a closed form or recurrence is possible for $a(n)$ in general.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Have you tried computing $a(n)$ for, say, $n=2,3,\dots,10$ and then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$
    – Gerry Myerson
    Commented Oct 18, 2022 at 22:58
  • $\begingroup$ @GerryMyerson, thank you for comment! Yes, but to no avail. $\endgroup$
    – Notamathematician
    Commented Oct 19, 2022 at 6:17
  • 1
    $\begingroup$ Followup question by OP: mathoverflow.net/questions/432834/… $\endgroup$
    – Gerry Myerson
    Commented Oct 20, 2022 at 22:23

1 Answer 1

Reset to default
2
$\begingroup$

The reason is that for $n=2^k$ the following recursion holds:
$a(n)=1+2a(n/2)+(n/2-1)n/2$.
To see why this holds, notice that first you split the $n$ balls into two groups of $n/2$, one group in the first box, the other in the second.
After that, you do $a(n/2)$ steps for the balls in the second box.
Then, you do $a(n/2)$ steps for the balls in the first box, except that you need to move all but one ball (which stays in the first box) $n/2$ positions farther.
In these latter steps, only one ball moves each time.
Once you have the recursion, it is straight-forward to verify your formula.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for answer! Could you please also prove the recurrence: $a(n)=\frac{n(n-1)}{2}-b(n)$ for $n>0$ where $b(n)=b(\left\lfloor\frac{n}{2}\right\rfloor)+c(\left\lceil\frac{n}{2}\right\rceil-2)+\left\lfloor\frac{n}{2}\right\rfloor-1$ for $n>3$, otherwise $b(n)=0$ and where $c(n)$ is A181132. $\endgroup$
    – Notamathematician
    Commented Oct 19, 2022 at 10:57
  • 1
    $\begingroup$ I'm not so sure about that... Maybe you can pose it as another question and someone might answer it. $\endgroup$
    – domotorp
    Commented Oct 19, 2022 at 12:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .