Об одной комбинаторной задаче

В процессе своей научной работы у меня накопилось несколько интересных результатов, которые, с моей точки зрения, слабоваты для публикации в научном издании, однако сами по себе представляют интерес, например в области спортивного программирования. Один из таких результатов, который я сформулирую ниже, в некоторой вариации может быть предложен соискателю на собеседовании в крупную IT-компанию.

Итак, начну издалека. Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы]. Такие структуры, при некоторых достаточных условиях на параметры задачи, можно кодировать бесконечными в обе стороны символическими последовательностями, которые мы называем кодами. То есть, непрерывные решения дифференциального уравнения классифицируются дискретными кодами. Алфавит кодировки, как правило, конечен и состоит из некоторого нечетного числа символов, например из символов, где – натуральное число. В алфавите есть нулевой символ , а все остальные символы делятся на пары, связанные некоторой симметрией. Для простоты мы будем обозначать алфавит кодировки , где символы и симметричны друг другу. Число мы будем называть мощностью алфавита .

Так как исследуемые нами структуры локализованы по пространству, то их коды начинаются и заканчиваются бесконечным числом нулевых символов, то есть имеют вид

Центральная часть кода , или его носитель, состоит из символов, причем крайние символы носителя, и , не являются нулевыми символами. Число мы будем называть длиной кода . Теперь, для каждого кода мы можем записать три симметричных кода,

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

Решение

Обозначим множество всех кодов . Разобьем на три непересекающихся подмножества

В подмножестве коды имеют следующую структуру

В подмножестве коды имеют следующую структуру

Соответственно, по определению, в подмножествах и коды разбиваются на пары , а в подмножестве – на четверки , то есть

где – число различных кодов в подмножестве , – мощность . Рассмотрим случай нечетного . Для подмножеств , и запишем

Для исходного множества получим оценку

Рассмотрим случай четного . Для подмножеств , и запишем

Для исходного множества получим оценку

Ответ

В итоге, в качестве ответа можно записать следующую систему уравнений (заменим обозначение на , так как зависит от переменных и )

В заключении отмечу, что ответ получился немного сложнее, чем могло показаться при первом знакомстве с задачей. Подобная задача вряд ли не годится для блиц-опроса, но и не является чересчур сложной, чтобы в какой-нибудь вариации не быть предложенной на собеседовании. Для проверки полученной формулы приведем следующие значения: , , , . Соответственно, приведем таблицу различных кодов, возникающий в этом случае. Так как , то мы выпишем коды, составленные из упрощенного алфавита .

Автор: gamekoff

Источник