实验三数字填图问题

第三周数字填图问题一、问题背景和实验目的数字填图问题是数学问题的一种趣味形式早在19世纪后半期，一些数学家就在报刊中大量使用数字填图游戏和字谜游戏等，目的是使业余爱好者也能通过简单的形式去认识、理解和琢磨深奥的数学问题，这些问题中甚至包括困惑了世间智者350多年、于1994年才刚刚被证明了的“费马大定理”100多年来，数字填图问题对数学界所起的作用是不言而喻的大家都知道，数学问题一般都经过严格的逻辑证明才得以解决而逻辑证明是指从一些公理出发，经过逻辑推理来证明问题但随着20世纪40年代以来计算机的诞生和发展，计算机改变了整个世界，计算机已在各个领域发挥作用，并取得了许多重大进展于是，能否用计算机来证明数学问题便成了大家关心的话题所谓计算机证明是指充分发挥计算机计算速度快和会“推理”的特点，用计算机程序模拟解题或进行穷举检验，最后得到问题的解几乎所有的数学家对计算机证明持保留态度，因为他们相信，只有逻辑证明才是真正可靠的但“四色问题”的证明，又使他们感到困惑，因为“四色问题”的证明实际上是一个计算机证明能否用计算机来证明数学问题的争论可能会持续一个相当长的时间，本实验旨在通过生活中几个常见的数字填图问题的探究，谈谈这类问题的逻辑推理解法和计算机解法二、 相关函数（命令）简介1cputime命令：记录执行本命令时的Matlab时钟的时间(秒)2tic命令：开始计时3toc命令：结束计时4disp(x)：输出矩阵 xx的各项应为字符，所以在输出时要进行转化相关的命令有：num2str( )：把数值转化为字符；mat2str( )：把矩阵转化为字符三、 实验内容让我们先从一个简单的问题出发来谈谈数字填图问题的两种解法然后通过几个稍复杂问题的探究，从中展示逻辑推理的严谨以及计算机解法的魅力，启迪我们去解决更复杂的数学问题注：在本实验中，将表达式 abc 理解为 ，即 100*a+10*b+c，其余类似，不另加说明(一)、一个简单的问题及其解答问题一：在图 1 的几个加法等式中，每个表示一个非零数字，任意两个数字都不相同，问有多少个解?图1【逻辑解法】 为简洁起见，将它的 3 个式子记作： a + b = c，d + e = f，g + h = i 0，若问题有解，则显然有 i = 1，且(a + b) + (d + e) + (g + h) = c + f + i 10，故 45 = (a + b + c) + (d + e + f) + (g + h + i) = 2 (c + f) + i 11，即 c + f = 17，故 c = 8，f = 9 或 c = 9，f = 8考虑到 a i 互不相同，当要求 a b，d e，g h 时，有如下 4 组解（见下表）： 注：本问题实际上仅有 2 个解是本质的，即表中的第 2、3 行，第 4、5 行所代表的解仅是位置不同而已如不要求 a b，d e，g h，则解的个数是 个【计算机解法】为验证此结果，可用 Mathematica、Matlab、Turbo C 等软件进行模拟解题，充分利用计算机运算速度快的特点进行穷举法检验实践表明本问题解的情况恰如上所述用 Matlab 实现的程序清单可参见附录1，这一算法比较慢（一个更慢的算法参见附录1B，试分析其原因），而一个提速的程序清单可参见附录2，Turbo C 程序清单可参见附录3，而Mathematica程序清单可参见附录4【评论】这个问题的逻辑解法十分简单，或许根本不需要计算机解法，但所用程序有一定的代表性，稍加修改即可解决一系列问题，这点可从下面的问题中看到(二)、几个较复杂的问题及其解答问题二：在图 2 的 4 个算式中，每个表示一个非零数字，任意两个数字都不相同，问 (A)、(B)、(C) 和 (D) 这 4 种情形分别有多少个解?图2讨论：显然，情形 (C) 无解情形 (D) 与 情形 (C) 实际上是同一个问题，因此也无解情形 (B) 与 情形 (A) 实际上也是同一个问题我们先讨论情形 (A) 的解的个数【逻辑解法】为简洁起见，将此竖式记作：abc + def = ghi，即 ，其中 a i 代表 1 9 这 9 个互不相同的非零数字据九余数性质可知，两个“加数”中的六个数字之和被 9 除的余数应等于“和数”中的三个数字之和被 9 除的余数又这两个“加数”与“和数”中共九个数字正好是1，2， ，9，它们的和为 45，被 9 除的余数是 0，易见“和数”的三个数字之和被 9 除的余数必为 0，也即：“和数”是 9 的倍数注意到题设可知，“和数”的三个数字之和必定为：g + h + i = 9 或 g + h + i = 18 考虑 g + h + i = 9 的情形(1) 首先必定有 g 3，否则 a，d 最小为 1，2，b，e 最小为 4，5，c，f 最小为 6，7，此时已有 abc + def 400，与 g 3 矛盾故 g 4；另外，g 6 为显然；(2) 若g = 4，由 g + h + i = 9，h + i = 5，故 h，i 最小为 1，4 或 2，3；但已有 g = 4，故 h，i 为 2，3，而 a，d 最小为 1，4，从而g 5，与 g = 4 矛盾；(3) 若g = 5，由 g + h + i = 9，h + i = 4，故 h，i 为 1，3；而 a，d 最小为 2，4，从而g 6，与 g = 5 矛盾；(4) 若 g = 6，由 g + h + i = 9，h + i = 3，故 h，i 为 1，2；而 a，d 最小为 3，4，从而g 7，与 g = 6 矛盾综上所述，g + h + i = 9 的情形下问题无解 考虑 g + h + i = 18 的情形由于 g 4（理由同上），以下按 g = 9，8，4 的顺序分类讨论：(1) g = 9，则 h + i = 9由于 a i 互不相同，于是 g，h，i 的可能的取值见下表： 对这些竖式有序地交换两个加数的百位数、十位数和个位数，可得到每个类型的 8(=) 个不同竖式 (解)，小计有解 12 8 = 96 个注意：表中的第 2、5、6、9 列为容易造成失解的地方，要特别留意完全类似地有如下一系列过程：(2) g = 8，则 h + i = 10仿(1)，小计有解 108=80 个，解例见下表：(3) g = 7，则 h + i = 11小计有解 58=40 个，解例见下表：(4) g = 6，则 h + i = 12小计有解 68=48 个，解例见下表：(5) g = 5，则 h + i = 13小计有解 58=40 个，解例见下表：(6) g = 4，则 h + i = 14小计有解 48=32 个，解例见下表：结论：本问题的解的个数为：(12 + 10 + 5 + 6 + 5 + 4) 8 = 42 8 = 336注：如不考虑两个加数的上下位置关系，则总的解的个数为：42 8/2 = 168由于情形 (B) 与 情形 (A) 是同一个问题，故解的个数也为：42 8 = 336【计算机解法】为验证此结果，仍用 Matlab、Mathematica、Turbo C 编程进行模拟解题，充分利用计算机运算速度快的特点进行穷举法检验实践表明本问题有且只有 336 个不同竖式（解），而 Matlab 程序清单可参见附录5，你可发现它与附录 1 十分相似【评论】这个问题的逻辑解法较复杂，而计算机解法则是如此的简单快捷，运行整个程序不要 1 分钟实际上非常复杂的“四色问题”的证明也是这样：对 1482 种有代表性地图的分析，若依靠人工去做，可能要几十年甚至上百年的时间，而用计算机，只要 1200 小时即告完成这还是 70 年计算机的计算水平，若用现在的计算机，计算时间应该不会超过一天!问题三：在图 3 的加法算式中，每个表示一个非零数字，任意两个数字都不相同，问可有多少个解?【逻辑解法】为简洁起见，将此竖式记作：a + bc + def = ghi 或 ，其中 a i 代表 1 9 这 9 个互不相同的非零数字据九余数性质并采用完全类似问题二的讨论可知，“和数”的三个数字之和必定为：g + h + i = 9 或 g + h + i = 18同时，g 1，否则 d = 1；另外 g d，从而 g = d + 1由于 9 g 2，以下按 g = 9，8，7， ，2 的顺序分类讨论：(0) g = 9，d = 8则 h + i = 9由于 a i 互不相同，于是 g，h，i 的可能的取值为（见下表）： 图3小计有解 0 个(1) g = 8，d = 7则 h + i = 1(不可能，舍去) 或 h+i=10由于 a i 互不相同，于是g，h，i 的可能的取值为(见下表)： 对这些竖式有序地交换三个加数的个位数、两个加数的十位数，可得到每个类型的 12 个不同竖式 (解)，小计有解 212=24 个完全类似地有如下一系列过程：(2) g = 7，d = 6则 h + i = 2(不可能，舍去) 或 h+i=11仿(1)，小计有解 212=24 个(3) g = 6，d = 5则 h + i = 3 或 h + i = 12有解 112=12 个，解例见下表： (4) g = 5，d = 4则 h + i = 4 或 h + i = 13有解 312=36 个，解例见下表： (5) g = 4，d = 3则 h + i = 5 或 h + i = 14有解 2 12 = 24 个，解例见下表： (6) g = 3，d = 2则 h + i = 6 或 h + i = 15有解 2 12 = 24 个，解例见下表： (7) g = 2，d = 1则 h + i = 7 或 h + i = 16有解 2 12 = 24 个，解例见下表： 结论：本问题的解的个数为：(2 + 2 + 1 + 3 + 2 + 2 + 2) 12 = 168【计算机解法】让我们再尝试计算机解法仍用 Matlab、Mathematica、Turbo C 编程进行穷举法验证，程序清单类似于附录1附录5，不再另附运行结果表明本问题的确有且只有 168 个不同竖式（解），要说明的是：该程序在一般的计算机上运行一次也只需不到 1 分钟【评论】也许有人会说，你的问题还仅是一个有穷的问题，象“费马大定理”这样的无穷问题，你的计算机就无能为力了! 情况或许是这样但应该注意到：非常复杂的“四色问题”也是一个无穷问题，但妙就妙在有人能将它们缩小到 1482 种有代表性地图以内，从而成为一个有穷的问题! 至此，对于计算机解题的作用恐怕再不能视而不见了! 下面的两个问题也是成功地运用计算机解题的的一些典型例子，而至少到目前为止还没有看到它们的推理解法. 问题四：图 4 的加法等式是：两个真分数之和等于第三个真分数，每个表示一个不为 0 的数字，任意两个数字都不相同比如：，试找出所有可能的解图4【计算机解法】本问题利用计算机程序已找到解答，共有 10 个解解答请参见：数学教学（华东师范大学）1994 年第 5 期【评论】程序如何编? 看起来问题似乎很简单，只要将附录1附录5 稍加修改即可例如可利用附录 6 的 Matlab 程序进行计算但实际情况让我们大吃一惊：用 Matlab 程序居然只有 6 个解！还有 4 个解到哪里去了？用 Turbo C 程序编写出的类似的程序居然只有 7（或9）个解！还有 3（或1）个解到哪里去了？还有人用 Turbo C 程序编写出的类似的程序，却居然得到了 11 个“解”！这个多出的 1 个“解”是哪里来的？类似的问题还会发生在本实验的“四、自己动手”的第 6 题中，用不同的语言编写出的类似程序，其运行结果居然差距很大，你能明白其中的道理吗？根据观察，可能是浮点问题，也可能是整数的上界问题，或别的什么原因具体什么原因，留作思考题问题五：图 5 的加法等式是：两个假分数之和等于第三个假分数，每个表示一个不为 0 的数字，任意两个数字都不相同试找出所有可能的解图5【计算机解法】本问题利用计算机程序也已找到解答，共有41个解同样只要将附录1 5的程序稍加修改即可(三)、小结数字填图问题是一种活泼的、变形的数学问题，逻辑推理是这类问题的一般解法但也有若干数字填图问题要找到这样的逻辑推理解法是非常地困难，而采用计算机解法则轻而易举问题一和问题二就是这样的例子至于问题四和问题五则只能给出计算机解法尽管数学家们很难接受计算机解法，因为他们担心计算机会出错（尽管这种出错的概率几乎为零!），更重要的是他们坚信逻辑证明是解答这类问题的根本方法但上述事实证明计算机解法也是十分有效的另一个公认的例子是“四色问题”，它的证明实际上就是一个计算机证明关于这个问题的争论可能会有一个相当长的时间不管将来的结论如何，但计算机证明 (解题) 毕竟代表将来数学问题解决的一个方向就象安德鲁怀尔斯 (Andrew Wiles) 突发灵感地把“伊娃沙娃理论”和“科利瓦金弗莱切方法”结合在一起可以完美地互相补足，以致最终证明了“费马大定理”一样，未来的数学家或许会让“逻辑证明”和“计算机证明”也完美结合，从而解决更多的数学问题注；西蒙辛格英，1998 年费马大定理一个困惑了世间智者 358 年的谜，薛密译，上海译文出版社四、 自己动手1一道竞赛题（以下称“原问题”）1998 年 4 月香港数理教育学会主办的初中数学竞赛有这样一道试题：在下面的加法算式中，每个表示一个数字，任意两个数字都不相同，那么 A 与 B 的乘积的最大值是多少?解答：最大值是 15你能给出逻辑推理解法并用计算机加以验证吗? 由上述问题引伸出的三个问题： 2满足原问题题意的不同的加法算式（竖式）共有多少个?本问题有 60 个不同竖式（解）试给出逻辑推理解法并用计算机加以验证原竞赛题是针对初中生而设计的，故问题的难度被大大降低了本练习已有一定难度不可否认，逻辑推理是解决问题的重要途径，而计算机模拟解题在其中所起的作用也是不言而喻的我们可以将练习 2 一般化，你将发现计算机模拟解题的有效性和重要性3如果在原问题中删除条件：“任意两个数字都不相同”，则满足题意的不同的加法算式（竖式）共有多少个?本问题实际上是一个有约束条件的全排列问题本问题的答案是：48195 个! 这真是一个神奇的数值要得到这个数值应该说是有一定难度的试给出逻辑推理解法并用计算机加以验证注：假如在本问题中允许三个“加数”与“和数”均可以由数字 0 作为开头，去掉“任意两个数字都不相同”这个条件限制，本问题则变成一个真正的全排列问题在 a + bc + def = ghij 中，“和数”ghij 是被动的由 a，b，c，d，e，f 0，1，2，3，4，5，6，7，8，9，此时本问题有解 106 个练习 3 是利用计算机模拟解题的真正代表，可以说计算机模拟解题能力在某些方面确已达到了逻辑推理解题的能力而以下的练习 4 将把练习 2 的难度进一步加大你将发现运用计算机模拟解题在某些方面甚至已超过运用逻辑推理解题这个问题是：4假如违反常规，允许三个“加数”与“和数”均可以由数字 0 作为开头，保留条件：“任意两个数字都不相同”，则满足原问题题意的不同的加法算式（竖式）共有多少个?本问题共有 228 个解，即在练习 2 有 60 个不同竖式（解）的基础上再增加 168 个解试给出逻辑推理解法并用计算机加以验证分析和观察：练习 4 的结论与本实验中的“问题三”的结论是否有一定的联系? 有何联系?5验证本实验中的“问题四”、“问题五”的结论能否给出相应的推理解法? 答案是：非常困难! 不妨一试你是否发现运用计算机模拟解决本问题，已超过运用逻辑推理解决本问题?6设A J表示十个互不相同的数字，问：方程（注意： 组成分数的四个数的第一位数字不能为0）共有多少个解？答案是110个? 是118个? 是其它的数字？为什么？五、附录附录1 (fulu1.m)：tic;n=0;for a=1:9 for b=1:9 if (b=a), continue; end for c=1:9 if (c=a | c=b), continue; end for d=1:9 if (d=a | d=b | d=c), continue; end for e=1:9 if (e=a | e=b | e=c | e=d), continue; end for f=1:9 if (f=a | f=b | f=c | f=d | f=e), continue; end for g=1:9 if (g=a | g=b | g=c | g=d | g=e | g=f), continue; end for h=1:9 if (h=a | h=b | h=c | h=d | h=e | h=f | h=g), continue; end for i=1:9 if (i=a | i=b | i=c | i=d | i=e | i=f | i=g | i=h) continue; endif i=a & i=b & i=c & i=d & i=e & i=f & i=g & i=h .& a+b=c & d+e=f & g+h=i*10 & ab & de & ad & ghn=n+1;disp(第, num2str(n), 个解：, .num2str(a), +, num2str(b), =, num2str(c), , .num2str(d), +, num2str(e), =, num2str(f), , .num2str(g), +, num2str(h), =, num2str(i), 0) end;end;end;end;end;end;end;end;end;end; % 共有10个endt3=toc;fprintf(n The elapsed time(measured by tic/toc) is: %g,t3)附录1B (fulu1B.m)： t=cputime;n=0;for a=1:9 for b=1:9if b=afor c=1:9 if c=a & c=b for d=1:9if d=a & d=b & d=cfor e=1:9 if e=a & e=b & e=c & e=d for f=1:9if f=a & f=b & f=c & f=d & f=efor g=1:9 if g=a & g=b & g=c & g=d & g=e & g=f for h=1:9if h=a & h=b & h=c & h=d & h=e & h=f & h=gfor i=1:9 if i=a & i=b & i=c & i=d & i=e & i=f & i=g & i=h .& a+b=c & d+e=f & g+h=i*10 & ab & de & ad & ghn=n+1;disp(第, num2str(n), 个解：, .num2str(a), +, num2str(b), =, num2str(c), , .num2str(d), +, num2str(e), =, num2str(f), , .num2str(g), +, num2str(h), =, num2str(i), 0)end;end;end;end;end;end;end;end;end;end; end;end;end;end;end;end;end % 共有17个endtime=cputime-t附录2 (fulu2.m，提速版)：t02=clock;n=0;A1=1:9;for i1=1:9 a=A1(i1); A2=A1(1:i1-1,i1+1:9); for i2=1:8 b=A2(i2); A3=A2(1:i2-1,i2+1:8); for i3=1:7 c=A3(i3); A4=A3(1:i3-1,i3+1:7); for i4=1:6 d=A4(i4); A5=A4(1:i4-1,i4+1:6); for i5=1:5 e=A5(i5); A6=A5(1:i5-1,i5+1:5); for i6=1:4 f=A6(i6); A7=A6(1:i6-1,i6+1:4); for i7=1:3 g=A7(i7); A8=A7(1:i7-1,i7+1:3); for i8=1:2 h=A8(i8); i=A8(1:i8-1,i8+1:2);if a+b=c & d+e=f & g+h=i*10 & ab & de & ad & ghn=n+1;disp(第, num2str(n), 个解：, .num2str(a), +, num2str(b), =, num2str(c), , .num2str(d), +, num2str(e), =, num2str(f), , .num2str(g), +, num2str(h), =, num2str(i), 0) end end end end end end end endendt2=etime(clock,t02);fprintf(n The elapsed time(measured by clock/etime) is: %g,t2)附录3 (Turbo C 程序，fulu3.c)：#includemain() int a,b,c,d,e,f,g,h,i,j,n=0;printf(nn);for (a=1;a=9;a+) for (b=1;b=9;b+)if (b=a) continue;for (c=1;c=9;c+) if (c=a|c=b) continue; for (d=1;d=9;d+)if (d=a|d=b|d=c) continue;for (e=1;e=9;e+) if (e=a|e=b|e=c|e=d) continue; for (f=1;f=9;f+)if (f=a|f=b|f=c|f=d|f=e) continue;for (g=1;g=9;g+) if (g=a|g=b|g=c|g=d|g=e|g=f) continue; for (h=1;h=9;h+)if (h=a|h=b|h=c|h=d|h=e|h=f|h=g) continue;for (i=1;i=9;i+) if(i=a|i=b|i=c|i=d|i=e|i=f|i=g|i=h) continue; else if (a+b=c)&(d+e=f) &(g+h=10*i)&(ab)&(de)&(ad)&(gh)printf (%3d: %d+%d=%d, %d+%d=%d, %d+%d=%d0 ,+n,a,b,c,d,e,f,g,h,i); if (n%3=0) printf(n); 附录4 (Mathematica 程序，fulu4.nb)：Timing (*a+b=c, d+e=f, g+h=i0*)Clearn,a,b,c,d,e,f,g,h,i; n=0;Fora=1,a=9,a+, Forb=1,b=9,b+,Ifb!=a,Forc=1,c=9,c+,Ifc!=a&c!=b, Ford=1,d=9,d+,Ifd!=a&d!=b&d!=c,Fore=1,e=9,e+,Ife!=a&e!=b&e!=c&e!=d, Forf=1,f=9,f+,Iff!=a&f!=b&f!=c&f!=d&f!=e,Forg=1,g=9,g+,Ifg!=a&g!=b&g!=c&g!=d&g!=e&g!=f,Forh=1,h=9,h+,Ifh!=a&h!=b&h!=c&h!=d&h!=e&h!=f&h!=g,Fori=1,i=9,i+,Ifi!=a&i!=b&i!=c&i!=d&i!=e&i!=f&i!=g&i!=h&a+b=c&d+e=f&g+h=10*i&ab&de&ad&gh,Print+n,: ,a,+,b,=,c,d,+,e,=,f,g,+,h,=,i,0 (* total have 17 right )s *)附录5 (Matlab 程序，fulu5.m)：程序基本上同附录1，只要将倒数第 4 行至倒数第 9 行换成下列 5 行即可if i=a & i=b & i=c & i=d & i=e & i=f & i=g & i=h . & (100*a+10*b+c)+(100*d+10*e+f)=(100*g+10*h+i) & adn=n+1;disp(第, num2str(n), 个解：, .num2str(100*a+10*b+c), +, num2str(100*d+10*e+f), =, num2str(100*g+10*h+i)附录6 (Matlab 程序，fulu6.m)：程序基本上同附录1，只要将倒数第 4行至倒数第 9 行换成下列 6 行即可if i=a & i=b & i=c & i=d & i=e & i=f & i=g & i=h .& a/(10*b+c)+d/(10*e+f)=g/(10*h+i) & adn=n+1;disp(第, num2str(n), 个解：, num2str(a), / , num2str(b), num2str(c), +, .num2str(d), / , num2str(e) , num2str(f), =, num2str(g), /, num2str(h), num2str(i)