Часть А вроде бы совсем проста. Докажем по индукции.

База. Если есть одна буква и это Т, то всё ок. Если это Н, то будет Н-->Т и вcё ок.

Шаг. Пусть верно для всех последовательностей из не более чем N букв. Рассмотрим последовательность из N+1 буквы. Если последняя буква T, то всё ок, т.к. она ни на что не повлияет и можно ее отбросить. Остаётся последовательность из N букв, а там всё хорошо по предположению индукции.

Если последняя буква Н, то докажем, что она когда-нибудь превратится в T (и тогда всё будет ок по написаному выше.

Наблюдение 1: если в начале строки стоит ровно N букв Н, то всё хорошо, это вызывает переворот последней N+1 буквы Н.
Наблюдение 2: если в начале строки стоит k<N букв H, то их число не может уменьшиться (пока N+1 буква H не станет T). Действительно, в любой момент времени в строке будет находиться как миниммум k+1 буква Н (k первых и 1 последняя). Значит, первые k переворачивать не придётся. Наблюдение 3: если в начале строки стоит 0 букв H, то их тут же станет 1. Наблюдение 4: если в начале строки стоит 0<k<N букв Н, то в какой-то момент их станет k+1. Действительно, пусть это не так и k+1 буква всегда будет T. Но по сказанному выше первые k букв Н ни на что не влияют (до тех пор пока N+1 буква всё ещё T). Отбросим их. Получим строку из не более чем N символов T...H, с той же эволюцией, что и у необрезанной строчки. По предположению индукции это строчка станет в какой-то момент TT...TTT. Значит, последняя Н будет перевёрнута. Значит все первые символы будут H. Значит в частности и первый символ будет Н, что противоречит тому, что он всегда будет T. Из наблюдений 1-4 вытекает, что в какой-то момент в строке будут первые N символов Н, что вызовет переворот последний N+1 буквы, которая станет T. После этого отбросим ее и, по предположению индукции, первые N букв тоже станут Т.

Пусть Gn - граф переходов последовательностей длины n. Очевидно, что граф переходов последовательностей длины n+1 оканчивающихся T совпадает с Gn. Чуть менее очевидно, что граф последовательностей длины n+1 оканчивающихся H тоже совпадает с Gn: переворот k монеты слева является переворотом n-k+1 монеты справа в укороченной последовательности без последней H, и поскольку количество T в такой последовательности равно n+1-k, мы можем считать количество T, l = n+1-k, и переворачивать l-ю монету справа в укороченной последовательности до тех пор пока не получим последовательность из одних H. Таким образом граф Gn+1 состоит из двух подграфов Gn, один из которых присоединен к другому в вершине HH...H.
Пусть Sn - сумма переходов от всех вершин до TT..T, тогда Sn+1 = Sn + (Sn + 2^(n-1)*n), поскольку количество переходов от HH...H до TT...T равно n. Легко показать, что Sn = n(n-1)2^(n-2), и среднее значение по всем вершинам графа Sn/2^n = n(n-1)/4.

В целом все верно, но где-то мелких недочет - ответ n(n+1)/4.

Конечно n(n+1)/4. Это я на последнем шаге сумму 1+2+...+n неверно записал.

a) Если процесс никогда не остановится, то ввиду конечного числа конфигураций монет (2^n), он обязан зациклиться. Возьмем один такой цикл, и пусть K - наибольшее число монет с H, которое встречается среди конфигураций этого цикла. Тогда всякий раз, когда цикл проходит через конфигурацию с K монет с H, он обязан перевернуть монету номер K, и ввиду максимальности K ее значение обязано измениться H->T, а не T->H. Но тогда ее значение никогда не вернется в H, что противоречит циклу.

b) Разделим все конфигурации C из n монет на две группы: с конечной монетой T и конечной монетой H.

Ясно, что для монет первой группы значения L(C) совпадают с таковыми для конфигураций из n-1 монет (конечная T никогда не меняется и ее можно просто отбросить).

С другой стороны, монеты с конечной H должны рано или поздно перевернуть эту H (ввиду пункта а) ), а это может случиться только в конфигурации "все H". По достижении этой конфигурации еще ровно через n шагов получаем "все T". По сути, стремясь к "все H", мы смотрим на развитие конфигураций из первых n-1 монет, но - из-за влияния последней n-ной H - с правилом "меняем k+1-ю монету, когда есть k H" вместо обычного правила "меняем k-ю монету, когда есть k H".

Но если среди n-1 монет есть k монет с H, значит, есть n-k-1 монет с T; более того, менять k+1-ю монету с начала - все равно, что менять n-(k+1)=n-k-1-ю монету с конца. Значит, если мы прочитаем последовательность от конца к началу, а также поменяем все T на H и наоборот, мы получим "обычные" правила для n-1 монет. Эта "перевернутая" последовательность дойдет до T...T за столько же шагов, за сколько наша исходная - до H...H.

Итак, половина конфигураций из n монет доходит до T...T за столько же шагов, сколько соответствующие конфигурации из n-1; а вторая половина - за столько же шагов, за сколько соответствующие ("перевернутые") конфигурации из n-1, плюс добавочные n шагов для каждой конфигурации (поход из H...H в T...T). Значит, в при переходе от n-1 к n монет мы добавляем n/2 шагов к среднему значению. Суммируя все такие переходы от 1 до n, получаем среднее значение (1+2+3...+n)/2 = n(n+1)/4.

a решается легко.

Доказываем индукцией по n. Для n=1 утверждение очевидно: Н сразу превратится в Т. Пусть n>1.

Если крайне правая монета (кпм) Т, то Н-монет будет меньше n, значит, и на следующем шаге кпм будет T. Значит, по индукции по количеству шагов, кпм будет Т всегда. Значит, она не влияет на количество Н-монет, и все остальные монеты будут эволюционировать как если бы её не было, и по предположению индукции когда-нибудь все превратятся в Т.

Если крайне левая монета H, она увеличивает количество Н-монет на единицу, значит, остальные монеты эволюционируют как если бы её не было, и рано или поздно все станут Т. После этого крайне левая монета тоже превратится в Т.

Если крайне левая монета T, а крайне правая H, все монеты между ними эволюционируют так, как если бы крайних не было. Когда-нибудь они все превратятся в Т. После этого монеты слева направо одна за другой начнут превращаться в H. Когда все станут Н, монеты справа налево начнут превращаться в Т, пока все не станут Т.

Для б, чую я, есть какое-то соответствие между последовательностью букв и двоичным числом, в котором прибавляем/вычитаем единицу.

Но есть другое: пусть f(n) - среднее к-во шагов, а f(xy, n) - среднее к-во шагов, если есть n монет, первая x, последняя y.

f(n) = (f(HH,n)+f(HT,n)+f(TH,n)+f(TT,n)) / 4
Если из крайних монет одна H, другая T, они вместе не влияют на все остальные монеты. Поэтому:
f(HT, n) = f(n-2) + 1
f(TH, n) = f(n-2) + 2n-1
Правое Т и левое H не влияют на остальные монеты. Поэтому:
f(TT, n) = (f(TT, n-1) + f(TH, n-1)) / 2
f(HH, n) = (f(TH, n-1) + f(HH, n-1)) / 2 + 1

С этими формулами можно работать.

А вот и решение части Б. Ответ: N(N+1)/4.

Пусть для строки из N символов ответ f(N). Тогда f(1)=0.5.

Пусть мы знаем f(N), найдем f(N+1).

Строчка из N+1 символа - это строка из N символов (назовём ее А) и приписанный последний символ.

Есть два варианта. Если последний символ - T, то L(AT)=L(A).

Пусть теперь последний символ H. Проведём изоморфизм между графом действий для строк из N символов и графом действий для строк из N+1 символов, в которых последний элемент - H.

Строка A:=a_1...a_n перейдет в строку F(A):=(1-a_n)...(1-a_1)H (мы приняли соглашение 1-H=T и 1-T=H)

Я утверждаю, что это изоморфизм, т.е. если строка A переходила в строку B, то строка F(A) перейдёт в строку F(B). Действительно, если A перейдёт в B и в А k cимволов H, то в B те же символы, что в A, но на k-ом месте слева 1-a_k. То есть она выглядит так:

B=a_1...a_{k-1}(1-a_k)a_{k+1}...a_N

По построению, в строчке F(A) имеем N-k+1 cимволов H. Значит в том куда она переедет те же символы, что и в F(A), но на N-k+1 месте другой. Тогда она выглядит так:

(1-a_n)...(1-a_{k+1})a_k(1-a_{k-1})...(1-a_1)H

Легко видеть, что это в точности F(B).

Теперь, вычислим L(F(A)). По сказаному выше, имеем, L(F(A))=L(A)+L(НН...Н)=L(A)+N+1 (действительно, если А нужно R действий, чтобы перейти в TT...TT, то F(A) нужно R действий, чтобы перейти в НН...Н и N+1 действие чтобы из НН...Н добраться до ТТ....Т).

Следовательно имеем: L(AT)=L(A); L(AH)=L(A)+N+1. Поэтому среднее по больнице у графа строк из N+1 символов такое: F(N)+(N+1)/2.

Отсюду учим, что F(N+1)=F(N)+(N+1)/2. Учитывая, F(1)=0.5, легко находим F(N)=N(N+1)/4.

Пусть L(n) искомое среднее для n монет, а Х произвольный ряд монет.
Введем следующую инволюцию F на ряде из n монет:
сначала переворачиваем все монеты, затем меняем местами монеты с номером i и n-i (монета с номером n остается на месте). Эта операция коммутирует с операцией, описанной в задаче (за исключением ситуации, когда все монеты лежат одной и той же стороной вверх). Таким образом, если ряд монет вида XT сходится к TT...T за к шагов, то ряд F(XT) за те же к шагов придет к НН...Н. Ряд НН...Н приходит к TT...T за n шагов. Очевидно, что ряды вида XT сходятся в среднем за L(n-1) шагов, тогда ряды вида XН сходятся в среднем за L(n-1)+n шагов. L(n)=L(n-1)+n/2=n(n+1)/4.

Поскольку в процессе выполнения алгоритма никогда любая Т, находящаяся правее последней Н, не изменится, то без потери общности можем рассматривать каждую последовательность только до последней встречающейся Н, игноринуя все дальнейшие Т. В связи с этим удобно сопоставить состояние с двоичной записью некоего числа, т.е. ТТТ = 0, НТТ = 1, ННТ = 3 и т.д.

1. Доказательство конечности последовательности. Докажем, что для любого i двоичной длиной l(i) < n не более чем за 2n-1 шагов в его двоичной записи станет ровно на одну единицу меньше. Действительно, если на ближайшем шаге будет меняться 1 -> 0, то утверждение верно. Пусть на ближайшем шаге меняется 0 -> 1, тогда на следующем шаге будет менятся разряд на 1 старший за текущий. Не более чем через n шагов разряд окажется единицей, после чего алгоритм начнёт уменьшать разряды, и ещё через максимум n-1 шагов вернёт все разряды в начальное состояние, кроме ближайшей единицы справа (в двоичной записи) от первого изменяемого разряда - эта единица станет нулем. ЧТД.

Поскольку в двоичной записи числа длиной l < n не более n единиц, то самое большее через 2n²-2 шагов любое начальное состояние превратится в 0.

2. Сначала выведем рекурсивные формулы.

а) если к любому числу дописать младшим разрядом ещё одну единичку, то алгоритм повторится в точности так же до нуля, оставив только дописанную единичку, а затем следующим шагом эта единица перейдёт в 0, т.е. L(2*i+1) = L(i) + 1.

б) L(2ⁿ) = 1 + L(2ⁿ + 1) = L(2^n-1) + 2 = L(2⁰) + 2n = 2n + 1

в) для четного 2ⁿ < i < 2ⁿ⁺¹ алгоритм будет работать так же, как для (i - 2ⁿ)/2, и через L((i-2ⁿ)/2) шагов придет к 2ⁿ, т.е. L(i) = L((i-2ⁿ)/2) + L(2ⁿ) = L((i-2ⁿ)/2) + 2n + 1. Эти варианты покрывают все случаи и позволяют рекурсивно вычислить длину последовательности для любого i.

Теперь ввведем обозначения:
,
т.е. s_n - сумма длин последовательностей для всех чисел двоичной длины ровно n, а S_n - для чисел длины n или менее. Искомое среднее арифметическое будет S(n)/2ⁿ.

Найдём рекурсивное выражение для s_n и S_n. В s_n+1 входит 2ⁿ слагаемых, по 2^n-1 четных и нечетных. Согласно рекурсивным формулам выше, сумма всех нечетных слагаемых s_n+1 будет равна

s_n + 2^n-1,

а четных -

S_n-1 + 2^n-1(2n + 1).

Таким образом.

s_n+1 = s_n + 2^n-1 + S_n-1 + 2^n-1(2n + 1) = S_n + 2ⁿ(n+1),

или

S_n+1 = 2S_n + 2ⁿ(n+1).

Дальше дело техники, S_n = 2ⁿ n (n+1) / 4, а искомое среднеарифметическое - n(n+1)/4.

EDIT: Сорри за многократные исправления, ЖЖ поломали функцию превью для комментария.

Edited at 2019-07-22 15:15 (UTC)

Немножко текст по-дэбильному написан. (И выкладывать PDF с растровыми шрифтами в кривой кодировке должно быть стыдно в 2019 году.)

> если в ряду ровно k > 0 монет лежат буквой H кверху, то...

Имеется в виду «обозначим через k число монет, лежащих буквой H кверху. Если k > 0, то...»?

> Банк города Бат выпускает монеты с буквой H на одной стороне и буквой T на другой стороне.

С помощью ложного утверждения можно обосновать всё что угодно.

Если С — конфигурация из n монет с конечным L(C), то L(C+T)=L(C) (добавление справа T ничего не меняет), L(H+C) = L(C)+1 (первые L(C) преобразований такие же, как для C, но сдвинутые вправо на 1 позицию, в результате получается HT...T, которая приводится к TT...T за один шаг), и L(T+C+H) = L(C) + 2n + 3 (преобразования также соответствуют преобразованиям С, сдвинутым на одну позицию вправо, вплоть до прихода к последовательности TT...ТН, которая за n+1 шаг будет приведена к НН..НН и затем за n+2 шага к ТТ..ТТ).
Любую комбинацию длины n+2 можно получить из комбинаций длины n и n+1 добавлением либо T справа, либо H слева, либо T слева и H справа, поэтому по индукции для любой комбинации любой длины число операций будет конечным (база индукции: для всех комбинаций длины 1 и 2 число операций конечно, L(T) = 0, L(H) = 1, L(TT) = 0, L(TH) = 3, L(HT) = 1, L(HH) = 2).

б) Обозначим S(n) сумму L(C) для всех комбинаций С длины n, и N(n) — сумму L(C) для комбинаций C длины n, заканчивающихся на H. S(1) = 1, S(2) = 6. Поскольку L(C+T)=L(C), то N(n+1) = S(n+1) - S(n). Рассматривая отдельно комбинации, кончающиеся на T, комбинации, начинающиеся и кончающиеся на H, и комбинации, начинающиеся на H и кончающиеся на T, получим
S(n+1) = S(n) + [ N(n) + 2^(n-1) ] + [ S(n-1) + (2n+1)*2^(n-1) ] =
= S(n) + S(n) - S(n-1) + 2^(n-1) + S(n-1) + (2n+1)*2^(n-1) =
= 2S(n) + (n+1)2^n.
Нетрудно показать, что S(n) = n(n+1)2^(n-2).


Edited at 2019-07-22 11:40 (UTC)

получается, каждому количеству шагов соответствует единственное уникальное состояние )

Нет. ННН и ТНТ сходятся за 3 шага.