与方格表、棋盘有关的问题选讲
1、 （第32届俄罗斯奥林匹克联邦区域竞赛，十年级）
如果从3?3方格表中减去一个2?2方格表，那么剩下的图形就称为由5个方格所构成的角状形。现在要将一个8?8方格表中的每一个方格都染为3种颜色之一。称一种染色方式是好的，如果在每个由5个方格所构成的角状形中都有3种不同颜色的方格。证明，至少有6种好的染色方式。
【证明】 我们指出，在每一个角状形中都包含有一个水平的1?3方格表。我们可以将8?8方格表中的每一行方格都适当染色，使得在每一个水平的1?3方格表都包含3个颜色各不相同的方格。易知，每一行都可以有3!?6种不同的染色方式（ABCABCAB，而ABC可以有6种不同的选择方式）。又由于各行之间的染色方式完全可以互相独立地选取，所以至少有6种好的染色方式。
2、 （第41届加拿大数学奥林匹克）
给定m?n方格表，其中每个方格被染成黑色或白色的。若某个黑格的同一行左边有白色方格，且同一列上边有白色方格，则称这个黑格为“坏方格”（如图，为一个不含有“坏方格”的4?5方格表）。求不含“坏方格”的2?n方格表的数目的表达式。
【解答】由题意，第一行肯定不含有“坏方格”，下考虑第二行。 设第二行的前k个方格均为黑色，第k+1个为白色（k?n?1），此时第一行对应的前k+1个方格，每个均有2种选择，前k+1列共有2k?188种可能。
而后面的n-k-1列中，上下两个方格的组合不能为上白下黑，故第一列有3种选择：上黑下白、上黑下黑或上白下白，从而有3n?k?1种选择。
n当k=n时，也即第二行均为黑色方格时，第一行可任意选取，共2种可能。
f(n)??2k?1?3n?k?1?2n综上，
k?0n?12?3n??()k?1?2n?2?3n?2nk?03n?1
3、 （第39届加拿大数学奥林匹克）
在8?9的方格表上已经放置了6块2?1的多米诺骨牌，位置如图所示，则该棋盘上至多可以放置多少块多米诺骨牌（每块骨牌都在方格表内，且互不重叠，包含已放置的6块多米诺）？
【证明】首先将棋盘划分成五个部分，C为放置的6个多米诺覆盖的部分，B、D分别为右上角、左下角处的小方格，A是B?C?D左上方的方格的集合，E是B?C?D右下方的方格的集合。
用黑白两色交替将方格表染色：使得B为白格，则D为黑格，A中有16个白格、13个黑格，E有16个黑格、13个白格。则在A?B?D中至多可以放入14个多米诺，在B?D?E中至多可以放入14个多米诺 ，则至多可以放入14?2?6?34块多米诺。这是可以达到的，我们只需在A?D和E?B中各放14块多米诺骨牌即可。
4、 （第32届俄罗斯奥林匹克决赛，九年级）
给定一个15?15的方格表，将其中有公共边的方格称为“相邻的”。将某些相邻方格的中心用线段相连，得到一个不自交的闭折线。现知该折线关于方格表的一条对角线对称，证明：折线的长度不大于200.
【证明】折线显然与对角线相交，设A为折线的一个位于对角线上的顶点。我们来沿
着折线运动，直到首次到达折线的又一个位于对角线上的顶点B。由对称性知，如果我们由A开始朝另一方向前进，那么B也是我们首次到达的折线的另一个位于对角线上的顶点。注意此时折线已经封闭，所以折线不再经过对角线上的其余13个方格的中心。
将方格表中的方格按照国际象棋盘的方式交替染为黑色与白色，使得对角线上的方格为黑色。在我们的折线上面黑格与白格是交替出现的，所以它们的数目相等。但是，在整个方格表中黑格比白格多一个，而且对角线上的方格为黑色，既然折线不经过对角线上的13个黑格的中心，所以它必不经过另外12个白格的中心。故知，折线的长度不大于
152?13?12?200。
5、 （第29届俄罗斯奥林匹克竞赛，九年级）
能否在一张无限大的方格纸的每一个方格中都填入一个正整数，使得对任意正整数
m,n?100，纸上的任何m?n方格表中所填的数的和都可以被m?n整除？
【解答】不可能
我们来观察一个200?200的方格表A。假设它位于某个200t?200t方格表B的角上，其中t是某个不能整除方格表A中所有数之和的正整数。将图形A\\B划分为一系列尺寸为
200(t?1)?200的矩形和一个尺寸为200?200(t?1)的矩形。根据题意，每一个这种矩形
中的数的和都可以被t整除；并且方格表B中的数的和也可以被t整除，从而方格表A中的数的和可以被t整除，由此导致矛盾。
6、 （第31届俄罗斯奥林匹克决赛，九年级）
列莎将正整数1至22分别写在22?22方格表的各个方格表中（每格写有一个整数）。试问：列莎能否选择两个具有公共边或公共顶点的方格，使得写在它们之中的数的和是4的倍数？
【解答】假设列莎不能选出所需的方格。我们将每个数都换成其被4除的余数，于是方格表中就有0，1，2和3个121个。将方格表划分为121个2?2的正方形。由于列莎不能选出所需的方格，所以在每个2?2正方形中都至多有1个0，也至多有1个2。由于0和2的个数与这种正方形的个数相同，所以在每个这种正方形中都刚好有1个0和1个2。然而在我们的假设之下，每个2?2正方形中剩下的两个方格中或者都只能放1，或者都只能放3，从而分别都只能放入偶数个1和3，此与它们各有121个的事实相矛盾。
7、 （第25届俄罗斯奥林匹克竞赛，九年级）
2将边长为n的正三角形的每一边都n等分，通过各个分点 作边的平行线，将它分为一系列边长为1的小正方形（右图所示的是n?5的情形）。试问，最多可以标出多少条以这些小三角形的顶点为端点的长度为1的线段，使得找不到这样的小三角形，它的三条边都是被标出的线段？
【解答】n(n?1) 事实上，一共有
3n(n?1)条以这些小三角形的顶点为端点2的长度为1的线段。由于每个小三角形的三条边都是分别平行于大三角形的三条边的，所以平行于大三角形的两条边的所有线段不能形成任何一个小三角形，因此可以标出
23(n(n?1))?n(n?1)条长度为1的线段，而不至于出现三条32边都是被标出的线段的小正三角形。
下面来证明，不能标出更多条线段。
如右图所示，涂黑所有顶点朝上的小正三角形。这些小三角形的周界中包含了所有长度为1的线段，并且每条这样的线段都恰好属于一个小三角形。显然每个小三角形中都至多可以标出两条边，所以一共只能标出所有边的
2。 3
8、 （第29届俄罗斯奥林匹克竞赛，十年级）
试找出最大的正整数N，使得无论怎样将正整数1至400填入20?20方格表的各个方 格，都能在同一行或同一列中找到两个数，它们的差不小于N。
【解答】209
首先来举例说明N?209。用正中的竖直直线将方格表分成两个20?10的方格表。将1至100逐行按递增顺序填入左表中（即在第一行中自左至右一次填入1至10，在第二行中自左至右依次填入11至20，如此等等）。再在右表中按同样的原则填入201至400。这样一来，在每一行中所填之数的最大差都不超过210?1?209；在每一列中所填之数的最大差都不超过191?1?190。所以N?209。
再证N不能小于209。我们来观察两个子集
M1?{1,2,?,91}和M2?{300,301,?,400}。
将凡是填有M1中的数的行和列都染为红色；将凡是填有M2中的数的行和列都染为蓝色。往证红色的行和列的数目不会小于20，而蓝色的行和列的数目不会小于21。这样一来，那么就有某一行或某一列既被染为红色，又被染为蓝色，从而其中必有两个数的差不小于300?91?209。
设有i行和j列被染为红色。于是M1中的元素全都位于这些行与这些列的相交处，所以ij?91。从而i?j?2。同理，被染为蓝色的行数与列数之和ij?291?19i?j?2ij?2101?20。
9、 （第34届俄罗斯数学奥林匹克，十年级）
一个n?n的方格表的n列从左到右分别称为1列，2列，?，n列。将1~n这n个正整数填入方格表中，使得表中的每一行和每一列都含有n个不同的数。若方格表中一个方格所填的数大于这个方格所在列的列数，则称这个方格是“好的”。请找出所有正整数n，使得可以在方格表中按上面的要求填上数且满足每行中好的方格的个数都相等。
【解答】首先找出好的方格的总数。
第1列中有n?1个（除了填上数1的方格外都是好的），第2列中有n?2个（除了填上数1和2的放格外都是好的），??第n列没有好格。故好方格共有
(n?1)?(n?2)???1?n(n?1)。 2n?1因此，每行有好方格的个数为，由此，n为奇数。
2当n?2k?1为奇数时，将位于第i行和第j列的交处的方格中填上数字aj，
?n?(j?i),j?i。 aj???i?j, j?i