给定一个 $n\times n$ 的 方格表，每个格子中填入一个整数，每次操作选择一个方格，将其同行，同列的 $2n-1$ 个数都加 $1$．求最小 $N(n)$，使得无论开始时方格表内数填的是多少，均可以通过有限此操作使得方格表内至少有 $N(n)$ 个 偶数．
【难度】
【出处】
2018第34届CMO试题
【标注】
【答案】
略
【解析】
当 $n$ 是偶数时，$N(n)=n^{2}$；当 $n$ 是奇数时 $N(n)=n^{2}-n+1$．首先构造一些操作组合．
设选取 $(i,j)$ 位置的方格所进行的操作为 $C(i,j)$，其中 $1\leqslant i,j\leqslant n$．
$C(i, j), C\left(i, j^{\prime}\right), C\left(i^{\prime}, j\right), C\left(i^{\prime}, j^{\prime}\right)$ 合并得到改变四个位置 $(i, j),\left(i^{\prime}, j\right),\left(i, j^{\prime}\right),\left(i^{\prime}, j^{\prime}\right)$ 的操作，记为 $D\left(i, i^{\prime}, j, j^{\prime}\right)$．
$C(i, j), C\left(i, j^{\prime}\right)$ 得到改变 $j, j^{\prime}$ 两列，但不改变 $(i, j),\left(i, j^{\prime}\right)$ 奇偶性的操作，记为 $E\left(i, j, j^{\prime}\right)$．
当 $n$ 是偶数时，$E\left(i, j, j^{\prime}\right)$ 在两列上各改变 $n-1$（奇数）个格子的奇偶性，复合 $(n-2) / 2$ 个 $D\left(i^{\prime}, i^{\prime \prime}, j, j^{\prime}\right)$ 操作，可以得到只改变某两个（同行）格子 $(k, j),\left(k, j^{\prime}\right)$ 上奇偶性的操作，记为 $F\left(k, j, j^{\prime}\right)$．
当 $n$ 是偶数时，同理可得到改变两个同列格子奇偶性的操作记为 $G\left(k, k^{\prime}, j\right)$．
当 $n$ 是偶数时，一个 $C(i, j)$，配合 $n / 2$ 个 $F$ 类操作，及 $n / 2$ 个 $G$ 类操作，可以得到只改变一个格子奇偶性的操作，因此这时任何初始情况可以得到全是偶数的方格表．
当 $n$ 是奇数时，通过 $D(1, i, 1, j)$ 类型的操作，可使所有的奇数位于第一行或第一列，然后选择进行或者不进行 $C(1,1)$ 操作，可以使奇数总数不超过 $n-1$．
当 $n$ 是奇数时，每个 $C(i, j)$ 操作任何两行的并集中偶数个格子，因此两行并集中的奇数个数奇偶性不变；同理两列并集中奇数个数奇偶性不变．
取初始状态为：第一列为奇数，其他所有数为偶数．初始第一列奇数个数与其他列不同，所有行奇数个数相同．设结束第一列有 $a$ 个奇数．
若 $a$ 是偶数，则第 $2$ 到 $n$ 列每列有奇数个奇数，因此总数至少 $n-1$ 个奇数．
若 $a$ 是奇数，则第 $2$ 到 $n$ 列每列有偶数个奇数，所有数总和为奇数；因为每行奇数个数奇偶性相同，方格表中奇数总数奇偶性与每行奇数个数奇偶性相同，因此每行有奇数个奇数，总数至少 $n$ 个奇数．
综上所述，当 $n=2k$ 是偶数时，可以操作所有数为偶数，$N(2 k)=4 k^{2}$；当 $n=2k+1$ 是奇数时，可以操作使奇数个数不超过 $n-1$，而且存在初始状态使奇数个数不能更小，$N(2 k+1)=4 k^{2}+2 k+1$．
设选取 $(i,j)$ 位置的方格所进行的操作为 $C(i,j)$，其中 $1\leqslant i,j\leqslant n$．
$C(i, j), C\left(i, j^{\prime}\right), C\left(i^{\prime}, j\right), C\left(i^{\prime}, j^{\prime}\right)$ 合并得到改变四个位置 $(i, j),\left(i^{\prime}, j\right),\left(i, j^{\prime}\right),\left(i^{\prime}, j^{\prime}\right)$ 的操作，记为 $D\left(i, i^{\prime}, j, j^{\prime}\right)$．
$C(i, j), C\left(i, j^{\prime}\right)$ 得到改变 $j, j^{\prime}$ 两列，但不改变 $(i, j),\left(i, j^{\prime}\right)$ 奇偶性的操作，记为 $E\left(i, j, j^{\prime}\right)$．
当 $n$ 是偶数时，$E\left(i, j, j^{\prime}\right)$ 在两列上各改变 $n-1$（奇数）个格子的奇偶性，复合 $(n-2) / 2$ 个 $D\left(i^{\prime}, i^{\prime \prime}, j, j^{\prime}\right)$ 操作，可以得到只改变某两个（同行）格子 $(k, j),\left(k, j^{\prime}\right)$ 上奇偶性的操作，记为 $F\left(k, j, j^{\prime}\right)$．
当 $n$ 是偶数时，同理可得到改变两个同列格子奇偶性的操作记为 $G\left(k, k^{\prime}, j\right)$．
当 $n$ 是偶数时，一个 $C(i, j)$，配合 $n / 2$ 个 $F$ 类操作，及 $n / 2$ 个 $G$ 类操作，可以得到只改变一个格子奇偶性的操作，因此这时任何初始情况可以得到全是偶数的方格表．
当 $n$ 是奇数时，通过 $D(1, i, 1, j)$ 类型的操作，可使所有的奇数位于第一行或第一列，然后选择进行或者不进行 $C(1,1)$ 操作，可以使奇数总数不超过 $n-1$．
当 $n$ 是奇数时，每个 $C(i, j)$ 操作任何两行的并集中偶数个格子，因此两行并集中的奇数个数奇偶性不变；同理两列并集中奇数个数奇偶性不变．
取初始状态为：第一列为奇数，其他所有数为偶数．初始第一列奇数个数与其他列不同，所有行奇数个数相同．设结束第一列有 $a$ 个奇数．
若 $a$ 是偶数，则第 $2$ 到 $n$ 列每列有奇数个奇数，因此总数至少 $n-1$ 个奇数．
若 $a$ 是奇数，则第 $2$ 到 $n$ 列每列有偶数个奇数，所有数总和为奇数；因为每行奇数个数奇偶性相同，方格表中奇数总数奇偶性与每行奇数个数奇偶性相同，因此每行有奇数个奇数，总数至少 $n$ 个奇数．
综上所述，当 $n=2k$ 是偶数时，可以操作所有数为偶数，$N(2 k)=4 k^{2}$；当 $n=2k+1$ 是奇数时，可以操作使奇数个数不超过 $n-1$，而且存在初始状态使奇数个数不能更小，$N(2 k+1)=4 k^{2}+2 k+1$．
答案
解析
备注
