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

В процессе научной работы у меня накопилось несколько интересных результатов, которые, с моей точки зрения, слабоваты для публикации в научном издании, однако сами по себе представляют интерес, например в области спортивного программирования. Один из таких результатов, который я сформулирую ниже, в некоторой вариации может быть предложен соискателю на собеседовании в крупную 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}

  • +22
  • 10,2k
  • 7
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 7

    +3
    Такие задачи легко решаются через лемму Бернсайда.
    Всего объектов (N — 1)^2 * N^{M — 2}. Группа инвариантных перестановок состоит их 4 элементов, неподвижных точек (для четного M):
    -у id (тождественной перестановки) (N — 1)^2 * N^{M — 2}
    -у T_1 (N — 1) / 2 * N^{M / 2 — 1}
    -у T_2 нету
    -у T_1 T_2 — (N — 1) / 2 * N^{M / 2 — 1}
    Делим сумму числа неподвижных точек на 4, получаем ответ (вроде бы совпадающий с вашим).
      0
      Да, вы правы. Только у T_1 (соответственно, у T_1T_2) неподвижных точек (N — 1) * N^{M/2 — 1}. Складывая все вместе и деля на 4 мы получаем ответ для четного M.
      +3
      >> в некоторой вариации может быть предложен соискателю на собеседовании в крупную IT-компанию.
      Интересно на какую позицию?
      • НЛО прилетело и опубликовало эту надпись здесь
          –2
          Ну что же вы прям так толсто троллите? Задача сформулирована в дискретном виде и вполне может быть дана, например, на собеседовании в Google, если вы попадете на on-site интервью к математику.
            0
            Просто в последнее время наметилась неприятная тенденция, когда на собеседовании от тебя требут примерно то что вы описали, а в итоге ты приходишь и правишь ресайз картинки в админке. Зачем?
              0
              Если вы опытный специалист в любой области, в частности в разработке ПО, то такие вопросы, скорее всего, вам на собеседовании задавать не будут. В этом случае достаточно будет обсудить ваш опыт работы и портфолио. С другой стороны, если вы начинающий специалист и у вас нет опыта работы и портфолио, как в таком случае работодателю выбрать вас? Тут появляются такого рода задачи, проще и сложнее. Работодатель пытается максимизировать потенциал молодого работника, который на момент собеседования ничего толком не знает, но который готов в этом направлении развиваться. Как справиться с таким отбором на junior-уровне? Не знаю. Хороший вариант – уметь такие задачи решать или хотя бы проявлять интерес к их решению. Можно пойти практическим путем – поскорее стать опытным специалистом, сделать хорошее портфолио.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое