实践周数学建模论文铺地砖问题

实践周数学建模论文设计题目： 铺地砖问题姓名： 学号： 专业班级： 指导老师： 完成时间： 2011年7月8日 目录摘要3一、问题重述.4二、问题分析.4三、模型假设及符号说明.5四、模型的建立与求解.6五、模型评价与推广.8参考文献.10摘 要铺瓷砖问题是数学建模中典型的一个案例，本文利用奇偶校检法建立模型，讨论了如何用用20块矩形砖铺设形状如图1的地面（其中一块矩形砖覆盖两块方形砖），通过建模分析发现不论我们如何摆放这二十块矩形砖，都不能将上述图形的地面铺好，铺好唯一的方法是将最后一块矩形砖截成两块方砖进行铺设。关键词：铺地砖问题 奇偶校验法 图1:一、问题重述要用40 块方砖铺设图1所示的地面, 但当时商店只有长方形瓷砖，每块大小等于方形的两块，一人买了20 块长方形瓷砖，试铺这地面，结果弄来弄去始终无法完整铺好，问题：用这20 块长方形瓷砖正好铺成图1所示的地面可能性是否存在?二、问题分析本题主要利用奇偶校验法进行分析证明，在图上染上白、黑相间的颜色如图2所示,同色的具有相同的奇偶性，异色具有相反的奇偶性。如果一个是奇数，一个是偶数，则具有相反的奇偶性，长方形瓷砖显然只能覆盖具有相反奇偶性的一对方格，从图中我们可以看出，有21块黑色的方图，19块白色的方图，由已知，只有剩下两个奇偶性相反的方砖时，才可以正好铺满，但是我们发现不管我们怎么铺，在19块长方形方砖铺好后，剩下的两块方砖具有相同的奇偶性，所以无法铺上最后一块长方形地砖。图2：三、模型假设及符号说明（一）模型假设1各块方砖大小相等。2. 一块长方形方砖正好覆盖两块颜色不同大小相等的方形砖。3假定图形标记的形状如图一所示。4. 黑色方砖用1表示，白色的方砖用0表示。5对此图进行编号如图3图3： （二）符号说明i代表行，j代表列，A(ij)代表图案中所指示的固定方砖。四、 模型的建立与求解（一） 模型的建立对于以上问题，我们首先将模型建立为：我们对图好颜色的图2进行编号，得到图3.其中1（奇数）代表黑色，0（偶数）代表白色.假令一块长方形砖只能覆盖两块不同颜色的方砖，其中然后利用奇偶校验法对该问题进行接求解。在规则“1+10，1+01，0+11，0+00”下，求相邻两块不同奇偶性的方砖数值相加为1的所有组合。并把最终不能相加的为1的组合挑选出来。（二）模型求解 此地砖的铺设无非有两种方式，一种从行，一种从列。第一种，从行开始：A(12)+ A(13)=1。A(14)+ A(15)=1。 A(21)+ A(22)=1。A(23)+ A(24)=1。 A(25)+ A(26)=1。A(31)+ A(32)=1。 A(33)+ A(34)=1。A(35)+ A(36)=1。 A(27)+ A(37)=1。A(41)+ A(42)=1。 A(43)+ A(44)=1。A(45)+ A(46)=1。 A(51)+ A(52)=1。A(53)+ A(54)=1。 A(55)+ A(56)=1。A(47)+ A(57)=1。 A(61)+ A(62)=1。A(63)+ A(64)=1。 A(65)+ A(66)=1。 其中只剩下A(16)，A(67)没有组合，两者都是黑色，奇偶性相同，数值加和为2，由假设知此图案不能完全用20块方砖铺满。第二种：从列开始：A(21)+ A(31)=1。A(41)+ A(51)=1。 A(12)+ A(22)=1。A(32)+ A(42)=1。 A(52)+ A(62)=1。A(13)+ A(23)=1。 A(33)+ A(43)=1。A(53)+ A(63)=1。 A(14)+ A(24)=1。A(34)+ A(44)=1。 A(15)+ A(25)=1。A(35)+ A(45)=1。 A(55)+ A(65)=1。A(16)+ A(26)=1。 A(36)+ A(46)=1。A(56)+ A(66)=1。 A(27)+ A(37)=1。A(47)+ A(57)=1。 其中只剩下A(61)， A(67)没有进行组合，两者都是黑色，奇偶性相同，数值加和为2，由假设知此图案不能完全用20块方砖铺满。 由上述所得两种结论可以看出，无论怎么进行铺设，我们总是不能将其正好用20块长方形砖进行铺好，唯一的方法是将最后一块长方形砖平分成两块进行铺设。五、对模型的评价与推广该方案运用奇偶校验模型成功的证明了上述图案用20块长方形砖是不能正常铺设的，通过从行从列两个方面全面的证明了结论，但是模型的结构比较单一，不能借助程序进行实现，是本模型的一大遗憾。本模型属于铺设地砖模型中比特殊，较简单，基础的一个模型。在其基础山，还有另外几种普遍形式：推广1：（1）在n 行，m 列的地面如图4，去掉同一边的两个角，判断用若干块长方形瓷砖正好铺这地面可能性是否存在? 图4：不妨设去掉上面的两个角，如图4所示，如果去掉其它边的两个角，可通过旋转变成去掉上面的两个角的情形。当m，n 都为奇数时，整个方块数mn- 2也为奇数，用每块大小等于两块方形的长方形瓷砖是无法铺的。当m为偶数，不论n 为何值，每行都是偶数块，全部横铺就能铺好，因此这种情形可以用长方形瓷砖铺好。当m为奇数，n为偶数时，在左下角染上黑色，其它染上白、黑相间的颜色，如图4所示，黑格个数为mn/2白格个数为mn/2-2因此长方形瓷砖正好铺这种地面不可能。推广2: 在n 行, m 列的地面, 去掉对角的两个角如图5, 判断用若干块长方形瓷砖正好铺这地面可能性是否存在？图5：不妨设去掉左上和右下的两个角，如图5左边图形所示，如果去掉其它的两个角，可通过旋转变成图5左边图形情形。当m，n都为奇数时，整个方块数mn- 2也为奇数，用每块大小等于两块方形的长方形瓷砖是无法铺的。当m为奇数，n为偶数，把整个图分成3部分，如图5右边图形所示，第块是n- 1行，m- 1列, 每行都是偶数块，全部横铺就把第块铺好，第II块是1行m- 1列( 偶数)，横铺就把第II块铺好，第III块是1列，n-2行，全部竖铺就把第III块铺好。因此这种情形可以用长方形瓷砖铺好。当m为偶数，n为奇数，情况类似于m为奇数，n为偶数情况，可以用长方形瓷砖铺好。当m，n都为偶数时，在左下角染上黑色, 其它染上白、黑相间的颜色。如图5左边图形所示，黑格个数为mn/2，白格个数为mn/2-2，因此长方形瓷砖正好铺这种地面不可能。参考文献1 任善强, 雷鸣. 数学模型( 第二版) M . 重庆: 重庆大学出版社, 1998: 31-32.2