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

в 11:17, , рубрики: Занимательные задачки, комбинаторика, математика, Спортивное программирование

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

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

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

{bf c}=(ldots,0,s_1,s_2,ldots,s_M,0,ldots),quad s_iin A, quad s_1neq 0,quad s_Mneq 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}_1mathcal{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}_1mathcal{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}_1mathcal{I}_2{bf c}}, \D_3={{bf c}mid {bf c}neqmathcal{I}_1{bf c},  {bf c}neqmathcal{I}_1mathcal{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}_1mathcal{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{2sqrt{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{2sqrt{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$   \  hlineg{$(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)$}\            hlineend{tabular} end{small} end{center}

Автор: gamekoff

Источник

Поделиться

* - обязательные к заполнению поля