В процессе научной работы мною накоплено несколько интересных результатов, которые, с моей точки зрения, слишком слабы для публикации в научном журнале, но представляют интерес сами по себе, например, в области спортивного программирования.
Один из таких результатов, который я сформулирую ниже, в некоторой вариации можно предложить соискателю на собеседовании в крупную ИТ-компанию.
Итак, начну издалека.
Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы] .
Такие структуры при определенных достаточных условиях на параметры задачи могут быть закодированы бесконечными символьными последовательностями в обоих направлениях, которые мы называем кодами.
То есть непрерывные решения дифференциального уравнения классифицируются дискретными кодами.
Кодирующий алфавит обычно конечен и состоит из некоторого нечетного числа символов, например
персонажи, где
- натуральное число.
В алфавите есть нулевой символ
, а все остальные символы разбиваются на пары, связанные некоторой симметрией.
Для простоты будем обозначать алфавит кодирования
, где персонажи
И
симметричны друг другу.
Число
мы назовем силу алфавита
.
Поскольку изучаемые нами структуры локализованы в пространстве, их коды начинаются и заканчиваются бесконечным числом нулевых символов, то есть имеют вид
Центральная часть кода
, или его носитель, состоит из
символы и самые внешние символы носителя,
И
, не являются нулевыми символами.
Число
мы назовем это длиной кода
.
Теперь для каждого кода
мы можем написать три симметричных кода,
Где
И
— две симметрии кодов, которые нас интересуют. Задача формулируется следующим образом: найти количество всех кодов длины
, составленный из степенного алфавита
до двух симметрий
И
.
То есть, если два произвольных кода связаны симметриями
,
или
, то считаем такие коды одинаковыми.
В условиях ограниченности времени во время собеседования вы можете быстро ответить, что количество всех кодов без учета симметрии равно
.
Дальше, с моей точки зрения, проблему следует решать с карандашом в руке.
Скажу сразу, что мое решение может быть не оптимальным (по количеству и простоте математических операций).
Пользователь Михаил предложил очень элегантное решение такой проблемы с помощью группы инвариантных перестановок и леммы Бернсайда.
Решение Обозначим множество всех кодов
.
Давайте сломаем это
на три непересекающихся подмножества
В подмножестве
коды имеют следующую структуру
В подмножестве
коды имеют следующую структуру
Соответственно, по определению, в подмножествах
И
коды разделены на пары
, и в подмножестве
- на четверых
, то есть
Где
– количество различных кодов в подмножестве
,
- власть
.
Рассмотрим случай нечетного
.
Для подмножеств
,
И
давай запишем
Для оригинального набора
мы получаем оценку
Рассмотрим случай четного
.
Для подмножеств
,
И
давай запишем
Для оригинального набора
мы получаем оценку
Отвечать В результате в качестве ответа можно записать следующую систему уравнений (заменим обозначения
на
, потому что
зависит от переменных
И
)
В заключение отмечу, что ответ оказался немного сложнее, чем могло показаться при первом столкновении с проблемой.
Такая задача вряд ли подойдет для быстрого опроса, но она не слишком сложна, чтобы ее не задали в какой-то вариации на собеседовании.
Для проверки полученной формулы приведем следующие значения:
,
,
,
.
Соответственно, приведем таблицу различных кодов, возникающих в этом случае.
Потому что
, то запишем коды, составленные из упрощенного алфавита
.
Теги: #математика #комбинаторика #спортивное программирование #Занимательные задачи #математика
-
Однодневное Предложение От Альфа-Банка
19 Oct, 24 -
Машины На Чистом Svg
19 Oct, 24 -
Нишевый Конкурент Atom От Amd
19 Oct, 24 -
Нашёл Ли Twitter Свою Бизнес-Модель?
19 Oct, 24 -
Как Работают Финансы Облачных Компаний
19 Oct, 24
