序号函数是什么(序号公式是什么)

导语：序号函数：一个组合几何中格点问题的代数刻画

【附】为便于编辑修改，特提供纯文本文档如下：

序号函数：一个组合几何中格点问题的代数刻画

冯跃峰

对于离散点集问题，一种常见的处理方式，是对已知点适当编号，然后借助代数手法，发掘点集的性质。

一种常用的编号方式，就是用相应的参数刻画点的位置，使各点之间具有某种顺序。我们称这样的编号为“序号”。

如果序号涉及k个参数，则称之为k维序号，记为（x1，x2，…，xk），它类似于k维空间中点的坐标。

此外，代数手法也是多种多样的，本文介绍一种行之有效的处理方式：引入序号函数。

所谓“序号函数”，就是对k维序号（x1，x2，…，xk）中的参数进行适当运算，使每个点都对应一个数值，记为f（x1，x2，…，xk）。然后通过对其函数值f（x1，x2，…，xk）隐含性质或特征的发掘与研究，找到解决问题的途径。

序号函数可以有效刻画点集特征，从而方便我们对点集进行规划和安排。下面举一个例子来说明。

【问题】设X={（x1，x2，…，xn）| x1，x2，…，xn∈Z}是n维空间所有格点的集合，对X中任意两个格点A（x1，x2，…，xn）、B（y1，y2，…，yn），定义它们的距离为：|A-B|=|x1-y1|+|x2-y2|+…+|xn-yn|。

求r的最小值，使得能将X中的点r-染色，分别满足以下要求：

（1）任何两个同色的格点A、B，满足|A-B|≥2；

（2）任何两个同色的格点A、B，满足|A-B|≥3。（原创题）

【题感】从目标看，本题属于“存在型”组合极值，但条件不提供算法，宜从等式入手：构造一种色数尽可能少的染色，由此猜出色数的最小值。

从规则看，染色方法是由“距离”不等式|A-B|≥2限定的。而该不等式的反面容量远远小于正面容量（[2，+∞）与{1}之间的显著差别），可采用补集思考：只需适当染色，使满足|A-B|=1的任意两点A、B都异色。——这可采用局部扩展策略。

从条件看，n维空间过于抽象，不妨从特例开始，先考察2维空间的格点集合。

【研究特例】（1）先考虑n=2的情形。

【局部扩展】取点A为红色，则由条件可知， A的邻点都不是红色。因为A的任何两个邻点的距离都是2，可采用最简单的构造：将其邻点都染蓝色。

如此下去，发现相间染色（类似于国际象棋盘）合乎要求。

【本质推广】现在的问题是，在n维空间中能否有类似的“相间染色”，使同色点A、B满足：|A-B|≥2？

“相间”是一种几何上的位置刻画：在特定排序中间隔一个对象。但对于高于3维的空间，“相间”没有确切的含义。我们需要一种更广泛的本质描述，以便推广到高维空间。

由此想到棋盘中奇偶格的定义：当i+j为奇（偶）时，称格aij为奇（偶）格。

早在1987年1月，笔者在《中等数学》上发表的“格阵”一文，首次给出这一定义，目的是想说明：用格的“奇偶性”代替“黑白染色”，具有更广泛的意义。但当时有人由于没有看清这一点，对其做法不以为然，讥讽为“故意将文章写得别人看不懂”——其实是他们不懂我的心，我当然也就不以为意。

实际上，格的奇偶性可以推广到任何高维空间，也揭示了黑白相间染色的本质。引入序号函数：坐标分量之和，则高维空间中相邻两点对应的函数值不同奇偶——这也是我编拟这道题的初衷。

【序号函数】对于格点A（x1，x2，…，xn），其所有邻点可表示为（x1，x2，…，xi-1，xi±1，xi+1，…，xn）。定义f（A）=x1+x2+…+xn为A的特征值，则对任何相邻两点A、B，有f（A）、f（B）不同奇偶。

这样，将特征值为奇数的点染红色，特征值为偶数的点染蓝色，则染色合乎要求。问题（1）迎刃而解。

【新写】（1）首先，因为所有点不全同色，所以r≥2。

其次，当r=2时，对格点A（x1，x2，…，xn），称f（A）= f（x1，x2，…，xn）=x1+x2+…+xn为A的特征值。

因为相邻两点（距离为1）的坐标恰有一个分量相差1，其他分量都相同，从而相邻点的特征值不同奇偶。于是，将特征值为奇数的点染红色，特征值为偶数的点染蓝色，则染色合乎要求。

实际上，如果A、B同色，则由染色规则知，它们不相邻，从而|A-B|≥2。

综上所述，r的最小值为2。

下面考虑（2），求r的最小值，使任何两个同色的格点A、B，满足|A-B|≥3。

【研究特例】先考虑n=2的情形。

【局部扩展】取点A为1色，则由条件可知， A的邻点都不是1色。而且A的4个邻点两两异色。否则，设A的两个邻点B、C同色，但|B-C|=2<3，矛盾。由此可见，r≥5。

如果r=5，不妨设A的4个邻点分别为2、3、4、5色，这5个点形成一个以A为中心的“十字架”。

如此下去，发现染色使每个“十字架”中的点两两异色时合乎要求。

值得指出的是，这并不是“染色方法”，仅仅是“目标要求”，因为它并没有告诉我们如何染色。构造中务必注意：不能用“目标要求”代替具体构造。

如何使每个“十字架”中的点两两异色？关键是引入点的序号函数：每个点都对应一个函数值，使每个“十字架”的点对应函数值都属于不同类（这当然需要函数值互异）。

【以简驭繁】先尝试最简单的函数：f（x，y）=x+y。

因为以（x，y）为中心的“十字架”的其他4个点为（x±1，y），（x，y±1），但由上述定义，有

f（x+1，y）=x+y+1= f（x，y+1），不合要求。

如何修改函数，使（x+1，y）与（x，y+1）的函数值不同？——这稍作改变，将y的系数更改为2即可。

【改进函数】令f（x，y）=x+2y即可，此时，5个特征值为：

f（x，y）=x+2y，f（x+1，y）=x+2y+1，f（x-1，y）=x+2y-1，f（x，y+1）=x+2y+2，f（x，y-1）=x+2y-2，

它们构成模5的完系。

将特征值属于模5的同一个剩余类中点染同一种颜色，可知5种颜色足够。从而r的最小值为5。

如何推广到n维空间？——希望找到一个类似的“十字架”。

【发掘特征】“十字架”的特征是（不能迁移形状，只能迁移特征）：一个点及其所有邻点构成的集合。

要学会用数学语言对有关形象进行描述，它通常可一字不改地推广到高维空间。这是一种非常重要的基本功。

【特征迁移】对n维空间，考察任意一个点A，由A及其所有邻点构成的集合称为一个“群”，其中点A为该群的中心。注意：邻点的邻点不能归入同一个群。

【符号刻画】对A∈X，称集合Q（A）={P∈X｜|P-A|≤1}是以A为中心的一个群。

显然，以A为中心的群中任何两点的距离不大于2，这是因为P、Q到A的距离都不大于1。

【平凡估计】对于点A0（x1，x2，…，xn），它有2n个邻点：（x1，x2，…，xi-1，xi±1，xi+1，…xn）（1≤i≤2n），若染色合乎要求，则这2n+1个点两两异色，所以r≥2n+1。

下面构造一种含有2n+1种颜色的染色，使任何两个同色点的距离不小于3，这只需将2维空间的序号函数迁移到n维空间即可。

【归纳通式】将2维空间的序号函数f（x，y）=x+2y，直接迁移到n维空间，变为f（x1，x2，…，xn）=x1+2x2+…+nxn。

【染色方案】每个“群”中所有点的特征值构成模2n+1的完系，将特征值模2n+1同余的点染同一种颜色，可知2n+1种颜色足够，从而r的最小值为2n+1。

【新写】（2）对A∈X，称集合Q（A）={P∈X｜|P-A|≤1}是以A为中心的一个群。考察以A0（x1，x2，…，xn）为中心的群，它的另2n个点为Ai（x1，x2，…，xi-1，xi+1，xi+1，…xn），An+i（x1，x2，…，xi-1，xi-1，xi+1，…xn）（1≤i≤n），若染色合乎要求，则这2n+1个点两两异色。

实际上，由|A0-Ai|=1<3（1≤i≤2n），知A0与Ai异色；由|Ai-Aj|=2<3（1≤i<j≤2n），知Ai与Aj异色。所以r≥2n+1。

当r=2n+1时，对格点A（x1，x2，…，xn），称f（A）= f（x1，x2，…，xn）=x1+2x2+…+nxn为A的特征值，则以A为中心的群中各点的特征值分别为f（A），f（A）±1，f（A）±2，…，f（A）±n，它们构成模2n+1的完系。

将特征值模2n+1的余数为i（1≤i≤2n+1）的点染第i种颜色，则每一个群中没有同色点。

下面证明染色合乎要求。实际上，如果|A-B|≤2，则A、B或者相邻，或者同为某个点的邻点。从而A、B属于同一个群，由染色规则知A、B异色。

由此可见，若A、B同色，则|A-B|≥3，所以r=2n+1合乎条件。

综上所述，r的最小值为2n+1。

遗留问题：（I）求r的最小值，对任何两个同色的格点A、B，有|A-B|≥4。

（II）我们还可进一步考虑，求r的最小值，对任何两个同色的格点A、B，有|A-B|≥k（k是给定的大于1的整数）。

期待大家给出好的结果，并欢迎交流与指正！

本文内容由小琪整理编辑！