📄 timu.htm
字号:
<p><span lang=EN-US>11. 证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。注意F<sub>1</sub>=F<sub>2</sub>=1是相同的Fibonacci数。 </span></p>
<p>证明：这里只证明可表示性<span lang=EN-US>(对n用归纳法). </span></p>
<p><span lang=EN-US> 1）当n=1时命题成立 </span></p>
<p style='text-indent:24.0pt'><span lang=EN-US>2）设对小于n的正整数命题成立。 对于n+1，如果存在k使得n+1
= F<sub>k </sub><span style="mso-spacerun: yes"> </span>，结论是显然的。否则存在k,满足F<sub>k
</sub>< n+1 < F<sub>k+1</sub> 。 </span></p>
<p style='text-indent:24.0pt'>则<span lang=EN-US>n+1-F<sub>k</sub>可表示为不相同且不相邻的F数列的和,且其中每个的下标i都满足i
< k-1.(否则，F<sub>k-1</sub> <= n+1-F<sub>k</sub> < F<sub>k+1</sub> - F<sub>k</sub>
= F<sub>k-1</sub>,矛盾)</span></p>
<p style='text-indent:24.0pt'>这样<span lang=EN-US>n+1也可以表示成不相同且不相邻的F数列的和。</span></p>
<p style='text-indent:24.0pt'>利用归纳原理，命题得证。</p>
<p style='text-indent:24.0pt'>关于唯一性：我觉得一般是不成立的。只要利用<span lang=EN-US>F<sub>2m</sub>
= F<sub>2m-1</sub> + F<sub>2n-3</sub> + …… + F<sub>3 </sub>+ F<sub>1</sub>就可以构造很多这样的反例。 </span></p>
<p><span lang=EN-US>12. 设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？ </span></p>
<p>解：设<span lang=EN-US>n个满足条件的平面把空间分成a<sub>n</sub>个域，n-1个满足条件的平面把空间分成a<sub>n-1</sub>个域
，则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。第n个平面被这n-1条线分成C(n-1,2)+1个域 。</span></p>
<p>可得<span lang=EN-US> <img width=184 height=21 id="_x0000_i1070"
src="timu.files\timu.h59.gif" border=0></span></p>
<p>设<span lang=EN-US> <img width=166 height=41 id="_x0000_i1071"
src="timu.files\timu.h60.gif" border=0></span></p>
<p>解得</p>
<p><span lang=EN-US> <img width=116
height=126 id="_x0000_i1072" src="timu.files\timu.h61.gif" border=0></span></p>
<p><span lang=EN-US>13. 相邻位不同为0的n位2进制数中一共出现了多少个0？ </span></p>
<p>解：设符合条件的<span lang=EN-US>n位二进制数的个数为h<sub>n</sub> 这些数中一共有a<sub>n</sub>个0
。 当n位二进制数最高位为1时,符合条件的n位二进制数的个数为h<sub>n-1</sub></span></p>
<p><span lang=EN-US> <sub> </sub>最高位为0时，次高位必为1符合条件的n位二进制数的个数为h<sub>n-2</sub></span></p>
<p><span lang=EN-US> <img width=213 height=20 id="_x0000_i1073"
src="timu.files\timu.h62.gif" border=0><span style="mso-spacerun:
yes"> </span>即h<sub>n</sub>是F数列 </span></p>
<p><span lang=EN-US> <img width=199
height=106 id="_x0000_i1074" src="timu.files\timu.h63.gif" border=0></span></p>
<p>特征方程为：<span lang=EN-US> </span></p>
<p><span lang=EN-US> <img width=88
height=20 id="_x0000_i1075" src="timu.files\timu.h64.gif" border=0></span></p>
<p>解得<span lang=EN-US>a、b为2重根。 设 </span></p>
<p><span lang=EN-US> <img width=165
height=20 id="_x0000_i1076" src="timu.files\timu.h65.gif" border=0></span></p>
<p>分析上式结构可得：<span lang=EN-US> </span></p>
<p><span lang=EN-US> <img width=225
height=133 id="_x0000_i1077" src="timu.files\timu.h66.gif" border=0></span></p>
<p>把<span lang=EN-US>n=2代入可解得： </span></p>
<p><span lang=EN-US> <img width=126
height=29 id="_x0000_i1078" src="timu.files\timu.h67.gif" border=0></span></p>
<p>代入<span lang=EN-US>a<sub>n</sub></span></p>
<p><span lang=EN-US> <img width=199
height=29 id="_x0000_i1079" src="timu.files\timu.h68.gif" border=0></span></p>
<p>可得方程组<span lang=EN-US> </span></p>
<p><span lang=EN-US> <img width=161
height=45 id="_x0000_i1080" src="timu.files\timu.h69.gif" border=0></span></p>
<p>解得</p>
<p><span lang=EN-US> <img width=70
height=75 id="_x0000_i1081" src="timu.files\timu.h70.gif" border=0></span></p>
<p><span lang=EN-US> <img width=221
height=79 id="_x0000_i1082" src="timu.files\timu.h71.gif" border=0></span></p>
<p><span lang=EN-US>14. 在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？ </span></p>
<p>解：设<span lang=EN-US>n为偶数 </span></p>
<p><span lang=EN-US> 1）先把n-1个盘通过C移到B </span></p>
<p><span lang=EN-US> 2）把第n个盘移到C </span></p>
<p><span lang=EN-US> 3）把n-3个盘通过C移到A </span></p>
<p><span lang=EN-US> 4）把第n-2个盘移到B </span></p>
<p><span lang=EN-US> 对n为奇数时上述四步仍然成立，但是B、C对调。 </span></p>
<p><span lang=EN-US> <img width=231
height=19 id="_x0000_i1083" src="timu.files\timu.h72.gif" border=0></span></p>
<p>其中<span lang=EN-US>k(1)=1,k(2)=2,k(3)=5</span></p>
<p><span lang=EN-US>h(k)为Hanota数列。 </span></p>
<p><span lang=EN-US> <img width=180
height=43 id="_x0000_i1084" src="timu.files\timu.h73.gif" border=0></span></p>
<p>可得特征方程：<span lang=EN-US> </span></p>
<p><span lang=EN-US> <img width=97
height=20 id="_x0000_i1085" src="timu.files\timu.h74.gif" border=0></span></p>
<p>解得<span lang=EN-US> <img width=132 height=32
id="_x0000_i1086" src="timu.files\timu.h75.gif" border=0></span></p>
<p><span lang=EN-US> <img width=231
height=35 id="_x0000_i1087" src="timu.files\timu.h76.gif" border=0></span></p>
<p>代入初值可解得<span lang=EN-US> <img width=97 height=38
id="_x0000_i1088" src="timu.files\timu.h77.gif" border=0></span></p>
<p> </p>
<p><span lang=EN-US>15. 一书框中有m格，每格各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？</span></p>
<p>解：设<span lang=EN-US>m层中有k层不在原来的层上，m-k层在原有层上，但是每册都不在原来的位置。 <img
width=160 height=41 id="_x0000_i1089" src="timu.files\timu.h78.gif" border=0></span></p>
<p><span lang=EN-US>16. 设一矩形ABCD,其中</span></p>
<p><span lang=EN-US> <img width=116
height=35 id="_x0000_i1090" src="timu.files\timu.h8.gif" border=0></span></p>
<p>作<span lang=EN-US>C<sub>1</sub>B<sub>1</sub>使得AB<sub>1</sub>C<sub>1</sub>D是一正方形。试证矩形B<sub>1</sub>C<sub>1</sub>CD和ABCD相似。试证继续这过程可得一和原矩形相似的矩形序列。 </span></p>
<p>解：把<span lang=EN-US>AD看成1 则AB为 <img width=40 height=39
id="_x0000_i1091" src="timu.files\timu.h79.gif" border=0></span></p>
<p><span lang=EN-US> <img width=161
height=117 id="_x0000_i1092" src="timu.files\timu.h80.gif" border=0></span></p>
<p><span lang=EN-US> <img width=106
height=19 id="_x0000_i1093" src="timu.files\timu.h81.gif" border=0></span></p>
<p>同理可得其他矩形相似</p>
<p><span lang=EN-US>17. 平面上有两两相交，无三线共点的n条直线，试求这n条直线把平面分成多少个域？ </span></p>
<p>解：满足条件的<span lang=EN-US>n条直线把平面分成a<sub>n</sub>个域，其中n-1条直线分割成的域数为a<sub>n-1</sub>，第n条直线与这n条直线均相交。
被分成n-1+1=n段。 </span></p>
<p><span lang=EN-US> 增加的域数为n。 <img width=168 height=20
id="_x0000_i1094" src="timu.files\timu.h82.gif" border=0></span></p>
<p>设<span lang=EN-US> <img width=121 height=41 id="_x0000_i1095"
src="timu.files\timu.h83.gif" border=0></span></p>
<p>解得</p>
<p><span lang=EN-US> <img width=96
height=106 id="_x0000_i1096" src="timu.files\timu.h84.gif" border=0></span></p>
<p><span lang=EN-US>18. 在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？ </span></p>
<p>解：<span lang=EN-US>n-1个点把圆分为a<sub>n-1</sub>部分，加上第n个点则对于前n-1个点来说，每选取3个点都有3条弦构成一个三角形，而中间的一点和第n点的连线把中间点与第n点间的弦分为两个部分，增加了一个域。而对第n点与其他n-1点的连线有把第1、n-1、n点构成的三角形分为n个域。
</span></p>
<p>所以递推关系为：<span lang=EN-US> </span></p>
<p><span lang=EN-US> <img width=203
height=63 id="_x0000_i1097" src="timu.files\timu.h85.gif" border=0></span></p>
<p>可设<span lang=EN-US> <img width=236 height=40 id="_x0000_i1098"
src="timu.files\timu.h86.gif" border=0></span></p>
<p>代入初值可解得</p>
<p><span lang=EN-US> <img width=108
height=147 id="_x0000_i1099" src="timu.files\timu.h87.gif" border=0></span></p>
<p>解法二：一共有<span lang=EN-US>C(n,1)个顶点，C(n,2)条边，每个内部的交点和外面的四个顶点是一一对应的，所以内部有C(n,4)的交点，加上顶点，有顶点数
V = C(n,4)+C(n,1)<o:p></o:p></span></p>
<p>而我们设<span lang=EN-US>m=C(n,2) , L<sub>1</sub>,L<sub>2</sub>,...,L<sub>m</sub>是所有的边，（含对角线），且L<sub>k</sub>上有x<sub>k</sub>个点（不含端点）,那么L<sub>k</sub>被分成了x<sub>k</sub>+1段，故一共有<span
style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1475"
type="#_x0000_t75" style='width:55.2pt;height:34.2pt' o:ole="">
<v:imagedata src="./timu.files/image055.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=73 height=46
src="./timu.files/image056.gif" v:shapes="_x0000_i1475"><![endif]></span><!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1475"
DrawAspect="Content" ObjectID="_1069585710">
</o:OLEObject>
</xml><![endif]--> 条小边，注意到<span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape
id="_x0000_i1481" type="#_x0000_t75" style='width:30pt;height:34.2pt' o:ole="">
<v:imagedata src="./timu.files/image057.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=40 height=46
src="./timu.files/image058.gif" v:shapes="_x0000_i1481"><![endif]></span><!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1481"
DrawAspect="Content" ObjectID="_1069585711">
</o:OLEObject>
</xml><![endif]-->= 2*内部点数 (因为每个内部点恰属于两条直线) = 2C(n,4)<o:p></o:p></span></p>
<p>所以边数<span lang=EN-US>E = <span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape
id="_x0000_i1480" type="#_x0000_t75" style='width:55.2pt;height:34.2pt' o:ole="">
<v:imagedata src="./timu.files/image055.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=74 height=45
src="./timu.files/image059.gif" v:shapes="_x0000_i1480"><![endif]></span><!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1480"
DrawAspect="Content" ObjectID="_1069585712">
</o:OLEObject>
</xml><![endif]--><span style="mso-spacerun: yes"> </span>= <span
style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1482"
type="#_x0000_t75" style='width:30pt;height:34.2pt' o:ole="">
<v:imagedata src="./timu.files/image060.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=40 height=45
src="./timu.files/image061.gif" v:shapes="_x0000_i1482"><![endif]></span><!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1482"
DrawAspect="Content" ObjectID="_1069585713">
</o:OLEObject>
</xml><![endif]-->+ m = 2C(n,4) + C(n,2)<o:p></o:p></span></p>
<p>由<span lang=EN-US>Euler公式，我们就有 F = E - V + 2 = C(n,4) + C(n,2) - C(n,1) + 2<o:p></o:p></span></p>
<p>再去掉外面的一个无界区域和添上<span lang=EN-US>C(n,1)个弓形区域，我们就有 F' = C(n,4) + C(n,2) + 1</span></p>
<p><span lang=EN-US>19. 求n位二进制数相邻两位不出现11的数的个数。 </span></p>
<p>解：设<span lang=EN-US>n-1位不出现11的个数为a<sub>n-1</sub> </span></p>
<p><span lang=EN-US> <sub> </sub>n-2位不出现11的个数为a<sub>n-2</sub> </span></p>
<p><span lang=EN-US> n位不出现11的个数为a<sub>n</sub></span></p>
<p><span lang=EN-US> <sub> </sub>则 <img width=218
height=41 id="_x0000_i1100" src="timu.files\timu.h88.gif" border=0></span></p>
<p><span lang=EN-US> 特征方程为 </span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -