命题灵感来自棋盘上个互不攻击的车及其位置．原计划用于命题研讨会投稿，但一直怀疑已有类似问题，遂暂时搁置．

今天用 GPT 再次检索，仍未发现更早出处，故将题目及解答整理发出．

本题难度约为联赛二．

题目

给定正整数 ，设 为 的任意一个置换．求

的最小值，其中，表示 的原像．

解答

证明

称称为“小数”，称为“大数”．

设在中，恰有个大数，于是其中 个小数之和至少为

而 个大数之和至少为

因此

是所有大数 所在位置的编号之和，其中恰有 个大数位于前 个位置，故这 个位置编号之和至少为

其余 个大数位于后面的 个位置，它们的位置编号之和至少为

故

于是

由为整数知

取等的构造

由于 为整数，所以右端在 取最接近 的整数时最小．

具体地：

• 若 ，取 ；
• 若 ，取 ；
• 若 ，取 或 ；
• 若 ，取 ．

置换 的构造如下：

答案

容易验证上述构造满足要求，因此所求最小值为

注

一、答案数列

本题答案数列恰为OEIS A282513，但暂未发现两者关联，感兴趣的读者可以尝试一下．

二、另解

将分解为若干个不交的置换．

将按照是大数/小数的关系分成四类，计算每一类在中的贡献．

进行调整，直到只剩下长度为的置换和不动点．