Преобразования слов

[Roman Kotyk]

Это частный случай задачи, которая была решена в общем виде относительно недавно.

Игрок выписывает слово из 10 букв, которые могут принимать значения $a$, $b$, $c$. Один ход игры состоит в том, что можно заменить две рядом стоящие одинаковые буквы на две оставшиеся, идущие по алфавиту. То есть разрешённые преобразования имеют один из трёх видов: $aa\to bc$, $bb\to ac$, $cc\to ab$. За каждый сделанный ход игрок получает 1 балл. Какое максимальное количество баллов он может набрать?

Например, для слова из четырёх букв возможна такая игра: $abb\to aac\to bcc\to bab$ (не утверждается, что она даёт наилучший результат).

[kknop]

А общий случай какой?

[Roman Kotyk]

Первую строчку можно не читать. Интересует решение этой, конкретной задачи.

[Sonic86]

Ну давайте я напишу для затравки.
Я нашел цепочку квадратичной длины:
(в скобках справа пишется текущее число сделанных ходов)
$b(bc)^n =$
$bbc(bc)^{n-1}\ \ (0)\to$
$acc(bc)^{n-1}\ \ (1)\to$
$(aa)^1b(bc)^{n-1}\ \ (2)\to$
$(aa)^2b(bc)^{n-2}\ \ (4)\to...$
$(aa)^nb\ \ (2n)\to$
$(bc)^nb\ \ (3n)$
Т.е. $b(bc)^n$ преобразуется в $(bc)^nb$ за $3n$ ходов.
Далее, для $k\geqslant n$
$b^k(bc)^n\ \ (0)\to $
$b^{k-1}(bc)^nb^1\ \ (3n) \to...$
$(bc)^nb^k\ \ (3nk)$
И наконец
$(bc)^nb^k\to (bc)^n(ac)^{[k/2]}b^{k\bmod 2}$ за $(3kn+\left[\frac{k}{2}\right])$ ходов.
Длина слова $2n+k$. Для $n=3,k=4$ длина слова $=10$, а число ходов получается равным $3\cdot 3\cdot 4+2=38$ ходов.
(проверьте, могу наврать)
Я, конечно, не утверждаю, что это максимум. Однако максимум теперь $\geqslant 38$.

upd: можно еще сначала добавить ходы типа $aa\to bc$ для построения $(bc)^n$. Получим еще 1 ход: максимум $\geqslant 39$.

[Cash]

Sonic86 в сообщении #1061313 писал(а):

можно еще сначала добавить ходы типа $aa\to bc$ для построения $(bc)^n$. Получим еще 1 ход: максимум $\geqslant 39$

Почему еще 1, если их $n$?

[Sonic86]

Cash в сообщении #1061318 писал(а):

Почему еще 1, если их $n$?

Да, я поторопился: проверять, проверять и проверять. Итого $\geqslant 41$.

А вот насчет теоретического обоснования максимума все как-то глуховато.

(варианты)

1. Комбинаторно оценивать максимум мы помрем.
2. Дополнить "как этот объект-то называется?" до полугруппы можно, но максимум тогда увеличится.

Можно наваять прогу и запустить... Но зачем?
Или настоящий максимум сильно больше?

[mihiv]

Вариант $c^2b^8$ дает, если не ошибаюсь 66 ходов. Проверяется так: $ccb\to abb\to aac\to bcc$, т.е. $b$ переставляется с $cc$ за три хода. Таким способом перегоняем $cc$ слева направо за $3\cdot 8=24$ хода. Затем перегоняем каждое из двух $c$ справа налево. При этом используем следующий способ: $bbc\to acc\to aab\to bcb$. Т.е. $c$ переставляется с $b$ при движении справа налево за три хода. Так что первое $c$ перейдет направо за $3\cdot 7=21$ ход. Второе $c$ перейдет направо за $3\cdot 6=18$ ходов. В результате получим слово $(bc)^2b^6$, заменим в нем $bb\to ac$ (еще три хода ). Получим $(bc)^2(ac)^3$. Всего $24+21+18+3=66$ ходов.
В этой задаче имеет смысл каждому слову сопоставить вершину ориентированного графа. В этом графе будут вершины только с исходящими ребрами (тип 1), только с входящими ребрами(тип 2) и смешанные. Тогда задача сводится к поиску максимального пути от вершины типа 1 к вершине типа 2.( тип 1 означает, что данное слово не может быть получено ни из какого другого слова, например: $a^{10}$)

[12d3]

Варианты $b^8a^2$ и $c^2b^8$ дают по 105 ходов, это максимум.

(Оффтоп)

Для второго варианта преобразования:
ccbbbbbbbb
abbbbbbbbb
aacbbbbbbb
bccbbbbbbb
babbbbbbbb
baacbbbbbb
bbccbbbbbb
bbabbbbbbb
bbaacbbbbb
bbbccbbbbb
bbbabbbbbb
bbbaacbbbb
bbbbccbbbb
bbbbabbbbb
bbbbaacbbb
bbbbbccbbb
bbbbbabbbb
bbbbbaacbb
bbbbbbccbb
bbbbbbabbb
bbbbbbaacb
bbbbbbbccb
bbbbbbbabb
bbbbbbbaac
bbbbbbbbcc
bbbbbbaccc
bbbbbbaabc
bbbbbbbcbc
bbbbbaccbc
bbbbbaabbc
bbbbbbcbbc
bbbbbbcacc
bbbbbbcaab
bbbbbbcbcb
bbbbaccbcb
bbbbaabbcb
bbbbbcbbcb
bbbbbcaccb
bbbbbcaabb
bbbbbcbcbb
bbbaccbcbb
bbbaabbcbb
bbbbcbbcbb
bbbbcaccbb
bbbbcaabbb
bbbbcbcbbb
bbaccbcbbb
bbaabbcbbb
bbbcbbcbbb
bbbcaccbbb
bbbcaabbbb
bbbcbcbbbb
baccbcbbbb
baabbcbbbb
bbcbbcbbbb
bbcaccbbbb
bbcaabbbbb
bbcbcbbbbb
accbcbbbbb
aabbcbbbbb
bcbbcbbbbb
bcaccbbbbb
bcaabbbbbb
bcaaacbbbb
bcabccbbbb
bcababbbbb
bcabaacbbb
bcabbccbbb
bcabbabbbb
bcabbaacbb
bcabbbccbb
bcabbbabbb
bcabbbaacb
bcabbbbccb
bcabbbbabb
bcabbbbaac
bcabbbbbcc
bcabbbbbab
bcaacbbbab
bcbccbbbab
bcbabbbbab
bcbaacbbab
bcbbccbbab
bcbbabbbab
bcbbaacbab
bcbbbccbab
bcbbbabbab
bcbbbaacab
bcbbbbccab
bcbbacccab
bcbbaabcab
bcbbbcbcab
bcbaccbcab
bcbaabbcab
bcbbcbbcab
bcbbcaccab
bcbbcaabab
bcbbcbcbab
bcaccbcbab
bcaabbcbab
bcbcbbcbab
bcbcaccbab
bcbcaabbab
bcbcaaacab
bcbcabccab
bcbcababab

[mihiv]

Интересно, не могут ли при каких-то $n$ возникать циклы, или это исключено?

[worm2]

mihiv писал(а):

Интересно, не могут ли при каких-то $n$ возникать циклы, или это исключено?

При $n\leqslant 15$ исключено. Это показывает компьютерный перебор (у меня получились те же результаты, что и у 12d3), но человеческими рассуждениями мне обосновать не удаётся.

[Sonic86]

http://math.hashcode.ru/questions/73954 ... 0%BE%D0%B2
Эта же задача обсуждается здесь.
Там выписано простое доказательство отсутствия циклов