     【附】为便于编辑修改，特提供纯文本文档如下： 2021年中国台湾数学竞赛组合极值问题思路剖析与新解 冯跃峰 【真题2-4】在m×n的方格棋盘中，有些方格被填入一个字母X，有些方格为空格。将每个填有X的格都赋值0；每个空格都赋值为与此格相连且填有X的方格个数。这里，如果两个方格有公共顶点，则称为彼此相邻。设f（m，n）为棋盘中所有赋值总和的最大值。求最小的实数C，使得(f（m，n）)/mn≤C，对任意正整数m、n恒成立。（2021中国台湾数学奥林匹克） 【题感】从条件看，我们称题中的棋盘为m×n布阵，其赋值总和记为Sm。 从目标看，属于双重最值问题。这可分两步进行：先估计f（m，n）的下界，由此确定C的下界C0。然后证明不等式(f（m，n）)/mn≤C0成立。 如何求最大值f（m，n）？由于题目不提供“算法”，可先构造一种m×n布阵，使赋值总和尽可能大。 但m、n不具体，直接构造存在困难，可先研究特例。 【研究特例】考察2×2的布阵，本质上有4种情形。 其中有两种情形的赋值总和都达到最大值f（m，n）=4。此时还难以看出规律，继续研究特例。 考察2×3的布阵，除去明显可加入、减少X使f（m，n）增加的布阵，本质上还有18种情形。 其中有两种情形的赋值总和都达到最大值f（m，n）=8，且有共同规律。 【特征迁移】由此发现，使赋值总和都达到最大值f（m，n）的布阵是：序号为奇的列（称为“奇列”）都填入X。 【注】研究特例是解题中一根有效的“拐棍”，当解题遇到困难时常有奇效。更多的研究特例的例子可百度“跃峰奥数研究特例”查看。 【通式构造】将m×n棋盘的奇列方格都填入X，当n为奇数时，令n=2k+1（k∈N），在有k个偶列赋值为4，6，6，…，6，4。此时， Sm=[2×4+6（m-2）]k=（6m-4）k=（3m-2）（n-1）； 当n为偶数时，令n=2k（k∈N+），则有k-1个偶列赋值为4，6，6，…，6，4，一个偶列赋值为2，3，3，…，3，2。此时， Sm=[2×4+6（m-2）]（k-1）+[2×2+3（m-2）] =（6m-4）（k-1）+（3m-2）=（3m-2）（n-1）。 两种情况结果一致，表明f（m，n）有统一的下界。 所以f（m，n）≥Sm=（3m-2）（n-1）， (f（m，n）)/mn≥(（3m-2）（n-1）)/mn=3+(2-2m-n)/mn→3（m→∞，n→∞）。 依题意，(f（m，n）)/mn≤C（∀m、n∈N+），所以C≥3。 否则，C<3，令e=3-C，由极限的意义，存在m、n，使3-(（3m-2）（n-1）)/mn<e=3-C，即(（3m-2）（n-1）)/mn>C，从而(f（m，n）)/mn≥(（3m-2）（n-1）)/mn>C，矛盾。 下面证明C=3合乎要求，即(f（m，n）)/mn≤3（∀m、n∈N+）。 这是一个“与自然数相关”的命题，可优先考虑归纳法。本题比较简单，直接对m归纳即可。 【数学归纳法】我们只需证明对任何m×n布阵，都有Sm≤3mn。 当m=1时，每个方格最多有两个相连格，所以每个方格赋值至多为2，此时，S1≤2n<3mn，结论成立。 设结论对m成立，考虑（m+1）×n布阵。 【化归】去掉最后一行，得到m×n棋盘，相对于m×n布阵，原棋盘只有第m行可能某些格的赋值需要改变，设改变后的赋值之和为Sm'，由归纳假设，Sm'≤3mn。 现在将去掉的一行加回，则该行中的X使前述的m×n布阵中某些格的赋值增加1。 为了确定其增加的总量，需要知道添加的一行中有多少个X，这引入容量参数即可。 【容量参数】添加第m+1行，设该行中有r个X。 显然，该行中每个X至多与上一行的3个格相连，从而至多使上一行3个格的赋值各增加1，于是每个X产生的增量至多为3。 r个X产生的增量至多为3r，所以Sm+1≤Sm'+3r+S1，其中S1是第m+1行方格赋值的和。 考察第m+1行的任意一个空格g，设g与上一行的t个X相连，则有以下情况： （1）g与同行的2个X相连，则g的赋值f（g）=2+t。这两个X的增量和相对于以前计入的增量至少减少t，所以g的“有效”赋值不大于（2+t）-t=2。 （2）g只与同行的1个X相连，则g的赋值f（g）=1+t。这个X的增量相对于以前计入的增量至少减少t-1，所以g的“有效”赋值不大于（1+t）-（t-1）=2。 （3）g不与同行的X相连，则g至多与上一行的3个格相连，其赋值f（g）≤3。 于是，n-r个空格有效赋值的和不大于3（n-r）。 所以，Sm+1≤Sm'+3r+3（n-r）≤3mn +3n=3n（m+1），结论成立。 因为任何m×n布阵，都有Sm≤3mn，特别地，当然有f（m，n）≤3mn，所以(f（m，n）)/mn≤3。故C的最小值为3。 【新写】将m×n棋盘的奇列方格都填入X，则各格的赋值总和 Sm=（3m-2）（n-1）。所以f（m，n）≥Sm=（3m-2）（n-1）， (f（m，n）)/mn≥(（3m-2）（n-1）)/mn=3+(2-2m-n)/mn→3（m→∞，n→∞）。 由题意，(f（m，n）)/mn≤C（∀m、n∈N+），所以C≥3。 否则，C<3，令e=3-C，由极限的意义，存在m、n，使3-(（3m-2）（n-1）)/mn<e=3-C，即(（3m-2）（n-1）)/mn>C，从而(f（m，n）)/mn≥(（3m-2）（n-1）)/mn>C，矛盾。 下面证明对任何m×n布阵，都有Sm≤3mn。 当m=1时，每个方格赋值至多为2，此时，S1≤2n<3mn，结论成立。 设结论对m成立，考虑（m+1）×n布阵。去掉最后一行，得到m×n棋盘，相对于m×n布阵，原棋盘只有第m行可能某些格的赋值需要改变，设改变后的赋值之和为Sm'，由归纳假设，Sm'≤3mn。 加回第m+1行，设该行中有r个X。每个X至多与上一行的3个格相连，于是每个X产生的增量至多为3。r个X产生的增量至多为3r，所以Sm+1≤Sm'+3r+S1，其中S1是第m+1行方格赋值的和。 考察第m+1行的任意一个空格g，设g与上一行的t个X相连。 （1）g与同行的2个X相连，则g的赋值f（g）=2+t。这两个X的增量和相对于以前计入的增量减少t，所以g的“有效”赋值不大于（2+t）-t=2。 （2）g只与同行的1个X相连，则g的赋值f（g）=1+t。这个X的增量相对于以前计入的增量减少t-1，所以g的“有效”赋值不大于（1+t）-（t-1）=2。 （3）g不与同行的X相连，则g至多与上一行的3个格相连，其赋值f（g）≤3。 于是，若每个X格的增量都按3计算，则每个空格的赋值不大于3，所以一共n-r个空格的赋值和不大于3（n-r）。 所以，Sm+1≤Sm'+3r+3（n-r）≤3mn +3n=3n（m+1），结论成立。 因为任何m×n布阵，都有Sm≤3mn，特别地，当然有f（m，n）≤3mn，故(f（m，n）)/mn≤3。 综上所述，C的最小值为3。 【注】没有看到“官方”解答，我们的解答可能不是最佳的。 |
|
|
