问题3：能否在 的方格表 的各个空格中，分别填写 这三个数中的任一个，使得每行，每列及对角线 的各个数的和都不相同？为什么？

分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为 个；而用 填入表格，每行,列及对角线都是 个数， 个数的和最小为 ，最大为 ，共有 种；利用鸽笼原理， 个“鸽”放入 个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以题目中的要求，无法实现。

思考题：在一个边长为 的正三角形内，若要彼此间距离大于  ，最多能找到几个点？

1.2 “奇偶校验”方法

    所谓 “奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。

问题1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只剩下 个方格（如图1—2）。若你还有 块骨牌，每块骨牌的大小为 方格。试说明用互不重叠的骨牌完全覆盖住这张残缺的棋盘是不可能的。

分析：关键是对图1—2的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两个方格，必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为 和 ；因此不同能用 块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。

问题2（菱形十二面体上的H路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过各顶点恰好一次，该问题被称为Hamilton路径问题。

分析：我们注意到菱形十二面体每个顶点的度或者为 或者为 ，所谓顶点的度是指通过这一顶点的棱数，如图1—3；且每 度顶点刚好与 个 度顶点相连，而每个 度顶点刚好与 个 度 顶点相连。因此一个Hamilton路径必是 度与 度顶点交错，故若存在Hamilton  路径，则 度顶点个数，与 度顶点个数要么相等，要么相差 。用奇偶校验法 度顶点为奇数顶点， 度顶点为偶数顶点，奇偶配对，最多只能余 个；而事实上菱形十二面体中，有 度顶点 个， 度顶点 个；可得结论，菱形十二面体中不存在Hamilton 路径.

思考题：1、设一所监狱有 间囚室，其排列类似 棋盘，看守长告诉关押在一个角落里的囚犯，只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他将获释，问囚犯能否获得自由？

2、某班有 个学生，坐成 行 列，每个坐位的前后左右的坐位叫做它的邻座，要让 个学生都换到他的邻座上去，问是否有这种调换位置的方案？

1.3 自然数的因子个数与狱吏问题

令  为自然数 的因子个数，则 有的为奇数，有的为偶数，见下表:          

我们发现这样一个规律，当且仅当 为完全平方数时, 为奇数；这是因为 的因子是成对出现的,也即 ; 只有 为完全平方数, 才会出现 的情形， 才为奇数。

下面我们利用上述结论研究一个有趣的问题.

狱吏问题：某王国对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次按所定规则转动门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？

问题分析： 牢房的锁最后是打开的，则该牢房的锁要被转动奇数次；如果把n间牢房用 编号，则第k间牢房被转动的次数，取决于k是否为 整除，也即k的因子个数，利用自然数因子个数定理，我们得到结论：只有编号为完全平方数的牢房门仍是开着的。

1．4 相识问题

问题：在6人的集会上，总会有3人互相认识或互相不认识。

分析：设6人为 ;下面分二种情形，1. 至多只和两个人相识，不妨设 不认识 ；若 互相都认识，则结论成立，若 中有两人不认识，则加上 ，有三人互不相识. 2．  至少和三人相识，不妨设  认识 ；若 互不相识结论成立，若 有两人相识，加上  则有三人互相认识 。这样，我们就证明了结论成立,这个问题的讨论，我们也可以采用几何模似的方法，如图1—4