Игра с перестановками

[arseniiv]

Придумать-то я её придумал, а как играть, до сих пор не понял.

Правила следующие. Фиксируются какие-то положительные целые $n, k$. Один игрок (назовём его компьютером) выбирает $c_1,\ldots,c_k\in S_n$ и выбирает какой-то элемент из $\langle c_1,\ldots,c_k\rangle$ как начальное состояние. Каждое состояние компьютер сообщает другому игроку, но не просто так, а показывая только, какие элементы текущая перестановка оставляет на своих местах, а какие — нет (например, выводит строку из символов двух типов). Второй игрок что-то там соображает и выбирает число $i\in 1..k$, после чего компьютер умножает текущую перестановку на $c_i$ и показывает новое состояние игроку в своей манере снова. Всё повторяется, пока игрок не приведёт состояние к единичной перестановке (и компьютер покажет ему, что теперь все элементы остаются на месте).

Как лучше выбирать $c_1,\ldots,c_k$ и начальное состояние компьютеру, чтобы отсрочить конец, и как ходить второму игроку, чтобы его приблизить?

[Geen]

Ну, для $k=1$ решение очевидно. И уже не очень приятное.

[iancaple]

arseniiv в сообщении #1060987 писал(а):

Второй игрок что-то там соображает и выбирает число $i\in 1..k$, после чего компьютер умножает текущую перестановку на $c_i$

А знает ли он при этом, какой номер имеет начальное состояние? Если знает, то некоторое число раз подряд (НОК порядков независимых циклов, составляющих ее) применить только этот номер. А связываться с другими номерами рискованно, может, они все оставляют на месте некоторый элемент.

[NSKuber]

iancaple в сообщении #1061012 писал(а):

А знает ли он при этом, какой номер имеет начальное состояние?

Начальное состояние принадлежит подгруппе, порождённой выбранными $c_1,\ldots,c_k$, оно не обязательно с кем-то из них совпадает.
Ещё вопрос, второй игрок знает эти самые $c_i$, или просто называет номера, не имея понятия (изначально), как каждая из них действует?

[iancaple]

NSKuber в сообщении #1061016 писал(а):

iancaple в сообщении #1061012 писал(а):

А знает ли он при этом, какой номер имеет начальное состояние?

Начальное состояние принадлежит подгруппе, порождённой выбранными $c_1,\ldots,c_k$, оно не обязательно с кем-то из них совпадает.

Спасибо, вопрос снимается. Угловые скобки были очень похожи на круглые

[arseniiv]

(Оффтоп)

Я в одном (растровом, правда) шрифте путал круглые с фигурными.

NSKuber в сообщении #1061016 писал(а):

Ещё вопрос, второй игрок знает эти самые $c_i$, или просто называет номера, не имея понятия (изначально), как каждая из них действует?

Не имеет.

Как вы верно заметили, начальная перестановка может вполне не совпасть ни с одной из $c_i$, хотя может и совпасть.

Я даже пока без понятия, как игрок мог бы просто перебрать всю $\langle c_i\rangle$, это было бы первым приближением к его стратегии. Впрочем, особо и не думал, только сегодня вспомнил о задаче.

[Geen]

arseniiv в сообщении #1061046 писал(а):

Как вы верно заметили, начальная перестановка может вполне не совпасть ни с одной из $c_i$

Это уже какая-то совсем мучительная игра получается...

arseniiv в сообщении #1061046 писал(а):

Я даже пока без понятия, как игрок мог бы просто перебрать всю $\langle c_i\rangle$

Кажется, как $n^k$. И похоже, принципиально в общем не улучшить.

arseniiv в сообщении #1060987 писал(а):

Каждое состояние компьютер сообщает другому игроку, но не просто так, а показывая только, какие элементы текущая перестановка оставляет на своих местах

Вообще не вижу как это может помочь - кроме отдельных экзотических случаев это будет строка всех нулей.

[AV_77]

Здесь, возможно, стоит посмотреть в сторону длины системы образующих (минимальное число $t$, для которого любую подстановку из $\langle c_i, i = 1, \ldots, k \rangle$ можно представить в виде произведения не более чем $t$ подстановок $c_i$. Очевидно, что начальное состояние компьютеру надо выбирать так, чтобы эта подстановка имела максимальную длину в заданной системе. Однако в общем случае задача определения длины подстановки в заданной системе образующих, если не ошибаюсь, NP-полная.