Про одну комбінаторної задачі

В процесі своєї наукової роботи у мене накопичилося кілька цікавих результатів, які, з моєї точки зору, заслабкі для публікації у науковому виданні, проте самі по собі представляють інтерес, наприклад в області спортивного програмування. Один із таких результатів, який я сформулюю нижчою, в деякій варіації може бути запропонований претенденту на співбесіді у велику 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_1s_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_1D_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_1D_2D_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_1D_2D_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залежить від змінних NM)
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 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.