Игра в города

[General]

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

Пусть у игроков обдинаковый запас слов. Пусть в алфавите k букв. Имеется квадратная матрица А размера kxk, каждый элемент которой $a_{ij}$ показывает, сколько осталось неназванных слов, которые начинаются на i-ю букву алфавита и оканчиваются на j-ю букву. Позиция в игре Представляет собой пару (А, k), где А - текущая матрица неназванных слов, а k - номер буквы, на которую нужно назвать слово. Своим ходом игрок уменьшает на 1 один из элементов k-й строки матрицы А (допустим, a_{km}:=a_{km-1}) и создаёт позицию (А', m), где А' - текущая матрица неназванных слов (предыдущая матрица с уменьшенным на 1 элементом a_{km}), а m - номер в алфавите последней буквы слова, названного игроком, и, соответственно, первая буква слова, которое нужно назвать следующему игроку.

Позиция (А, k) будет проигрышной, если в матрице А все элементы k-й строки будут равны 0.

Кто-то встречал такое обощение, может, велосипед изобретаю?

[maxal]

Я бы скорее сформулировал игру в форме блужданий по графу. Направленный граф здесь определим так: вершинами являются слова из запаса, и два слова соединены дугой, если второе слово начинается на ту же букву, на которую оканчивается первое.
Тогда ход в игре будет соответствовать переходу по дуге из текущей вершины в другую, ранее не посещенную. Таким образом, партия будет соответствовать несамоперескающемуся пути в графе, который нельзя продолжить (то есть из последней вершины все дуги ведут в ранее посещенные вершины - что соответствует проигрышной позиции).

[General]

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