数学建模教程课后答案.ppt

第一章思考题参考答案 #1-1:关于过河问题(1)的思考题 问题:此问题的答案唯一吗?不允许重复时有几个答案? 最少渡河次数是多少? 如果每人都能划船结论又是如何? 解:不允许重复时有2个不同答案.前面讲过一个答案是(共7次):①师乙过去,接着师回;②师甲过去,接着师乙回;③师丙过去,接着师回;④师乙过去. 还有且仅有另一个答案是(甲丙互换): ①师乙过去,接着师回;②师丙去,接着师 乙回;③师甲过去,接着师回;④师乙过去. 所以,问题有2个不允许重复答案,7次渡河. 每人能划船条件下的一种安全过河方案 (共5次过渡) ① 甲丙过去, 接着甲回; ② 师甲过去, 接着师回; ③ 师乙过去. #1-2①:对任何正整数n的n商n从安全过河问题,不允许重复的解一定是有限个. 证:对给定的正整数n,安全状态集的点数是有限数3n+1.显然,经过有限个点,并按跳棋规则从点(n,n)跳到点(0,0)的不重复跳棋方案的个数一定有限.这就证明:不重复安全过河方案必定是有限个. #1-2②:在渡船至多容2人条件下,3商3从安全过河问题,不允许重复解的个数是4. 证:下图给出一个无重复的解.仔细分析此解不难看出:任何一个无重复的解的最先2步除下图给出的方案外,还有且仅有另一个方案是:”1商1从过去,接着1商回来”.此外,其最后2步除下图给出的方案外,还有且仅有另一个方案是:”1商回来,接着1商1从过去”. 所以,3商3从安全过河问题,不允许重复解的个数是2?2=4个. #1-3 船至多容2人时,讨论n(?2)商人n随从能否安全过河? 解:已讲过:n=3存在安全过河方案;n=2存在安全过河方案如下图所示.显然,不存在任何无重复安全过河解便一定不存在任何安全过河解?. 今证:n?4不存在任何无重复安全过河解.(反证法)设存在一个无重复安全过河方案.该方案第一次跳到y轴前的状态只能是(如图所示):(2,2)和(1,1),且都是偶数步.若为(2,2) 则前一步必是从(1,1)到(2,2)产生重复; 若为(1,1),则前一步必来自y轴上的点都是不可能的. #1-4 n+1商人n随从安全过河问题 问题:设渡船至多容纳2人,n+1商人n随从能否安全过河? 解:此岸状态图如下图所示.用一次”一商一从去,接着一从回,一商一从去,接着一商回”的循环可使此岸状态从(i+1,i)改变到(i,i-1).经n-1次这种循环之后,从(n+1,n)变到(2,1);再经 ”一商一从去,接着一从回,最后一商一从去”三次过渡便达到(0,0)状态.不难看出:全程共需4(n-1)+3次渡河. 对n用归纳法证明n+1商n从能安全过河 证:n=1时,2商1从可安全过河(次数为3),结论显然成立.设n=k时结论已经成立,则让k+1商k从经xk次全安全渡到对岸,接着,一商回,再二商去,一商回,最后一商一从去,全体安全到达对岸.所以,n=k时结论成立可推出n=k+1时结论也成立.再推导公式:xn=4n-1. 上面已推出:x1=3;xk+1=xk+4,对任意正整数k成立.于是 xn=xn-1+4=xn-2+2?4=…=x1+4(n-1)=4(n-1)+3 #1-5? 五商人五随从安全过河问题 解:假设渡船至多容3人,5商人和5随从能安全过河.仿照解安全过河问题(2)的方法,一个安全过河方案(共过渡11次,参看下图)如下: 3从过去 接着 1从回来; 2从过去 接着 1从回来; 3商过去 接着 1商1从回来; 3商过去 接着 1从回来; 3从过去 接着 1从回来; 2从过去. #1-5? n商人n随从安全过河问题 问题推广:假设渡船至多容m(1)人,2m-1商人和2m-1随从必能安全过河. 证:仿照解安全过河问题(2)和#1-5?的方法,一个过渡11次的安全过河方案如下: m从过去 接着 1从回来; 2从过去 接着 1从回来; m商过去 接着 1商1从回来; m商过去 接着 1从回来; m从过去 接着 1从回来; m-1从过去. #1-6 船可容4人必能安全过河 解:假设渡船至多容4人和n0,则n商人和n随从必能安全过河. 一个安全过河方案如下: 2商2从过去,接着1商1从回来,此岸状态变为(n-1,n-1); 再重复一次上述循环,此岸状态变为 (n-2,n-2); 经n-2次上述循环后,此岸状态变为(2,2);再2商2从过去即可.共过渡4(n-2)+1次. #1-7② {fn}封闭公式(2.1)的证明 证:考察以fn为系数的形式幂级数: F(x)=?n=0?fn+1xn=f1+?n=1?fn+1xn 利用已知关系: