Число шагов, требуемых для получения 1 шара в каждой коробке

[kthxbye]

Дано $n$ шаров, которые изначально лежат в первой из $n$ пронумерованных коробок. Пусть $a(n)$ - это число шагов, требуемых для получения одного шара в каждой коробке, где шагом называется перемещение в следующую коробку каждого второго шара из коробки, в которой лежит более одного шара, и номер которой относительно других таких коробок максимален.

Я предполагаю, что для $n=2^k$ ($k>0$) будем иметь

$$a(n)=\frac{n(n-k+1)}{2}-1$$

Вот простенькая программка на PARI для проверки результата:

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

Есть ли способ доказать мою гипотезу (или же опровергнуть ее)?

Возможна ли в общем виде для $a(n)$ формула без рекурсии?

[Null]

Что делать если в коробке нечетное $2k+1$ шаров? Вы $k$ перекладываете?

[kthxbye]

Null в сообщении #1567106 писал(а):

Что делать если в коробке нечетное $2k+1$ шаров? Вы $k$ перекладываете?

Именно так (что можно также заметить из программки на PARI). Мне кажется это очевидным, если задано условие "каждый второй".

[bot]

kthxbye в сообщении #1567109 писал(а):

Мне кажется это очевидным, если задано условие "каждый второй".

С чего это вдруг очевидно? А мне, кажется, более очевидным разрезать последний шар пополам и переложить вторую половинку.

[DeBill]

kthxbye
Ваша формула ломается при $k=5$...
Вообще, сомнительно получить хорошую формулу - даже для степеней двоек: начиная с 6, начинается некий разнобой для $6+0$ единичек, и $6+s$ единичек.

[wrest]

DeBill в сообщении #1567307 писал(а):

Ваша формула ломается при $k=5$...

Я проверял до $k=10$, всё пучком, соответствует

$$a(2^k)=\frac{2^k(2^k-k+1)}{2}-1$$

Табличка:

k   a(2^k)
1   1
2   5
3   23
4   103
5   447
6   1887
7   7807
8   31871
9   129023
10   519679

Первая производная (первая разность) болтается чуть ниже $n$ и в степенях двойки - равна $n$, т.е. $a(2^k+1)-a(2^k)=2^k$, а вторая разность ходит туда-сюда, причем $a(2^k)-2a(2^k-1)+a(2^k-2)=k$

Картинка

На картинке
$a''(n)=a(n)-2a(n-1)+a(n-2)$
$a'(n)-n=a(n)-a(n-1)-n$
Прощу прощения за разнобой в разностях (то влево то вправо), ну думаю общая картна не меняется.
Соответственно на картинке синий график не достаёт до нуля из-за этого разнобоя.

[DeBill]

wrest
Да, я там в арифметике ошибся -это у меня бывает.
kthxbye
И да, формула действительно правильная. А доказывать ее можно по индукции.
Пусть $b(2^k,s)$ - число шагов для случая "в первой кучке - $2^k$ шаров, а в остальных $s$ кучках - по одному".
Имеем рекуррентные равенства
$b(2^{k+1},s) = 1+b(2^k+1,s-1)+b(2^k,2^k+s)$

$b(2^{k+1},0)=1+b(2^k,0)+ b(2^k,2^k)$,

и аналогичные для $ b(2^k+1,s), b(2^k+1,0)$.

По индукции проверяем, что

$b(2^k,s)=-1+s(2^k-1)+2^{k-1}(2^k-k+1)$, $b(2^k+1,s)=-1+s\cdot 2^k+2^{k-1}\cdot (2^k-k+3)=b(2^k,s)+2^k+s$