     【附】为便于编辑修改，特提供纯文本文档如下： 2018年CMO中一个操作问题剖析与解答 冯跃峰 2018年CMO有一个颇为有趣的极值操作问题，题目如下： 【问题】在n×n方格的每个格都填一个整数，每次操作选取一个方格，将其同行、同理的2n-1个数都加1，其余数不变。求最大的正整数N，使得任何数表，均可通过有限次操作使表中至少有N个偶数。（2018中国数学奥林匹克第5题） 该题难度适中，解题入口较低，可从多个角度思考。下面介绍我们的一种思考方式。 【题感】本题所求的极值，既是“任意型”的，又是“存在型”的，从而不等式论证及验证等号成立两个方面都需要构造。 对于证明不等式N≤C，需要构造一个特定的数表，证明不论怎样操作，都不能使M中多于C个偶数；对于验证N=C合乎要求，需要对任一数表M，构造一系列操作，使M产生至少C个偶数。 由于两种构造都一时难以发现，可先研究特例。 【研究特例】当n=1时，显然N的最大值为1。 当n=2时，先考虑“最难”操作的棋盘（偶数最少）能产生多少偶数。为方便，将表中的数都按模2理解。 取数表M=，尝试如下操作。第一次操作本质上是唯一的： →。 至此，表中剩下惟一的奇数，自然想到对该奇数操作，得到： →。 现在，表中有2个奇数，接下来自然想是对其中一个奇数操作，得到： →。 以下无需继续操作，仔细观察，便有惊喜。 【发掘性质】通过上述3次操作后，恰有格（1，2）改变了奇偶性。我们将上述3次操作捆绑看成一个“大操作”，并认为该大操作是对格（1，2）进行的，它包含的3个基本操作分别是对格（1，2）所在行与列的3个格进行的。 显然，将每个填奇数的格都进行一次大操作，则所有数都变成偶数，所以N的最大值为4。 【归纳通式】上述大操作的性质是否对任何阶数表都成立呢？考察一般的n×n数表，可类似定义大操作。为叙述问题方便，先给出如下定义： 【引入定义】由棋盘一行与一列方格构成的图形称为“十字形”，其中既在行中又在列中的那个格称为十字形的中心。 对以（i，j）为中心的十字形的每个格分别进行一次操作，将这2n-1次操作捆绑，称为对格（i，j）进行的一个大操作。 【发掘性质】在对格（i，j）进行的大操作中，十字形的中心格改变2n-1次奇偶性，十字形的其它格改变n次奇偶性（同行或同列的n个操作）。此外，不在该十字形中的格改变2次奇偶性，是因这样的格所在行与列与该十字形有两个公共格。 显然，要使只有中心格改变奇偶性，其它格的奇偶性不变的充分必要条件是n为偶数。 【构造操作序列】由此可见，当n为偶数时，对所有填奇数的格都进行一次大操作，则所有格都变成偶数，此时N的最大值为n2。 【分割化归】对n为奇数的情形，可化归到n为偶数的情形处理。 首先，左上角的（n-1）×（n-1）棋盘中的数都可按上述方式操作到全为偶数，剩下第n行与第n列共2n-1个格中可能有奇数。 如果这2n-1个格中填奇数的格超过n-1个，则对格（n，n）进行一次基本操作，于是，总可使这2n-1个格中至少有n个偶数。 所以，存在有限次操作，使表中至少有（n-1）2+n=n2-n+1个偶数，所以N= n2-n+1合乎条件。 下面证明N≤n2-n+1（n为奇）。 【构造数表】我们要构造一个数表，使无论怎么操作，都不能产生n2-n+2个偶数。换句话说，就是表中任何时候都至少有n-1个奇数。 【发掘不变量】我们先发掘操作的特征，它有一个显然的不变量：每次操作使每行中奇数（1或n）个格改变奇偶性，整个数表中也是奇数个格改变奇偶性。如果用Si表示第i行各数的和，S表示所有数的和，则操作中Si+Sj、S+Si的奇偶性都不变。 【找充分条件】为了存在至少n-1个奇数，一个充分条件是有n-1行各至少一个奇数，即有n-1个Si为奇。结合不变性，想到如下构造： 取表中第1行全为0，其余行都为1。此时，S1=0为偶，Si=n（2≤i≤n）为奇，于是由操作中的不变性可知，S1+Si恒为奇。 考察操作中的任一时刻，如果S1为偶，则Si为奇，所以第i行至少一个奇数。注意到i=2，3，…，n，所以表中至少n-1个奇数。 【对称处理】如果S1为奇，则Si（2≤i≤n）为偶，此时S=S1+S2+…+Sn为奇。 记第j中数的和为Tj（1≤i≤n），则由对称性可知，S+Tj的奇偶性都不变。 由于最初表中S+Tj为偶，所以操作中恒有S+Tj为偶。但上述时刻S为奇，所以该时刻Tj为奇，从而每列至少一个奇数，所以表中至少n个奇数。 所以N的最大值为n2-n+1。 注：后一部分采用反证法更为简单。 如果某个时刻表中最多有n-2个奇数，则必存在除第一行外的一行全为偶数，也存在一列全为偶数，考察该行该列组成的去掉了中心的“空心十字架”，记其所有数的和为S。由于每次操作改变空心十字架中2或n-1或2n-2个数的奇偶性，所以操作中S不变。 但最初状态中S0=2n-3为奇，目标状态中S1=0为偶，矛盾。 【新写】由棋盘一行与一列方格构成的图形称为“十字形”，其中既在行中又在列中的那个格称为十字形的中心。 对以（i，j）为中心的十字形的每个格分别进行一次操作，将这2n-1次操作捆绑，称为对格（i，j）进行的一个大操作。其中，十字形的中心格改变2n-1次奇偶性，十字形的其它格改变n次奇偶性，不在该十字形中的格改变2次奇偶性（是因这样的格所在行与列与该十字形有两个公共格）。 当n为偶数时，每个大操作只改变中心格的奇偶性，对所有填奇数的格都进行一次大操作，则所有格都变成偶数，此时N的最大值为n2。 对n为奇数的情形，对左上角的（n-1）×（n-1）棋盘按上述方式操作，使其变得全为偶数。对剩下第n行与第n列共2n-1个格，若奇数超过n-1个，则对格（n，n）进行一次基本操作。于是，总可使这2n-1个格中至少有n个偶数。 所以，存在有限次操作，使表中至少有（n-1）2+n=n2-n+1个偶数，所以N= n2-n+1合乎条件。 下面证明N≤n2-n+1（n为奇）。 如果某个时刻表中最多有n-2个奇数，则必存在除第一行外的一行全为偶数，也存在一列全为偶数，考察该行该列组成的去掉了中心的“空心十字架”，记其所有数的和为S。 由于每次操作改变空心十字架中2或n-1或2n-2个数的奇偶性，所以操作中S不变。 但最初状态中S0=2n-3为奇，目标状态中S1=0为偶，矛盾。 综上所述，n为奇时，N的最大值为n2-n+1；n为偶时，N的最大值为n2。 |
|
|
