则不难验证此时第2i行的好方格为前i?1个和从第2i到k?i个，而在2i?1行的好方格为前i?1个和从第2i?1到k?i?1个，每一行恰有k个好方格。
10、 （第36届俄罗斯数学奥林匹克，十年级）
100?100的方格表中的每个方格中有一个正整数。若一个矩形（由若干个方格组成）所含方格中的各数之和是17的倍数，则称其为“好的”。我们可以对方格表中某些好的矩形所含各方格同时染色，且每个方格至多染一次。已知对任意一个如上数表都可按照上面的规则将其中至少d个方格染色。求d的最大值。
【解答】dmax?9744?1002?162
首先证明一个引理。
引理 1?n方格表的每个方格中有一个正整数，则至少可以将n?16个方格染色。 证明 对n用数学归纳法。 当n?16时，结论显然成立。
不妨设n?k?17，且对于小于k的一切n，结论都成立。
假设左边17个方格中的数分别为a1,a2,?,a17，则在0,a1,a1?a2,?,a1?a2???a17中存在两个数使得它们的差被17整除，即17|(ai?ai?1???aj)。
于是，从第i个到第j个方格构成一个好矩形A。从表格中将A去掉，得到一个
1?(k?(j?i?1))的新表格，由归纳假设，新表格除至多16个方格外，还可表为两两内部
不交的好矩形的并。这些好矩形如果没有同时含原表中第i?1和j?1个方格的，则它们也是原表格中好矩形；如果有一个好矩形同时含原表格中的第i?1个和第j?1个方格，则它与A的并构成原表格中的好矩形。无论哪种情况，都说明当n?k时结论成立。 下面证明：可以对表格中至少9744个方格染色。
将每列看成一个大格，其中的数为该列各数之和。由引理知，除了至多16列之外，表格可以表示若干个高度为100的好矩形之并。对剩下的每列都可以利用引理得到每列除了至多16个方格外都可以染色。于是，整个表格至多有16?256没被染色。
2下面给出一个至少有256个方格不被染色的例子。
在表格中的一个16?16的子表B的每个方格中填1，其余每个方格填上17，则B中方格都不可能被染色。
11、 （第34届俄罗斯数学奥林匹克，十一年级）
是否可以将51~150这100个整数放在10?10的数表中，使得对任意两个相邻小方格（即
它们有公共边）中的数a,b，方程x?ax?b?0和x?bx?a?0中至少有一个有两个整数根。
【解答】不可以。
假设有一种方法满足要求。设77?a?150是一个质数，b是一个与a相邻的数。
若方程x?bx?a?0有两个整数根，则由韦达定理，它们的积等于a，它们的和等于b?0。这表明1、a是它的根，且b?1?a。
若方程x?ax?b?0有两个整数根x1,x2，则x1?x2?a,x1x2?b；
若还有x1,x2?2，则b?x1(a?x1)?2(a?2)，这推出b?2a?4?150，矛盾，故1是方程的根，b?1?(a?1)?a?1。
上述讨论表明，对于这样的质数a，只有两个数可以和它相邻，即b?a?1，b?a?1。
故a只能位于表格中的角上。但在77与150之间的质数多于4个（如79，83，89，97，101），它们不可能都位于角上。矛盾。
12、 （第29届美国数学奥林匹克）
在1000?1000棋盘中有几个小方格被染色。求n的最小值，使得一定有3个染色方格的连线构成直角三角形，且直角边与棋盘的边框平行。
【解答】我们来证最小的n值是1999.
2222事实上，n?1999，因为我们可以染1998个方格使得不存在直角三角形：给第一行和第一列的方格都染色（除了它们的公共方格）。假设现在部分方格被染色并且不存在直角三角形。
若某一行（或列）中染色方格多于一个，则称其为重行（或重列），反之称其为轻行（或轻列）。
我们的假设意味着没有一个染色方格同处于重行和重列。
如果没有重行，那么每一行至多有一个染色方格，从而总共染色方格数不超过1000。. 如果没有重列，结果同上。
如果有一个重行和一个重列，那么由初步观察可知，重行（或重列）上的染色方格一定在轻列（或轻行）上。
所以染色方格的数目不超过轻行和轻列的数目，
即2?(1000?1)?1998。
从而我们断定1999是满足题意的最小n值。
13、
（第26届俄罗斯奥林匹克决赛，十一年级）
100?100的方格表被染为4种颜色，每一行与每一列中都刚好有每种颜色的方格各25个。证明，可以找到两行与两列，位于它们相交处的4个方格为4种不同颜色。
【证明】为方便起见，将4种颜色分别称为1至4号色。
假设不然，那么任何两行任何两列相交处得4个方格中都有两个方格同色。我们将同一行中的两个异色方格称为一个“横对”，同一列中的两个异色方格称为一个“竖对”；同一行中的两个同色方格称为一对“横向重合”，同一列中的两个同色方格称为一对“纵向重合”。将异色方格对按颜色分为6种类型：{1,2}、{1,3}、{1,4}、{2,3}、{2,4}、{3,4}。
我们来考察表中的任意两行，并证明在它们中，至少有25对纵向重合。首先，由我们的假设可知，由这两行中的方格构成的任何两个竖对中都有颜色相同的方格。于是不难看出，这两行中的竖对至多有两种不同类型，或者都含有某个同一种颜色（例如，1号色）；或者皆为形如{1,2}、{1,3}、{2,3}的竖对（当然也可以是另外三种颜色构成的对子）。下面分别考察这两种情况。
如果所有的竖对中都含有1号色，那么异色对子的总数不会超过这两行中的1号色方格的总数，即50。这就表明，这两行中至少有50对纵向重合。
再考虑所有的竖对皆为{1,2}、{1,3}、{2,3}的情形。此时，这两行中的所有的4号色的方格皆形成纵向重合，从而两行中至少有25对纵向重合。
这样，我们便证明了，任何两行中都至少有25对纵向重合。同理可证，任何两列中都
2至少有25对横向重合。如此一来，在我们的方格表中，共有不少于2?C100?25?25?99?100对重合。但由于每一行与每一列中都刚好有每种颜色的方格各25个，重合的对子数目为
2200?C25?4?24?1002。由于25?99?24?100，所以产生矛盾。因而，必有两行与两列，
位于它们相交处的4个方格为4种不同颜色。
14、 （第31届俄罗斯数学奥林匹克，十年级）
在8?8的国际象棋棋盘上的16个方格中各放有一枚棋子车。试问，它们之中至少有多少“对”棋子可以相互搏杀（同在一行或同在一列里且它们之间没有其他棋子的一对车可以相互搏杀？
【解答】16对。
我们指出，如果一行中有a枚棋子车，那么该行中就有a?1对棋子可以相互搏杀。因此水平方向可以相互搏杀的棋子不会少于8对。同理，竖直方向可以相互搏杀的棋子也不会少于8对。
存在恰有16对棋子可以相互搏杀的摆法，例如可以把所有棋子都放到两条主对角线上（左上右下，右上左下）。 15、 （第30届俄罗斯数学奥林匹克，十一年级）
有一个9?2004的方格表，在它的方格里边把正整数1到2004各填9次，并且在每一列中所填的数之差都不大于3。试求第一行数的和的最小可能值。
2【解答】C2003?1?2005004.
考察9?n的方格表，在它的方格里边把正整数1到n各填9次，并且在每一列中所填
2的数之差都不大于3.我们用数学归纳法来证明：第一行数的和不小于Cn?1?1。
当n?4时，结论显然。因为每个方格中的数都不小于1，而且当n?4时，有
2n?Cn?1?1。
下面来作归纳过渡。如有必要，可以通过调整列的顺序，使得第一行中的数按非降顺序排列。所以可以假设第一行中的数已经按非降顺序排列。以Si表示第一行中不小于i的数的个数，并令Di?n?Si，于是S1?n,D1?0。而且第一行数的和就等于
S?S1?S2???Sn。改写该式，可得
S?(n?D1)?(n?D2)???(n?Dn)?n(n?3)?(D1?D2???Dn?3)。
如果对任何i?n?3，都有Di?i?1，则有
n2?3n?4S?n(n?3)?(0?3?4???(n?2))?，
2即为所证。假设存在某个k?n?3，使得Dk?k?2。我们指出，此时必有k?2，因此k?2?4。由于第一行中至少有k?2个数小于k，因此该表中的前k?2列中的数都不超过k?2。这就表明，所有这样的数全都在前k?2列中，因此后面各列中的数都不小于k?3。现在将整个表分成两部分：前k?2列为第一部分，其余的为第二部分。由于
n?1?k?2?4，所以第一部分中第一行中的数的和不小于Ck2?1?1。如果将第二部分中的
每个数都减去k?2，则得到一个具有n?(k?2)?1列的满足题意的方格表。于是由归纳假
2设知：它的第一行数的和不小于(k?2)(n?k?2)?Cn将上述两个估计值相加，即?k?3?1。222得S?Ck?1?1?(k?2)(n?k?2)?Cn?k?3?1?Cn?1?3，这比所要证明的结论还要强。
我们再给出一个可以达到最小可能值的例子。
16、 （第28届俄罗斯数学奥林匹克，九年级）
在国际象棋棋盘上放有8枚棋子“车”，它们不能相互搏杀。证明，其中必有某两对棋子之间的距离相等（两枚棋子之间的距离是指它们所在的方格的中心之间的距离）。
【解答】考察分布在相邻列中的7对车。各对车的纵坐标的差都在1与7之间。（注：由题意，这些车不能互相搏杀，所以它们不能处于同行或同列位置，因此每行每列都恰有一枚车，所以相邻列的车有7对，各列车的纵坐标之差不能为0）因此，或者有两对车的纵坐标的差相同，此时这两对车的距离已经相同（因为它们的横坐标的差都是1）；或者这7对车的纵坐标的差为1到7一样一个。特别地，其中有一对车（称为A）的纵坐标的差为2，而它们的横坐标的差为1。同理，在分布在相邻行的7对“车”中，或者可以找到两对“车”的横坐标的差相同，此时这两对“车”的距离已经相同；或者必有一对车（称为B）的横坐标的差为2，而它们的纵坐标的差为1。于是，“对A”与“对B”有相同的距离。