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

[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.

[zim32]

>> в некоторой вариации может быть предложен соискателю на собеседовании в крупную IT-компанию.
Интересно на какую позицию?

[gamekoff]

Ну что же вы прям так толсто троллите? Задача сформулирована в дискретном виде и вполне может быть дана, например, на собеседовании в Google, если вы попадете на on-site интервью к математику.

[zim32]

Просто в последнее время наметилась неприятная тенденция, когда на собеседовании от тебя требут примерно то что вы описали, а в итоге ты приходишь и правишь ресайз картинки в админке. Зачем?

[gamekoff]

Если вы опытный специалист в любой области, в частности в разработке ПО, то такие вопросы, скорее всего, вам на собеседовании задавать не будут. В этом случае достаточно будет обсудить ваш опыт работы и портфолио. С другой стороны, если вы начинающий специалист и у вас нет опыта работы и портфолио, как в таком случае работодателю выбрать вас? Тут появляются такого рода задачи, проще и сложнее. Работодатель пытается максимизировать потенциал молодого работника, который на момент собеседования ничего толком не знает, но который готов в этом направлении развиваться. Как справиться с таким отбором на junior-уровне? Не знаю. Хороший вариант – уметь такие задачи решать или хотя бы проявлять интерес к их решению. Можно пойти практическим путем – поскорее стать опытным специалистом, сделать хорошее портфолио.