初等数学方法建模 每列及对角线AC,BD的各个数的和都不相同?为什么? 分析:若从考虑填法的种类入手,情况太复杂:这里我们注意到,方格表中行,列及对角线的总数为18 个;而用1,2,3填入表格,每行,列及对角线都是8个数,8个数的和最小为8,最大为24,共有24-8+1=17 种:利用鸽笼原理,18个“鸽”放入17个“鸽笼”,必有两个在一个“鸽笼”,也即必有两个和相同。所以 题目中的要求,无法实现。 思考题:在一个边长为1的正三角形内,若要彼此间距离大于,最多能找到几个点? 12“奇偶校验”方法 所谓“奇偶校验”,即是如果两个数都是奇数或偶数,则称这两个数具有相同的奇偶性:若一个数是 奇数,另一个数是偶数,则称具有相反的奇偶性。在组合问题中,经常使用“奇偶校验”考虑配对问题 问题1(棋盘问题):假设你有一张普通的国际象棋盘,一组对角上的两个方格被切掉,这样棋盘上只 剩下62个方格(如图1—2)。若你还有31块骨牌,每块骨牌的大小为1×2方格。试说明用互不重叠的骨牌 完全覆盖住这张残缺的棋盘是不可能的 分析:关键是对图1—2的棋盘进行黑白着色,使得相邻的两个方格有不同的颜色:用一块骨牌覆盖两 个方格,必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格,白格个数,分别为30和32:因此 不同能用31块骨牌盖住这张残缺的棋盘。用奇偶校验法,我们可以把黑色方格看成奇数方格,白色方格看 成偶数方格;因为奇偶个数不同,所以不能进行奇偶配对,故题中要求的作法是不可能实现的 团团 图1-2 图1-3 问题2(菱形十二面体上的H路径问题):沿一菱形十二面体各棱行走,要寻找一条这样的路径它通过 各顶点恰好一次,该问题被称为 Hamilton路径问题 分析:我们注意到菱形十二面体每个顶点的度或者为3或者为4,所谓顶点的度是指通过这一顶点的棱 数,如图1-3:且每3度顶点刚好与3个4度顶点相连,而每个4度顶点刚好与4个3度顶点相连。因此 一个 Hamilton路径必是3度与4度顶点交错,故若存在 Hamilton路径,则3度顶点个数,与4度顶点个数 要么相等,要么相差l。用奇偶校验法3度顶点为奇数顶点,4度顶点为偶数顶点,奇偶配对,最多只能余 1个:而事实上菱形十二面体中,有3度顶点8个,4度顶点6个;可得结论,菱形十二面体中不存在 Hamilton 路径 思考题:1、设一所监狱有64间囚室,其排列类似8×8棋盘,看守长告诉关押在一个角落里的囚犯, 只要他能够不重复地通过每间囚室到达对角的囚室(所有相邻囚室间都有门相通),他将获释, 问囚犯能否获得自由? 2、某班有49个学生,坐成7行7列,每个坐位的前后左右的坐位叫做它的邻座,要让49个初等数学方法建模 2 每列及对角线 AC, BD 的各个数的和都不相同？为什么？ 分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为 18 个；而用 1,2,3 填入表格，每行,列及对角线都是 8 个数， 8 个数的和最小为 8 ，最大为 24 ，共有 24−8+1=17 种；利用鸽笼原理， 18 个“鸽”放入 17 个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以 题目中的要求，无法实现。 思考题：在一个边长为 1 的正三角形内，若要彼此间距离大于 n 1 ，最多能找到几个点？ 1.2 “奇偶校验”方法 所谓 “奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是 奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。 问题 1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只 剩下 62 个方格（如图 1—2）。若你还有 31 块骨牌，每块骨牌的大小为 1 2 方格。试说明用互不重叠的骨牌 完全覆盖住这张残缺的棋盘是不可能的。 分析：关键是对图 1—2 的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两 个方格，必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为 30 和 32 ；因此 不同能用 31 块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看 成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。 问题 2（菱形十二面体上的 H 路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过 各顶点恰好一次，该问题被称为 Hamilton 路径问题。 分析：我们注意到菱形十二面体每个顶点的度或者为 3 或者为 4 ，所谓顶点的度是指通过这一顶点的棱 数，如图 1—3；且每 3 度顶点刚好与 3 个 4 度顶点相连，而每个 4 度顶点刚好与 4 个 3 度 顶点相连。因此 一个 Hamilton 路径必是 3 度与 4 度顶点交错，故若存在 Hamilton 路径，则 3 度顶点个数，与 4 度顶点个数 要么相等，要么相差 1 。用奇偶校验法 3 度顶点为奇数顶点， 4 度顶点为偶数顶点，奇偶配对，最多只能余 1 个；而事实上菱形十二面体中，有 3 度顶点 8 个， 4 度顶点 6 个；可得结论，菱形十二面体中不存在 Hamilton 路径. 思考题：1、设一所监狱有 64 间囚室，其排列类似 88 棋盘，看守长告诉关押在一个角落里的囚犯， 只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他将获释， 问囚犯能否获得自由？ 2、某班有 49 个学生，坐成 7 行 7 列，每个坐位的前后左右的坐位叫做它的邻座，要让 49 个 图 1-2 图 1-3