Comments: |
Часть А вроде бы совсем проста. Докажем по индукции.
База. Если есть одна буква и это Т, то всё ок. Если это Н, то будет Н-->Т и в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 букв тоже станут Т.
Если не наврал, то сумма L(C) по всем C с кратностью H равной k равна: n*(n-k+1)*binom(n-1,k-1).
Соответственно, среднее L(C) по всем C равно n*(n+1)/4. Edited at 2019-07-21 19:04 (UTC)
Пусть 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-2 шагов любое начальное состояние превратится в 0. 2. Сначала выведем рекурсивные формулы. а) если к любому числу дописать младшим разрядом ещё одну единичку, то алгоритм повторится в точности так же до нуля, оставив только дописанную единичку, а затем следующим шагом эта единица перейдёт в 0, т.е. L(2*i+1) = L(i) + 1. б) L(2 n) = 1 + L(2 n + 1) = L(2 n-1) + 2 = L(2 0) + 2n = 2n + 1 в) для четного 2 n < i < 2 n+1 алгоритм будет работать так же, как для (i - 2 n)/2, и через L((i-2 n)/2) шагов придет к 2 n, т.е. L(i) = L((i-2 n)/2) + L(2 n) = L((i-2 n)/2) + 2n + 1. Эти варианты покрывают все случаи и позволяют рекурсивно вычислить длину последовательности для любого i. Теперь ввведем обозначения: ,&space;\\&space;S_n=\sum_{i=1}^{2^n-1}L(i)=\sum_{i=1}^ns_i=S_{n-1}+s_n) , т.е. s n - сумма длин последовательностей для всех чисел двоичной длины ровно n, а S n - для чисел длины n или менее. Искомое среднее арифметическое будет S(n)/2 n. Найдём рекурсивное выражение для s n и S n. В s n+1 входит 2 n слагаемых, по 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(n+1), или S n+1 = 2S n + 2 n(n+1). Дальше дело техники, S n = 2 n 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 шага. | |