В процессе научной работы у меня накопилось несколько интересных результатов, которые, с моей точки зрения, слабоваты для публикации в научном издании, однако сами по себе представляют интерес, например в области спортивного программирования. Один из таких результатов, который я сформулирую ниже, в некоторой вариации может быть предложен соискателю на собеседовании в крупную IT-компанию.
Итак, начну издалека. Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы]. Такие структуры, при некоторых достаточных условиях на параметры задачи, можно кодировать бесконечными в обе стороны символическими последовательностями, которые мы называем кодами. То есть, непрерывные решения дифференциального уравнения классифицируются дискретными кодами. Алфавит кодировки, как правило, конечен и состоит из некоторого нечетного числа символов, например из символов, где
– натуральное число. В алфавите есть нулевой символ
, а все остальные символы делятся на пары, связанные некоторой симметрией. Для простоты мы будем обозначать алфавит кодировки
, где символы
и
симметричны друг другу. Число
мы будем называть мощностью алфавита
.
Так как исследуемые нами структуры локализованы по пространству, то их коды начинаются и заканчиваются бесконечным числом нулевых символов, то есть имеют вид
Центральная часть кода , или его носитель, состоит из
символов, причем крайние символы носителя,
и
, не являются нулевыми символами. Число
мы будем называть длиной кода
. Теперь, для каждого кода
мы можем записать три симметричных кода,
где и
– две интересующие нас симметрии кодов. Задача ставится следующим образом: найти число всех кодов длины
, составленных из алфавита мощности
с точностью до двух симметрий
и
. То есть, если два произвольных кода связаны симметриями
,
или
, то мы считаем такие коды одинаковыми. В условиях цейтнота, на собеседовании, довольно быстро можно ответить, что число всех кодов без учета симметрий равно
. Дальше, с моей точки зрения, задачу следует решать с карандашом в руках. Сразу скажу, что мое решение может быть не оптимальным (в смысле количества и простоты математических операций). Пользователь mihaild предложил очень элегантное решение такой задачи через группу инвариантных перестановок и лемму Бёрнсайда.
Обозначим множество всех кодов . Разобьем
на три непересекающихся подмножества
В подмножестве коды имеют следующую структуру
В подмножестве коды имеют следующую структуру
Соответственно, по определению, в подмножествах и
коды разбиваются на пары
, а в подмножестве
– на четверки
, то есть
где – число различных кодов в подмножестве
,
– мощность
. Рассмотрим случай нечетного
. Для подмножеств
,
и
запишем
Для исходного множества получим оценку
Рассмотрим случай четного . Для подмножеств
,
и
запишем
Для исходного множества получим оценку
В итоге, в качестве ответа можно записать следующую систему уравнений (заменим обозначение на
, так как
зависит от переменных
и
)
В заключении отмечу, что ответ получился немного сложнее, чем могло показаться при первом знакомстве с задачей. Подобная задача вряд ли годится для блиц-опроса, но и не является чересчур сложной, чтобы в какой-нибудь вариации не быть предложенной на собеседовании. Для проверки полученной формулы приведем следующие значения: ,
,
,
. Соответственно, приведем таблицу различных кодов, возникающий в этом случае. Так как
, то мы выпишем коды, составленные из упрощенного алфавита
.
Комментарии (7)
zim32
27.12.2016 01:47+3>> в некоторой вариации может быть предложен соискателю на собеседовании в крупную IT-компанию.
Интересно на какую позицию?am-amotion-city
27.12.2016 12:07+3Тренер по стационарным локализованным структурам в одномерном уравнении Гросса-Питаевского?
gamekoff
27.12.2016 12:15-2Ну что же вы прям так толсто троллите? Задача сформулирована в дискретном виде и вполне может быть дана, например, на собеседовании в Google, если вы попадете на on-site интервью к математику.
zim32
29.12.2016 16:27Просто в последнее время наметилась неприятная тенденция, когда на собеседовании от тебя требут примерно то что вы описали, а в итоге ты приходишь и правишь ресайз картинки в админке. Зачем?
gamekoff
29.12.2016 18:03Если вы опытный специалист в любой области, в частности в разработке ПО, то такие вопросы, скорее всего, вам на собеседовании задавать не будут. В этом случае достаточно будет обсудить ваш опыт работы и портфолио. С другой стороны, если вы начинающий специалист и у вас нет опыта работы и портфолио, как в таком случае работодателю выбрать вас? Тут появляются такого рода задачи, проще и сложнее. Работодатель пытается максимизировать потенциал молодого работника, который на момент собеседования ничего толком не знает, но который готов в этом направлении развиваться. Как справиться с таким отбором на junior-уровне? Не знаю. Хороший вариант – уметь такие задачи решать или хотя бы проявлять интерес к их решению. Можно пойти практическим путем – поскорее стать опытным специалистом, сделать хорошее портфолио.
mihaild
Такие задачи легко решаются через лемму Бернсайда.
Всего объектов (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, получаем ответ (вроде бы совпадающий с вашим).
gamekoff
Да, вы правы. Только у T_1 (соответственно, у T_1T_2) неподвижных точек (N — 1) * N^{M/2 — 1}. Складывая все вместе и деля на 4 мы получаем ответ для четного M.