n*n的棋盘填上1，2，...，n^2，使任意相邻（有公共边）格子里的数字之和不大于S，求S最小值? 第1页

我们有充分的理由断言，对于任意的 ， 的最小值为 .　这里的 表示不小于 的最小整数，例如： , , .

为了便于叙述，我们需要作如下说明：在一个 的方格表中，我们从左侧起，将每两列视作一个子方格表，依次记为 , ,　…　, (任何两个子方格表都没有公共的列).　注意，若 为偶数，则每一个子方格表都恰有两列.　若 为奇数，则 是唯一的只包含了一列的子方格表(其余每个子方格表都恰包含两列).

首先，我们需要证明一个对本题而言至关重要的引理.

引理.　令 与 为正整数，且 .　在一个 的方格表中挑选 个互不相邻的方格染成红色，而后，将所有与红格相邻的方格染成蓝色.　如果

• 每一列所包含的红格均少于 个，
• 对于任意的 ， 中至少包含一个红格，

则方格表中至少有 个蓝格.

证明.　任取一个 ，设该子方格表中有 个红格.

Ⅰ.　若 只包含了方格表中的一列，则我们断言， 中至少有 个蓝格.　这是因为此时 ，若 , ，易证此结论是成立的，于是，我们可以对 进行归纳.

• 若从上至下第一个方格为红格，则第二个方格为蓝格.　这表明还有 个红格分布在剩余的 个方格之中，而 ，由归纳假设，剩余的 个方格中至少有 个蓝格，故此时 中至少有 个蓝格.
• 若从上至下第一个方格不为红格，则每一个红格的上方都有一个与之相邻的蓝格，故此时 中亦至少有 个蓝格.

Ⅱ.　若 恰包含了方格表中的两列，我们将形如" "的 的子方格表称为骨牌.　显然， 由 个骨牌组成，而每一个包含红格的骨牌也会同时包含一个蓝格，故包含红格的骨牌恰有 个.　又由于每列的红格都少于 个，故 ，这表明至少有一个骨牌不包含红格.　由此可见，必然存在两个相邻的骨牌，且它们中只有一个包含了红格，这就迫使那个不包含红格的骨牌必须包含一个蓝格.　故此时 中至少有 个蓝格.

综上可知，若 为偶数，则方格表中至少有 个蓝格.　若 为奇数，则方格表中亦有 个蓝格.　

接下来，我们证明 的最小值为 .

证明. 的验证过程是平凡的，故我们默认 .　不妨假设我们是按照降序将数字 , ,　…　, 依次填入方格表的，并且在填入数字 的那一刻，方格表中第一次有某行或某列恰被填入了 个数字(在此之前，任何一行和一列中所填的数字都少于 个)，我们把这一刻称为时刻 .

显然，在时刻 恰有 个数字被填入到方格表中，若 ，则必有某行和某列都被填入了 个数字，故 .　由此可见，若这 个数字所在的方格中有两个相邻，则 .　注意到，无论 的奇偶性如何，我们都可以通过一些简单的计算来证明 ，所以，我们不妨假设这 个数字所在的方格是互不相邻的，并且分以下三种情形来讨论.

情形ⅰ.　方格表的某行在时刻 恰被填入了 个数字，但任何一列中的数字都少于 个.　此时，我们将这 个数字所在的方格都染成红色，再将所有与红格相邻的方格都染成蓝色.　显然，方格表的每一列所包含的红格均少于 个.　而由于存在恰有 个红格的行，这意味着每一个 都恰好包含了该行中的一个红格(否则，该行中有两个相邻的红格).　由引理可知，此时至少有 个蓝格.　于是，在所有数字都被填入方格表后，至少有一个蓝格所填的数字不小于 ，而与该蓝格相邻的红格所填的数字不小于 ，故 .

情形ⅱ.　方格表的某列在时刻 恰被填入了 个数字，但任何一行中的数字都少于 个.　显然，我们只要沿主对角线翻转方格表即可将此情形变为情形ⅰ，故证明略去.

情形ⅲ.　方格表的某行和某列在时刻 都恰被填入了 个数字.　这一次，我们将所有大于 的数字所在的方格都染成红色，再将所有与红格相邻的方格都染成蓝色.　此时，方格表每一列所包含的红格均少于 个.　另一方面，由于数字 所在的行和列都各有 个红格，而 (因为 )，故必然存在互不相邻的 列，其中的每一列都至少包含一个红格，从而，每一个 都至少包含了一个红格.　由引理可知，此时至少有 个蓝格，这意味着在所有数字都被填入方格表后，至少有一个蓝格所填的数字不小于 ，而与该蓝格相邻的红格所填的数字不小于 ，故 .

最后，我们还需要构造一个 的例子.　我们可以用 来表示方格表第 行第 列方格所填的数字( )，并给出如下填数规则.　

• 若 为偶数，则 ，
• 若 为奇数，则 .

针对这种填数规则，我们可以通过一些计算来证明下面四个结论.

• 若 为偶数，则 随 的增大而减小，当 不变时， 随 的增大而减小.
• 若 为奇数，则 随 的增大而增大，当 不变时， 随 的增大而增大.
• 若 为偶数， 为奇数，则 .
• 任何两个相邻方格所填的数字之和不大于 ，且 .

前三个结论表明数字 , ,　…　, 确实都被填入到了方格表中，第四个结论表明 .