       【附】为便于编辑修改，特提供纯文本文档如下： 一个高维空间计数极值问题 冯跃峰 2017年中国数学奥林匹克中有如下一个试题： 设n、k是正整数，T={（x，y，z）|x，y，z∈Ｎ，1≤x，y，z≤n}是空间直角坐标系中n3个整点构成的集合。已知T中（3n2-3n+1）+k个点被染成红色，满足如下条件：如果T中两点P、Q为红点，且PQ平行于坐标轴，则线段PQ上的所有整点都为红点。证明：存在至少k个互不相同的立方体，其棱长为1，且每个顶点为红点。 咋一看，觉得题中的数据“（3n2-3n+1）+k”非常奇怪：不仅含有两类参数，而且式子较为复杂。这自然想到，解题时先不必纠缠具体数值，可假定染有p个红点，然后估计红立方体的个数f（p）的下界。 进一步想到，可否求出f（p）的最小值？ 回答是肯定的。本文证明，对k维空间，按题设方式将p个格点染红色，则红色k维方格个数fk（p）的最小值为max{ p+（n-1）k-nk，0}。 先给出若干定义。 定义1：对k维空间Ω={（x1，x2，…，xk）|xi∈R，1≤i≤k}的点P（x1，x2，…，xk），若所有xi∈Z，1≤i≤k，则称P为格点。 定义2：对k维空间的点P（x1，x2，…，xk），固定k-1个分量x1，x2，…，xj-1，xj+1，xj+2，…，xk，而第j个分量取遍所有实数，则P运动得到的点的集合称为第j个维度方向上的一条直线。特别地，当固定的k-1个分量x1，x2，…，xj-1，xj+1，xj+2，…，xk都是整数时，相应直线称为第j个维度方向上的一条格线。 定义3：对任何整数x1，x2，…，xk，由k维空间的2k个点构成的集合G={（x1+i1，x2+i2，…，xk+ik）|it∈{0，1}，1≤t≤k}称为一个“k维方格”，G中每个点都称为k维方格的顶点，而点（x1，x2，…，xk）、（x1+1，x2+1，…，xk+1）分别称为该k维方格的“最小”、“最大”顶点。以（x1，x2，…，xk）为最小顶点的k维方格记为[x1，x2，…，xk]。 注意到G={（x1+i1，x2+i2，…，xk+ik）|it∈{0，1}=G1∪G2，其中 G1={（x1+i1，x2+i2，…，xj-1+ij-1，xj，xj+1+ij+1，…，xk+ik）|it∈{0，1}，1≤t≤k，t≠j}， G2={（x1+i1，x2+i2，…，xj-1+ij-1，xj+1，xj+1+ij+1，…，xk+ik）|it∈{0，1}，1≤t≤k，t≠j}。 而G1、G2都可分别看成是k维空间去掉第j个维度方向后得到的k-1维空间中的k-1维方格，且G2由G1按第j个维度方向平移一个单位长度后得到。 定理：对于k维空间nk个格点构成的n×n×…×n点阵：Ω={（x1，x2，…，xk）|xi∈N，1≤xi≤n，1≤i≤k}，将Ω中的部分格点按格线不间断地染成红色，即：对同一格线上的任意两个红点P（x1，x2，…，xk）、Q（y1，y2，…，yk），不妨设它们在第j（1≤j≤k）个维度方向的格线上，其中xi=yi（1≤i≤k，i≠j），xj<yj，则该格线上介于P、Q之间上的任意格点M（z1，z2，…，zk）都为红点，其中zi=xi=yi（1≤i≤k，i≠j），xj≤zj≤yj。 设共染有p个红点，记顶点为红色的k维方格的个数为fk（p），则fk（p）的最小值为max{ p+（n-1）k-nk，0}。 证明：对k归纳。当k=1时，1维方格为G={x1+i1|i1∈{0，1} }={x1，x1+1}，它可看成1维空间的单位线段。 由于格线上不间断地染了p个红格点，其红单位线段的条数f1（p）≥p-1（当p=0时等号不成立）。 又f1（p）≥0，所以f1（p）min= max{ p+（n-1）1-n1，0}，结论成立。 设结论对k-1成立，考察k的情形。 将nk个格点构成的n×n×…×n点阵分为n层，第r层格点构成的集合为Ωr={（x1，x2，…，xk-1，r）|xi∈N，1≤xi≤n，1≤i≤k-1}。 设Ωr上有pr个红格点，其中=p（1≤i≤n）。 由k-1维的结论，Ωr上k-1维红方格个数fk-1（pr）≥ pr+（n-1）k-1-nk-1，于是Ω1，Ω2，…，Ωn上k-1维红方格的个数：Sk-1==p+n（n-1）k-1-nk。 上述每个k-1维红方格都有一个最小顶点，共得到Sk-1个“最小顶点”。将所有Sk-1个“最小顶点”按所在第k维度方向格线的位置分为（n-1）k-1个类（对于k-1维方格[x1，x2，…，xk-1]，必须x1+1≤n，x2+1≤n，…，xk-1+1≤n，从而x1，x2，…，xk-1均有n-1种取值），设第j类中含有tj个“最小顶点”（1≤j≤（n-1）k-1），对应tj个红色k-1维方格，于是 =Sk-1≥p+n（n-1）k-1-nk。 下面证明，第j类 “最小顶点”在同一条第k个维度方向格线上的分布是“不间断”的（虽然由染色规则，每条第k个维度方向的格线上两个“最小顶点”之间的格点都是红色，但并不保证都是“最小顶点”）。 实际上，若有第k个维度方向的格线上的两个“最小顶点”P、Q之间的格点（z1，z2，…，zk）不是某个k-1维红方格的“最小顶点”，则存在i1，i2，…， ik∈{0，1}，使（z1+i1，z2+i2，…，zk+ik）不是红点。 设P、Q对应的k-1维红方格与（z1+i1，z2+i2，…，zk+ik）在同一第k个维度方向格线上的顶点分别为（x1+i1，x2+i2，…，xk+ik）、（y1+i1，y2+i2，…，yk+ik），则介于红点（x1+i1，x2+i2，…，xk+ik）、（y1+i1，y2+i2，…，yk+ik）之间的格点（z1+i1，z2+i2，…，zk+ik）不是红点，与染色规则矛盾。 所以，第j类“最小顶点”是同一第k个维度方向格线上的连续tj个红格点，它们产生tj-1个第k个维度方向的“单位红线段”（1≤j≤n-1）。 考察其中任意一条单位红线段AiAi+1，设其端点Ai（x1，x2，…，xk-1，i）、Ai+1（x1，x2，…，xk-1，i+1）分别是k-1维红方格Gi、Gi+1的“最小”顶点。 由于Ai（x1，x2，…，xk-1，i）按第k个维度方向平移一个单位长度后得到Ai+1（x1，x2，…，xk-1，i+1），所以k-1维方格Gi按第k个维度方向平移一个单位长度后得到Gi+1，于是Gi∪Gi+1是k维红方格。 由此可见，每条红单位线段AiAi+1至少对应一个k维红方格，从而第j类最小顶点产生至少tj-1个k维红方格。所以， fk（p）≥=-（n-1）k-1 ≥p+n（n-1）k-1-nk-（n-1）k-1=p+（n-1）（n-1）k-1-nk=p+（n-1）k-nk。 又显然fk（p）≥0，所以fk（p）≥max{ p+（n-1）k-nk，0}。 下面只需构造一种染色，使fk（p）=max{ p+（n-1）k-nk，0}。 当p=nk时，Ω中所有格点都被染红，红单位立方体个数fk（p）=（n-1）k= p+（n-1）k-nk，结论成立。 当p≤nk-（n-1）k时，max{ p+（n-1）k-nk，0}=0。 令πj={（x1，x2，…，xj-1，1，xj+1，xi+2，…，xk）|xi∈N，1≤xi≤n，1≤i≤k，i≠j}，π=π1∪π2∪…∪πk，则|π|=nk-（n-1）k，这是因为π以外的点构成（n-1）×（n-1）×…×（n-1）点阵，共有（n-1）k个点。 因为p≤|π|，按“字典排序规则”依次将π中排列在前面的p个格点染红色。所谓“字典排序规则”是指：对任何两个不同点P（x1，x2，…，xk）、Q（y1，y2，…，yk），设其对应分量不同的最小下标为i，即x1=y1，x2=y2，…，xi-1=yi-1，而xi≠yi。如果xi<yi，则P排在Q的前面。 显然，按“字典排序规则”依次将π中排列在前面的p个格点染红色，合乎“按格线不间断染色”的要求。易知，这p个红点不产生红色k维方格。 实际上，对任何k维方格G=[x1，x2，…，xk]，其“最大”顶点（x1+1，x2+1，…，xk+1）的任何分量都不为1，从而不属于π，所以其最大顶点不是红色。 此时，fk（p）=0=max{ p+（n-1）k-nk，0}，结论成立。 当nk-（n-1）k<p<nk时，max{ p+（n-1）k-nk，0}=p+（n-1）k-nk。 先将π中格点全部染红色，进而对剩下的（n-1）k个格点组成的（n-1）×（n-1）×…×（n-1）点阵，按“字典排序规则”依次将排在前面的p+（n-1）k-nk个格点染红色。 在染红π中全部格点后，每继续染红一个格点，便产生一个红色k维方格。比如，染红格点（2，2，…，2，2），产生唯一的红色k维方格[（1，1，…，1，1）]；再染红格点（2，2，…，2，3），又产生唯一的红色k维方格[（1，1，…，1，2）]，如此下去，直至产生p+（n-1）k-nk个红色k维方格。 此时，fk（p）=p+（n-1）k-nk=max{ p+（n-1）k-nk，0}，结论成立。 特别地，对k=3，有f3（p）的最小值为 max{ p+（n-1）3-n3，0}，所以f3（p）≥p+（n-1）3-n3。 将题中数据p=（3n2-3n+1）+k= n3-（n-1）3+k代入，可知p+（n-1）3-n3=k，故f3（p）≥k，这就是原题要证的结论。 |
|
|
