2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Игра с перестановками
Сообщение10.10.2015, 11:48 
Придумать-то я её придумал, а как играть, до сих пор не понял.

Правила следующие. Фиксируются какие-то положительные целые $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$ и начальное состояние компьютеру, чтобы отсрочить конец, и как ходить второму игроку, чтобы его приблизить?

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 13:12 
Аватара пользователя
Ну, для $k=1$ решение очевидно. И уже не очень приятное. :-)

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 13:19 
Аватара пользователя
arseniiv в сообщении #1060987 писал(а):
Второй игрок что-то там соображает и выбирает число $i\in 1..k$, после чего компьютер умножает текущую перестановку на $c_i$
А знает ли он при этом, какой номер имеет начальное состояние? Если знает, то некоторое число раз подряд (НОК порядков независимых циклов, составляющих ее) применить только этот номер. А связываться с другими номерами рискованно, может, они все оставляют на месте некоторый элемент.

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 13:31 
iancaple в сообщении #1061012 писал(а):
А знает ли он при этом, какой номер имеет начальное состояние?

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

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 13:44 
Аватара пользователя
NSKuber в сообщении #1061016 писал(а):
iancaple в сообщении #1061012 писал(а):
А знает ли он при этом, какой номер имеет начальное состояние?

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

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 14:59 

(Оффтоп)

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

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

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

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

 
 
 
 Re: Игра с перестановками
Сообщение10.10.2015, 15:21 
Аватара пользователя
arseniiv в сообщении #1061046 писал(а):
Как вы верно заметили, начальная перестановка может вполне не совпасть ни с одной из $c_i$

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

arseniiv в сообщении #1061046 писал(а):
Я даже пока без понятия, как игрок мог бы просто перебрать всю $\langle c_i\rangle$

Кажется, как $n^k$. И похоже, принципиально в общем не улучшить.
arseniiv в сообщении #1060987 писал(а):
Каждое состояние компьютер сообщает другому игроку, но не просто так, а показывая только, какие элементы текущая перестановка оставляет на своих местах

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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group