Бат, Великобритания, 2019 год

Банк города Бат выпускает монеты с буквой $H$ на одной стороне и буквой $T$ на другой стороне. Гарри разложил $n$ таких монет в ряд слева направо. Он последовательно производит следующую операцию: если в ряду ровно $k > 0$ монет лежат букой $H$ кверху, то он переворачивает $k$-ю слева монету; иначе все монеты лежат буквой $T$ кверху, и он останавливается. Например, если $n=3$ и процесс начинается с конфигурации $THT,$ то последовательность операций выглядит так $THT \to HHT \to TTT,$ то есть процесс остановится после трех операций.
   a) Докажите, что при любой начальной конфигурации процесс остановится после конечного числа операций.
   b) Для каждой начальной конфигурации $C$ через $L(C)$ обозначим количество операций, после которых процесс остановится. Например, $L(THT) =3$ и $ L(TTT)=0.$ Найдите среднее арифметическое значений $L(C),$ когда $C$ пробегает все $2^n$ возможных начальных конфигураций.

Комментарий/решение

Пусть $1234...n$ это места в конфигурации, будем оставлять $A$ (номер места) только те места которая занимает буква $H$, к примеру $THT$ - $H$ занимает $2$ место значит для него номер $A(2)$.

a)

Так как на каждом шагу одна цифра либо прибавляется либо убавляется в зависимости от количества цифра в данный момент процесса, то каждом шагу будем получаться разные числа, тогда сопоставим параллельно данной конфигурации, конфигурацию $B$ убывающие числа, равному количества цифр в данной конфигурации $L(C)$ и начинающегося в обратном порядке, к примеру $L(HHTTTH)=A(126)$ к ней параллельно $B(321)$, отметим что процесс перемещения будет начинаться с первой цифры $B$, будем продолжать такой процесс, выписывать цифры которые "убавились и прибавились" на том же примере, дополнительно впишем в этот процесс третий ряд который будет описывать количество шагов до завершения $C$

$A(1,2,6)=1236,12346,123456,12345,1234,123,12,1,0=9$

$B(3,2,1)$

$C(+3,+4,+5,-6,-5,-4,-3,-2,-1)=9$

Процесс начинается с первой цифры $B$, тогда описать процесс можно таким образом:

$A(a_{1},a_{2},a_{3},...a_{k})$

$B(k,k-1,k-2,...1)$

$C(+,-)$

Процесс будет считаться остановленным если последняя отнимаемая цифра будет $-1$

Если в ряду $A$ нету цифры $k$ то на это число ряд $A$ прибавляется, в противном случае убирается, если прибавилось добавляем в ряд $C$ знак $+$ в противном случае $-$, процесс $+$ в ряде будет происходит в зависимости от того есть ли это $k+1 -> k+2 -> ...$ цифра в ряде $A$, процесс $+$ очевидно остановится на определенной цифре $a_{t}$ в этом ряду так как числа расположены по возрастанию и процесс начинался с $k$ цифры , тогда такое же количество $-$ в ряде $C$ будет убираться следует из условия, тогда в ряде $C$ в совокупности знаков $-$ будет такое количество что и $+$, процесс остановится на определенной цифре в ряду $A$ если это не $1$ продолжаем процесс, откуда рано или поздно процесс дойдет до $1$ цифры в ряде $B$, тогда учитывая выше сказанное:

если $A(a_{1}a_{2}a_{3}...a_{k})$ тогда в ряде $C$ чисел со знаком $+$ будет в количестве $S=(a_{1}+a_{2}+...+a_{k})-(1+2+3+...k)=x-y$ но так как чисел со знаком минус будет аналогичное количество отличающегося лишь на количество цифр в ряду $A$ которое равно $k$ то есть чисел со знаком $-$ будет в количестве $S+k=x-y+k$ ,тогда количество операции до остановки равно сумме этих количеств $L=2(x-y)+k$ шагов до остановки

Например для $L(C)=(HHTTTH)=A(1,2,6)=B(3,2,1)$ для него $L=2S+3=2(1+2+6-(1+2+3))+3 = 9$

b) Опишем всевозможные конфигурации, для этого с теми же рассуждениями, опишем их через ряд $A$ в пункте выше.

Если рассмотреть расположения $2^n$ монет, то описать все возможные расположения монет буквой $H$ можно следующим образом, разбив числа от $[1,n]$ на две группы $0,1, \ 2, \ 3....n-4$ и $n-3, \ n-2, \ n-1, \ n$ тогда разбиение разобьется на $C_{n-4}^0+C_{n-4}^1+...+C_{n-4}^{n-4}=2^{n-4}$ и в каждой из них будет $2^4$ различных возрастающих расположении оставшихся $n-3, \ n-2, \ n-1, \ n$ чисел. На пример $n=6$

$[[0],6,5,56],[4,46,45,456],[3,36,35,356],[34,346,345,3456]$

$[[2],26,25,256],[24,246,245,2456],[23,236,235,2356],[234,2346,2345,23456]$

....

$[[12],126,125,1256],[124,1246,1245,12456],[123,1236,1235,12356],[1234,12346,12345,123456]$ где двойными скобками обозначены число сочетаний из $C_{2}^0+C_{2}^1+C_{2}^{2}=2^2$

чтобы найти количество всех операции $2^n$ изначальных конфигурации, из пункта $a$ следует что нужна найти сумму

$\sum 2(x-y)+k $ по всем $2^n$ изначальных конфигурациям, но для начало решим такую задачу, для примера пусть имеется $1,2,3$ набор чисел найдем число сочетаний по $2$ и $C_{3}^2 = 12,13,23$ обозначим $|C_{3}^2|$ сумму всех цифр в сочетании $1+2+1+3+2+3$ тогда найдем сумму всех таких $S_{1}=|C_{t}^1|+|C_{t}^2|+...+|C_{t}^t|$ для этого отметим

Тогда отметим что для каждого $|C_{t}^1| = C^{0}_{t-1} \cdot \dfrac{t(t+1)}{2}$ для $|C_{t}^2| = C^{1}_{t-1} \cdot \dfrac{t(t+1)}{2}$ и т.д , тогда $S_{1}=|C_{t}^1|+|C_{t}^2|+...+|C_{t}^t| = \dfrac{t(t+1)}{2} \cdot (C^{0}_{t-1}+C^{1}_{t-1}+...+C^{t-1}_{t-1}) = 2^{t-1}$ (Бином Ньютона) то есть $S_{1} = 2^{t-1} \cdot \dfrac{t(t+1)}{2} = 2^{t-2} \cdot t(t+1)$

1) Найдем сумму по всем $2^n$ суммы $x$ (сумма мест расположении в ряде $A$), из структуры разбиения следует что сумму $x = 2^2 \cdot 2^2 \cdot (|C_{n-4}^1|+|C_{n-4}^2|+...+|C_{n-4}^{n-4}|) + 4 \cdot 2 \cdot (n-2+n-3) + 2^{n-2} \cdot (n+n-1) = 2^{n-2}n(n+1)$

2) Найдем сумму по всем $2^n$ суммы $y$, для начало покажем что $\sum\nolimits_{k=0}^n k^2 \cdot C_{n}^{k} = 2^{n-2}n(n+1)$ $(1)$

это следует из того что

$k \cdot C_{n}^k = \dfrac{kn!}{(n-k)!k!} = \dfrac{n \cdot (n-1)!}{(n-k)!(k-1)!} = n \cdot C_{n-1}^{k-1}$

Тогда $ \sum\nolimits_{k=0}^n k^2 \cdot C_{n}^{k} =\sum\nolimits_{k=0}^n (k(k-1)+k) \cdot C_{n}^k$ = $ \sum\nolimits_{k=0}^n (k(k-1) \cdot C_{n}^k + k \cdot C_{n}^k)$=

$\sum\nolimits_{k=0}^n ((k-1) \cdot n \cdot C_{n-1}^{k-1} + n \cdot C_{n-1}^{k-1}) = \sum\nolimits_{k=0}^n (n(n-1) \cdot C_{n-2}^{k-2} + n \cdot C_{n-1}^{k-1}) $ = $n(n-1)2^{n-2}+n \cdot 2^{n-1} = 2^{n-2} \cdot n(n+1)$ .

Отметим что $y=C_{n-4}^0 \cdot S_{l_{0}} + C_{n-4}^1 \cdot S_{l_{1}} + .... + C_{n-4}^{n-4} \cdot S_{l_{n-4}}$

где $S_{l_{1}}$ применительно для $n=6$ выше $[1,1+2,1+2,1+2+3],[1+2,1+2+3,1+2+3,1+2+3+4],[1+2,1+2+3,1+2+3,1+2+3+4],[1+2+3,1+2+3+4,1+2+3+4,1+2+3+4+5]$ и очевидно что для каждого сочетания они будут одни и те же поэтому надо их умножить на это число сочетании. Для него можно рекурретно выразить $S_{l} = 8l^2+40l+56$

Тогда по $(1)$ суммируя по частям получим $\sum\nolimits_{k=0}^{n-4} 8l^2 \cdot C_{n-4}^{l} = 8 \cdot 2^{n-6}(n-4)(n-3) = 2^{n-3}(n-4)(n-3)$

Аналогично $ 40 \cdot \sum\nolimits_{k=0}^{n-4} k \cdot C_{n-4}^{k} = 40 \cdot 2^{n-5}(n-4)$ и последняя

$56 \sum\nolimits_{k=0}^{n-4} C_{n-4}^k = 56 \cdot 2^{n-4}$

Суммируя $y=2^{n-3}(n-4)(n-3)+40 \cdot 2^{n-5}(n-4) + 56 \cdot 2^{n-4} = 2^{n-3}n(n+3)$

3) Cумму цифр $k$ для всех $2^n$ конфигурации. можно посчитать можно рекуррентно $k=2^(n-1) \cdot n$

4) Тогда общее количество всех операции равно $L=2(x-y)+k = 2(2^{n-2}n(n+1) - 2^{n-3}n(n+3)) + 2^{n-1} \cdot n = 2^{n-2} \cdot n(n+1) $

Ответ среднее арифметическое равно $\dfrac{2^{n-2} \cdot n(n+1)}{2^n} = \dfrac{n(n+1)}{4}$

В примере с $THT$ забыта одна операция:

$$THT\to HHT\to \boxed{HTT}\to TTT.$$