У процесі наукової роботи у мене накопичилося кілька цікавих результатів, які, з моєї точки зору, слабенькі для публікації в науковому виданні, проте самі по собі представляють інтерес, наприклад в області спортивного програмування. Один з таких результатів, який я сформулюю нижче, в деякій варіації може бути запропонований претенденту на співбесіді у велику IT-компанію.
Отже, почну здалеку. Я вивчав стаціонарні локалізовані структури в одномірному рівнянні Гросса-Пітаєвського, [приклад роботи]. Такі структури, при деяких достатніх умовах на параметри завдання, можна кодувати нескінченними в обидва боки символічними послідовностями, які ми називаємо кодами. Тобто, безперервні рішення диференційного рівняння класифікуються дискретними кодами. Алфавіт кодування, як правило, кінцевий і складається з деякого непарного числа символів, наприклад з символів, де - натуральне число. В алфавіті є нульовий символ, а всі інші символи поділяються на пари, пов'язані деякою симетрією. Для простоти ми будемо позначати алфавіт кодування, де символи і симетричні один одному. Число ми будемо називати потужністю алфавіту.
Оскільки досліджувані нами структури локалізовані за простором, їх коди починаються і закінчуються нескінченним числом нульових символів, тобто мають вигляд
Центральна частина коду, або його носій, складається з символів, причому крайні символи носія, і, не є нульовими символами. Число ми будемо називати довжиною коду. Тепер, для кожного коду ми можемо записати три симетричних коди,
де і - дві симетрії кодів, які нас цікавлять. Завдання ставиться наступним чином: знайти число всіх кодів довжини, складених з алфавіту потужності з точністю до двох симетрій і. Тобто, якщо два довільних коди пов'язані симетріями, або, то ми вважаємо такі коди однаковими. В умовах цейтноту, на співбесіді, досить швидко можна відповісти, що число всіх кодів без урахування симетрій дорівнює. Далі, з моєї точки зору, завдання слід вирішувати з олівцем в руках. Відразу скажу, що моє рішення може бути не оптимальним (у сенсі кількості і простоти математичних операцій). Користувач mihaild запропонував дуже елегантне рішення такого завдання через групу інваріантних перестановок і лемму Бернсайда.
Рішення
Позначимо багато всіх кодів. Розіб'ємо на три підмножини
У підмножині коди мають наступну структуру
У підмножині коди мають наступну структуру
Відповідно, за визначенням, у підмножинах і коди розбиваються на пари, а в підмножині - на четвірки, тобто
де - число різних кодів у підмножині, - потужність. Розгляньмо випадок непарного. Для підмножин, і запишемо
Для початкової безлічі отримаємо оцінку
Розгляньмо випадок чіткого. Для підмножин, і запишемо
Для початкової безлічі отримаємо оцінку
Відповідь
У підсумку ви можете записати відповіддю наступну систему рівнянь (замініть позначення на, оскільки залежить від змінних та)
У висновку зазначу, що відповідь вийшла трохи складнішою, ніж могло здатися при першому знайомстві із завданням. Подібне завдання навряд чи годиться для бліц-опитування, але і не є надто складним, щоб в якій-небудь варіації не бути запропонованою на співбесіді. Для перевірки отриманої формули наведемо такі значення: , , , . Відповідно, наведемо таблицю різних кодів, що виникає в цьому випадку. Так як, то ми випишемо коди, складені зі спрощеного алфавіту.
