gamekoff 26 дек 2016 в 14:17

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

2 мин

10K

Занимательные задачкиМатематика*Спортивное программирование*

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

Итак, начну издалека. Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы]. Такие структуры, при некоторых достаточных условиях на параметры задачи, можно кодировать бесконечными в обе стороны символическими последовательностями, которые мы называем кодами. То есть, непрерывные решения дифференциального уравнения классифицируются дискретными кодами. Алфавит кодировки, как правило, конечен и состоит из некоторого нечетного числа символов, например из $N=2L+1$ символов, где $L$ – натуральное число. В алфавите есть нулевой символ , а все остальные символы делятся на пары, связанные некоторой симметрией. Для простоты мы будем обозначать алфавит кодировки $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}$ . Дальше, с моей точки зрения, задачу следует решать с карандашом в руках. Сразу скажу, что мое решение может быть не оптимальным (в смысле количества и простоты математических операций). Пользователь mihaild предложил очень элегантное решение такой задачи через группу инвариантных перестановок и лемму Бёрнсайда.

Решение

Обозначим множество всех кодов $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}$

Теги:

Хабы:

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

Публикации

Истории

Ближайшие события