代数 2026-08-12 含解答

一道原创代数题及解答

程国根 · 微信公众号「恩次方根」

正文文字 407 字公式 106 处

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

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

本题难度约为联赛二．

题目

给定正整数 n，设 σ为 1,2,…,n的任意一个置换．求

f(n)=∑_(k=1)^(m)σ(k)+∑_(k=m+1)^(n)σ^(−1)(k)

的最小值，其中m=⌊(n)/(2)⌋，σ^(−1)(k)表示 k的原像．

展开解答收起解答

解答

证明

称1,2,…,m称为“小数”，m+1,m+2,…,n称为“大数”．

设在σ(1),⋯,σ(m)中，恰有x个大数，于是其中 m−x个小数之和至少为

1+2+⋯+(m−x),

而 x个大数之和至少为

(m+1)+(m+2)+⋯+(m+x).

因此

∑_(k=1)^(m)σ(k);≥ 1+2+⋯+(m−x); +(m+1)+(m+2)+⋯+(m+x);= ((m−x)(m−x+1))/(2)+(x(2m+x+1))/(2).;

∑_(k=m+1)^(n)σ^(−1)(k)是所有大数所在位置的编号之和，其中恰有 x个大数位于前 m个位置，故这 x个位置编号之和至少为

1+2+⋯+x.

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

(m+1)+(m+2)+⋯+(n−x).

故

∑_(k=m+1)^(n)σ^(−1)(k);≥ 1+2+⋯+x; +(m+1)+(m+2)+⋯+(n−x);= (x(x+1))/(2)+((n−m−x)(m+1+n−x))/(2).;

于是

f(n) ≥((m−x)(m−x+1))/(2)+(x(2m+x+1))/(2); +(x(x+1))/(2)+((n−m−x)(m+1+n−x))/(2); =2x^(2)−nx+(n(n+1))/(2); =2(x−(n)/(4))^(2)+(3n^(2)+4n)/(8).;

由f(n)为整数知

f(n)≥⌈(3n^(2)+4n)/(8)⌉.

取等的构造

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

具体地：

若 n=4r，取 x=r；
若 n=4r+1，取 x=r；
若 n=4r+2，取 x=r或 x=r+1；
若 n=4r+3，取 x=r+1．

置换 σ的构造如下：

位置	放置的数
1,2,…,x	m+1,m+2,…,m+x
x+1,x+2,…,m	1,2,…,m−x
m+1,m+2,…,n−x	m+x+1,m+x+2,…,n
n−x+1,n−x+2,…,n	m−x+1,m−x+2,…,m

答案

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

minf(n)=⌈(3n^(2)+4n)/(8)⌉.

注

一、答案数列

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

二、另解

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

将σ(x)=y按照x,y是大数/小数的关系分成四类，计算每一类在f中的贡献．

进行调整，直到只剩下长度为4的置换(a,a,b,b)和不动点．

代数解题研究

在公众号查看原文 ↗ 反馈点公式可复制源码

留言

正常留言提交后可直接显示，无需人工审核；仍会经过防刷与垃圾内容过滤。请不要留下手机号等私人信息。解法、疑问都可以说；公式用 LaTeX：行内 $…$ ，整行 $$…$$。

题目

解答

证明

取等的构造

答案

注

一、答案数列

二、另解

留言

相关文章