?

Log in

No account? Create an account
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

олимпиада: 2019/P5 [июл. 21, 2019|05:53 pm]
Anatoly Vorobey
[Tags|, ]

Закончилась Международная Математическая Олимпиада-2019, и я вчера с привычной опаской пошел посмотреть на ее задачи. Оказалось, что по крайней мере некоторые из них в этом году находятся в пределах досягаемости простых смертных, или так мне кажется, по крайней мере. Давайте попробуем вместе над ними подумать?

Я буду постить сюда по одной задаче в день. Если вы хотите предложить свое решение, полное или неполное, пишите в комментариях. Я заскриню комментарии на сутки, а после этого ВСЕ ОТКРОЮ, учтите, опасайтесь спойлеров. Update: РАСКРЫТО. Первым правильный ответ дал relf, и есть еще много других правильных.

Есть хардкорные форумы в интернете, посвященные знают, где наверняка всем этим задачам уже нашли решения. Я туда сам смотреть не буду, и прошу оттуда идеи/решения не постить - только ваши собственные.

Итак, пятая задача (всего их шесть, я начинаю с той, которая легче других, на мой субъективный взгляд). Очень милая, должна программистам понравиться, мне кажется. Комменты скрываются до завтра. Чтобы прочитать с увеличенным шрифтом, можно нажать на картинку. Я запощу свое решение завтра (надеюсь, что правильное), и раскрою комментарии.

СсылкаОтветить

Comments:
[User Picture]From: Евгений Смирнов
2019-07-21 04:56 pm
Часть А вроде бы совсем проста. Докажем по индукции.

База. Если есть одна буква и это Т, то всё ок. Если это Н, то будет Н-->Т и в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 букв тоже станут Т.
(Ответить) (Thread)
[User Picture]From: relf
2019-07-21 07:03 pm

Если не наврал, то сумма 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)
(Ответить) (Thread)
From: barlaam
2019-07-21 09:18 pm
Пусть 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.
(Ответить) (Thread)
[User Picture]From: avva
2019-07-22 04:11 pm
В целом все верно, но где-то мелких недочет - ответ n(n+1)/4.
(Ответить) (Parent) (Thread)
From: barlaam
2019-07-22 04:54 pm
Конечно n(n+1)/4. Это я на последнем шаге сумму 1+2+...+n неверно записал.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2019-07-21 09:40 pm
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.
(Ответить) (Thread)
[User Picture]From: urod
2019-07-21 09:57 pm
a решается легко.

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

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

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

Если крайне левая монета T, а крайне правая H, все монеты между ними эволюционируют так, как если бы крайних не было. Когда-нибудь они все превратятся в Т. После этого монеты слева направо одна за другой начнут превращаться в H. Когда все станут Н, монеты справа налево начнут превращаться в Т, пока все не станут Т.
(Ответить) (Thread)
[User Picture]From: urod
2019-07-21 10:33 pm
Для б, чую я, есть какое-то соответствие между последовательностью букв и двоичным числом, в котором прибавляем/вычитаем единицу.

Но есть другое: пусть 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

С этими формулами можно работать.
(Ответить) (Thread)
From: olegbutkovsky
2019-07-21 10:39 pm
А вот и решение части Б. Ответ: 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.
(Ответить) (Thread)
[User Picture]From: alex_levit
2019-07-21 10:58 pm
Пусть 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.
(Ответить) (Thread)
From: ichthuss
2019-07-22 12:03 am
Поскольку в процессе выполнения алгоритма никогда любая Т, находящаяся правее последней Н, не изменится, то без потери общности можем рассматривать каждую последовательность только до последней встречающейся Н, игноринуя все дальнейшие Т. В связи с этим удобно сопоставить состояние с двоичной записью некоего числа, т.е. ТТТ = 0, НТТ = 1, ННТ = 3 и т.д.

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

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

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

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

б) L(2n) = 1 + L(2n + 1) = L(2n-1) + 2 = L(20) + 2n = 2n + 1

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

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

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

sn + 2n-1,

а четных -

Sn-1 + 2n-1(2n + 1).

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

sn+1 = sn + 2n-1 + Sn-1 + 2n-1(2n + 1) = Sn + 2n(n+1),

или

Sn+1 = 2Sn + 2n(n+1).

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

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

Edited at 2019-07-22 15:15 (UTC)
(Ответить) (Thread)
[User Picture]From: nakem
2019-07-22 04:13 am
Немножко текст по-дэбильному написан. (И выкладывать PDF с растровыми шрифтами в кривой кодировке должно быть стыдно в 2019 году.)

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

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

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

С помощью ложного утверждения можно обосновать всё что угодно.
(Ответить) (Thread)
[User Picture]From: torquelimach
2019-07-22 11:35 am
Если С — конфигурация из 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)
(Ответить) (Thread)
From: rengsolo
2019-07-22 02:27 pm
получается, каждому количеству шагов соответствует единственное уникальное состояние )
(Ответить) (Thread)
[User Picture]From: alex_levit
2019-07-22 04:10 pm
Нет. ННН и ТНТ сходятся за 3 шага.
(Ответить) (Parent) (Thread)