第15课时5.2.2数学归纳法应用

1、第第5章章 数学证明数学证明 5.2数学归纳法数学归纳法5.2.25.2.2数学归纳法应用数学归纳法应用第第15课时课时数学归纳法应用数学归纳法应用 例例2：某次象棋比赛共有人参加，每两个：某次象棋比赛共有人参加，每两个都应对奕，且一定决出胜负都应对奕，且一定决出胜负.证明：比赛证明：比赛结束后，可将这个人列为一队，使队列结束后，可将这个人列为一队，使队列中的每一个人都曾战胜过紧跟在他后面中的每一个人都曾战胜过紧跟在他后面的那个人的那个人. 例例3有有2n+1个飞机场，每个机场都有一架飞机，各个飞机场，每个机场都有一架飞机，各个机场间的距离都不相等，让所有的飞机一起起飞，个机场间的距离都不相等

2、，让所有的飞机一起起飞，飞向最近的机场降落。飞向最近的机场降落。 求证：必存在一个机场，没有飞机降落。求证：必存在一个机场，没有飞机降落。 1当当n=1时，时，3个机场为个机场为A、B、C，且且BCAC,BCAB 则则B、C间的飞机必定对飞，间的飞机必定对飞， 于是不管于是不管A机场的飞机飞向机场的飞机飞向B还是还是C机场，机场，A机场都没机场都没有飞机降落。有飞机降落。 2假设假设n=k时命题成立，则当时命题成立，则当n=k+1即即2k+3个机场时，个机场时， 由于各机场间距离都不相等，必有两个机场间距离最由于各机场间距离都不相等，必有两个机场间距离最短，这两处的飞机对开。短，这两处的飞机对

3、开。 将这两机场将这两机场“撤出撤出”，由假设，剩下的，由假设，剩下的2k+1个机场个机场中，必存在一个机场中，必存在一个机场P没有飞机降落。没有飞机降落。 再把再把“撤出撤出”的两机场复归，则机场的两机场复归，则机场P仍无飞机降落，仍无飞机降落， 得得n=k+1时命题仍成立。时命题仍成立。第二数学归纳法第二数学归纳法例举例举 例例4、有两堆棋子，数目相等。两人玩耍，每人可以在一堆里、有两堆棋子，数目相等。两人玩耍，每人可以在一堆里任意取几棵，但不能同时在两堆里取，规定取得最后一棵者胜。任意取几棵，但不能同时在两堆里取，规定取得最后一棵者胜。问先取者得胜，还是后取者可以得胜？试加以证明。问先取

4、者得胜，还是后取者可以得胜？试加以证明。 猜测猜测“后取者可以得胜后取者可以得胜”。 证明证明：（1）当当n=1时，必是后取者得胜。时，必是后取者得胜。 （2）假设当）假设当nk时命题成立，对于时命题成立，对于n=k+1，当先取者在一堆里，当先取者在一堆里取棋子取棋子m (1mk+1)颗时颗时， 后取者则在另一堆里取棋子后取者则在另一堆里取棋子m颗，两堆棋子仍都是颗，两堆棋子仍都是(k+1-m)颗。颗。 这样就变成了这样就变成了n=k+1-m的问题，按照归纳假设，后取者可以得的问题，按照归纳假设，后取者可以得胜，即胜，即n=k+1命题也成立。命题也成立。 由第二数学归纳法，证明了：对于任意正整

5、数由第二数学归纳法，证明了：对于任意正整数n，后取者按上后取者按上述策略都可以得胜。述策略都可以得胜。 思考：若两堆棋子的数目不同，则思考：若两堆棋子的数目不同，则先取者和后取者哪个有必胜先取者和后取者哪个有必胜的策略？的策略？案例案例1多面体欧拉公式多面体欧拉公式多面体欧拉公式的证明及其在平面上的推广多面体欧拉公式的证明及其在平面上的推广连通平面图的特征连通平面图的特征 外部面外部面“海洋海洋”，内部，内部面。面。 连通图：图中任意两点都有连通图：图中任意两点都有路相通路相通。 如果一个连通的平面图如果一个连通的平面图G有有V个顶点，个顶点，E条边，条边，F个面，那个面，那么么V-E+F=2

6、。 对平面图的边数用数学归纳对平面图的边数用数学归纳法证明法证明如果一个连通的平面图如果一个连通的平面图G有有V个顶点，个顶点，E条条边，边，F个面，那么个面，那么V-E+F=2。 思考：思考：对对V,E,F哪个量进行归纳哪个量进行归纳比较合适？比较合适？ 对边数对边数E进行归纳试试看！进行归纳试试看！ 证明：证明： 1）若）若G只有只有1条边条边,则则 V=2,E=1,F=1,故故V-E+F=2成立。成立。 2）假设假设G为有为有k条边的连通的平条边的连通的平面图，公式面图，公式Vk-Ek+Fk=2成立成立。 考察考察G为（为（k+1）条边时的情况。条边时的情况。 即当图即当图G由由k条边增

7、加条边增加1条边，使条边，使它仍为连通图时，有哪些情形？它仍为连通图时，有哪些情形？连通平面图连通平面图G有有V-E+F=2成立成立 （2） 当当G为（为（k+1）条边时条边时,只有两种情形：只有两种情形： 1）增加一个新顶点增加一个新顶点v/，则则v/必与图中的一点必与图中的一点v相连。相连。 此时，此时，Vk与与Ek都增加都增加1，而，而Fk不变，不变， 故故Vk+1-Ek+1+Fk+1 =(Vk+1)-(Ek+1)+Fk=Vk-Ek+Fk=2. 2）用一条边连结图中两个顶点用一条边连结图中两个顶点u和和v。 这时，这时，Ek和和Fk都增加都增加1，而顶点数，而顶点数Vk没有变，没有变， 故故Vk+1-Ek+