[Из песочницы] Об одной комбинаторной задаче

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


Итак, начну издалека. Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы]. Такие структуры, при некоторых достаточных условиях на параметры задачи, можно кодировать бесконечными в обе стороны символическими последовательностями, которые мы называем кодами. То есть, непрерывные решения дифференциального уравнения классифицируются дискретными кодами. Алфавит кодировки, как правило, конечен и состоит из некоторого нечетного числа символов, например из N=2L+1 символов, где L — натуральное число. В алфавите есть нулевой символ 0, а все остальные символы делятся на пары, связанные некоторой симметрией. Для простоты мы будем обозначать алфавит кодировки A=\{i\}_{i=-L}^L, где символы i и -i симметричны друг другу. Число N мы будем называть мощностью алфавита A.


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


{\bf c}=(\ldots,0,s_1,s_2,\ldots,s_M,0,\ldots),\quad s_i\in A, \quad s_1\neq 0,\quad s_M\neq 0.

Центральная часть кода {\bf c}, или его носитель, состоит из M символов, причем крайние символы носителя, s_1 и s_M, не являются нулевыми символами. Число M мы будем называть длиной кода {\bf c}. Теперь, для каждого кода {\bf c} мы можем записать три симметричных кода,


\mathcal{I}_1{\bf c}=(\ldots,0,s_M,s_{M-1},\ldots,s_1,0,\ldots), \\ \mathcal{I}_2{\bf c}=(\ldots,0,-s_1,-s_2,\ldots,-s_M,0,\ldots), \\ \mathcal{I}_1\mathcal{I}_2{\bf c}=(\ldots,0,-s_M,-s_{M-1},\ldots,-s_1,0,\ldots),

где \mathcal{I}_1 и \mathcal{I}_2 — две интересующие нас симметрии кодов. Задача ставится следующим образом: найти число всех кодов длины M, составленных из алфавита мощности N с точностью до двух симметрий \mathcal{I}_1 и \mathcal{I}_2. То есть, если два произвольных кода связаны симметриями \mathcal{I}_1, \mathcal{I}_2 или \mathcal{I}_1\mathcal{I}_2, то мы считаем такие коды одинаковыми. В условиях цейтнота, на собеседовании, довольно быстро можно ответить, что число всех кодов без учета симметрий равно (N-1)^2N^{M-2}. Дальше, с моей точки зрения, задачу следует решать с карандашом в руках. Сразу скажу, что мое решение может быть не оптимальным (в смысле количества и простоты математических операций).


Решение

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


D_1=\{{\bf c}\mid {\bf c}=\mathcal{I}_1{\bf c}\}, \\ D_2=\{{\bf c}\mid {\bf c}=\mathcal{I}_1\mathcal{I}_2{\bf c}\}, \\ D_3=\{{\bf c}\mid {\bf c}\neq\mathcal{I}_1{\bf c}, \ {\bf c}\neq\mathcal{I}_1\mathcal{I}_2{\bf c}\}.

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


{\bf c}=(\ldots,0,s_1,s_2,\ldots,s_{\frac{M-1}{2}},s_{\frac{M+1}{2}},s_{\frac{M-1}{2}},\ldots,s_2,s_1,0,\ldots), \quad M -\mbox{нечетно}, \\ {\bf c}=(\ldots,0,s_1,s_2,\ldots,s_{\frac{M}{2}},s_{\frac{M}{2}},\ldots,s_2,s_1,0,\ldots), \quad M -\mbox{четно}.

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


{\bf c}=(\ldots,0,s_1,s_2,\ldots,s_{\frac{M-1}{2}},s_{\frac{M+1}{2}},-s_{\frac{M-1}{2}},\ldots,-s_2,-s_1,0,\ldots), \quad M -\mbox{нечетно}, \\ {\bf c}=(\ldots,0,s_1,s_2,\ldots,s_{\frac{M}{2}},-s_{\frac{M}{2}},\ldots,-s_2,-s_1,0,\ldots), \quad M -\mbox{четно}.

Соответственно, по определению, в подмножествах D_1 и D_2 коды разбиваются на пары ({\bf c},\mathcal{I}_2{\bf c}), а в подмножестве D_3 — на четверки ({\bf c}, \mathcal{I}_1{\bf c}, \mathcal{I}_2{\bf c}, \mathcal{I}_1\mathcal{I}_2{\bf c}), то есть


Q(D_1)=\frac{|D_1|}{2},\quad Q(D_2)=\frac{|D_2|}{2},\quad Q(D_3)=\frac{|D_3|}{4}=\frac{|D_0|-|D_1|-|D_2|}{4},

где Q(D) — число различных кодов в подмножестве D, |D| — мощность D. Рассмотрим случай нечетного M. Для подмножеств D_1, D_2 и D_3 запишем


Q(D_1)=\frac{N-1}{2}N^\frac{M-1}{2}, \\ Q(D_2)=\frac{N-1}{2}N^\frac{M-3}{2}, \\ Q(D_3)=\frac{(N-1)^2}{4}N^{M-2}-\frac{N-1}{4}N^\frac{M-1}{2}-\frac{N-1}{4}N^\frac{M-3}{2}.

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


Q(D_0)=\sum_{i=1}^3{Q(D_i)}=\frac{N-1}{4}\left[N^{M-1}\left(1-\frac{1}{N}\right)+\sqrt{N^{M-1}}\left(1+\frac{1}{N}\right)\right].

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


Q(D_1)=\frac{N-1}{2}N^{\frac{M}{2}-1}, \\  Q(D_2)=\frac{N-1}{2}N^{\frac{M}{2}-1}, \\ Q(D_3)=\frac{(N-1)^2}{4}N^{M-2}-\frac{N-1}{2}N^{\frac{M}{2}-1}.

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


Q(D_0)=\sum_{i=1}^3{Q(D_i)}=\frac{N-1}{4}\left[N^{M-1}\left(1-\frac{1}{N}\right)+\frac{2\sqrt{N^M}}{N}\right].

Ответ

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


Q(N,M)=\left\{ \begin{array}{l} \frac{N-1}{4}\left[N^{M-1}\left(1-\frac{1}{N}\right)+\sqrt{N^{M-1}}\left(1+\frac{1}{N}\right)\right], \quad M -\mbox{нечетно}, \\ \frac{N-1}{4}\left[N^{M-1}\left(1-\frac{1}{N}\right)+\frac{2\sqrt{N^M}}{N}\right], \quad M -\mbox{четно}. \end{array} \right.

В заключении отмечу, что ответ получился немного сложнее, чем могло показаться при первом знакомстве с задачей. Подобная задача вряд ли годится для блиц-опроса, но и не является чересчур сложной, чтобы в какой-нибудь вариации не быть предложенной на собеседовании. Для проверки полученной формулы приведем следующие значения: Q(3,1)=1, Q(3,2)=2, Q(3,3)=5, Q(3,4)=12. Соответственно, приведем таблицу различных кодов, возникающий в этом случае. Так как N=3, то мы выпишем коды, составленные из упрощенного алфавита A=\{+,0,-\}.


\begin{center}  \begin{small}  \begin{tabular}{|l|l|l|l|l|} \hline $M=1$       &   $M=2$       &   $M=3$       &   $M=4$   \\   \hline \g{$(\ldots,0,+,0,\ldots)$} &   \g{$(\ldots,0,+,+,0,\ldots)$}   &   \g{$(\ldots,0,+,+,+,0,\ldots)$} &   \g{$(\ldots,0,+,+,+,+,0,\ldots)$}\\                         &   \y{$(\ldots,0,+,-,0,\ldots)$}   &   \y{$(\ldots,0,+,+,-,0,\ldots)$} &   \y{$(\ldots,0,+,+,-,+,0,\ldots)$}\\                         &               &   \y{$(\ldots,0,+,-,+,0,\ldots)$} &   \y{$(\ldots,0,+,-,-,+,0,\ldots)$}\\                         &               &   \y{$(\ldots,0,+,0,+,0,\ldots)$} &   \y{$(\ldots,0,+,+,0,+,0,\ldots)$}\\                         &               &   \g{$(\ldots,0,+,0,-,0,\ldots)$} &   \y{$(\ldots,0,+,-,0,+,0,\ldots)$}\\                         &               &               &   \g{$(\ldots,0,+,0,0,+,0,\ldots)$}\\                         &               &               &   \y{$(\ldots,0,+,+,+,-,0,\ldots)$}\\                         &               &               &   \y{$(\ldots,0,+,+,-,-,0,\ldots)$}\\                         &               &               &   \y{$(\ldots,0,+,-,+,-,0,\ldots)$}\\                         &               &               &   \g{$(\ldots,0,+,+,0,-,0,\ldots)$}\\                         &               &               &   \y{$(\ldots,0,+,-,0,-,0,\ldots)$}\\                         &               &               &   \y{$(\ldots,0,+,0,0,-,0,\ldots)$}\\             \hline \end{tabular}  \end{small}  \end{center}

Комментарии (0)

© Habrahabr.ru