有101个人参加乒乓球淘汰赛（每一轮比赛在参加人数是奇数时，让一人轮空），共需进行多少场比赛方可决出优胜者（一场比赛指两人的一次对垒）淘汰赛解（一）第一轮50场，剩50名优胜者1名轮空第二轮25场，剩25名优胜者1名轮空第三轮13场，剩13名优胜者第四轮6场，剩6名优胜者1名轮空第五轮3场，剩3名优胜者1名轮空第六轮2场，剩2名优胜者第七轮1场，剩1名优胜者共计50+25+13+6+3+2+1=100场解（二）用一一对应技术一场比赛对应一个被淘汰者，反之也真，那么比赛场数与被淘汰者人数是相等的由于优胜者只有一人，全部被淘汰者是100人，因此要进行100场比赛方可决出优胜者土耳其商人和帽子的故事这是著名物理学家爱因斯坦出过的一道题一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色的说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。
请问这个人猜得对吗？是怎么推导出来的？聪明的囚徒古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑并他自恃聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真假如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了试问：这囚徒说的是句什么话？哥哥尼尼斯斯堡堡城城位位于于普普雷雷格格尔尔河河畔畔，河河中中有有两两个个岛岛，七七座座桥桥使使两两个个河河心心岛岛及及两两岸岸彼彼此此相相连连十十八八世世纪纪的的城城中中居居民民热热衷衷于于这这样样一一个个问问题题：游人从四块陆地中的任何一地出发，能否找到一条路线，通过每桥一次且仅一次，最后返回原地？七桥问题欧拉对七桥问题的解欧拉对七桥问题的解17361736年年，著著名名数数学学家家欧欧拉拉研研究究了了七七桥桥问问题题，他他将将这这个个问问题题用用结结点点和和弧弧边边组组成成的的图图来来表表示示，问问题题归归结结为为从从图图中中任任一一结结点点出出发发，经经过过每每边边一一次次且且仅仅一一次次的的回回路路是是否否存存在在？他他找找到到了了存存在在这这样样一一条条回回路路的的充充分分必必要要条条件件，并并由由此此判断判断七桥问题无解而结束了而结束了哥尼斯堡城民的烦恼。
哥尼斯堡城民的烦恼同构同构任何一張平面地圖，如果相鄰的兩個國家，必須塗上不同的顏色以便劃清邊界，則至多只要四種顏色就搞定了，不管這張地圖有多麼奇特複雜四色问题發現者這是在西元1852年，由畢業於英國倫敦大學的弗朗西斯(FrancisGuthrie)發現的當時他正在畫英國各郡的地圖，而發現了這個有趣的現象格里斯覺得這其中一定有什麼奧妙，於是便寫信告訴他那數學很好的哥哥佛德雷克(FrederickGuthrie)佛德雷克百思不得其解，又求教於他的老師-數學家摩根(Morgan)摩根也無法確定這個說法對不對，於是又寫信給他的好朋友哈彌爾頓(Hamilton)，希望他要嘛就證明出這個說法是正確的，要不就舉一個反例，建構出一張需要5種顏色的地圖來大師級的哈彌爾頓耗了13年心血，仍一籌莫展，抱憾而逝公開徵答1878年，英國數學家Cayley將上述問題曝光取名為四色猜想(因為還不確定對不對，所以說是猜想)，公開徵求解答問題一傳出後，馬上就有了回應1879年和1880年，Kempe和Tait分別發表論文證明了四色問題轟動一時的熱度終於平息不料事隔11年後，一個名叫Heawood的年輕人指出了Kempe證明中的錯誤，並利用Kempe的方法證明出若用5種顏色就保證一定能區分出地圖上相鄰的區域。
雖然四色問題未被破解，但是至此算是邁出了一大步而另一方面，Tait的論文亦被陸陸續續發現多處錯誤，甚至最後一個錯誤是一直到1946年才被發現的從這裡我們可看出這些人的研究精神是多麼可敬，被發現錯誤的東西並未被棄之如敝屣般丟在一旁，仍舊不斷有人去研究它，甚至是在事隔半個多世紀之後當然這兩篇錯誤的論文在數學上仍然有其貢獻，不可小覷解題花絮一番風風雨雨下來，四色問題更加受到矚目了由於Heawood的五色定理的證明並不難，因此就有許多人也小看了四色問題的難度最有趣的是以下這個例子1902年秋天，閔可夫斯基教授(HermannMinkowsky，1864-1909，愛因斯坦的數學導師)在上拓樸學的課堂上就當著學生面前說：四色問題之所以尚未被解決是因為世界上第一流的數學家都還沒空去研究它而且興之所至，當場就證了起來；但是寫了好幾個黑板，卻依舊未能得證接下來幾個星期的課，他繼續證下去，課一堂一堂地過去了，他如身陷泥沼，仍舊無法證明出來他終於投降，承認自己也無能為力了就在這個時候，天空正好霹靂一聲巨響，他感嘆地說：上帝在責備我的狂妄！然後就繼續上他的拓樸課了离散数学是现代数学的一个重要离散数学是现代数学的一个重要分支，是计算机科学与技术的基分支，是计算机科学与技术的基础理论的核心课程之一。
离散数础理论的核心课程之一离散数学与计算机科学中的数据结构、学与计算机科学中的数据结构、操作系统、编译理论、算法分析、操作系统、编译理论、算法分析、逻辑设计、系统结构、机器定理逻辑设计、系统结构、机器定理证明等课程息息相关证明等课程息息相关基本内容包括数理逻辑、集合论、基本内容包括数理逻辑、集合论、代数系统、图论等几大部分代数系统、图论等几大部分绪绪言言离散数学离散数学(DiscreteMathematics)：研究离散结构的数学分科辞海79年版,P355用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明D.E.Knuth(克纽斯)1974年Turing奖获得者离散数学离散数学 左孝凌等左孝凌等 上海科技文献出版社上海科技文献出版社离散数学离散数学 耿素云等耿素云等 清华大学出版社清华大学出版社离散数学离散数学 方世昌主编方世昌主编 西安电子科大出版社西安电子科大出版社DiscreteMathematicsStructures BemardKolmanRobertC.BusbySharonRoss Prentice-HallInternational,Inc.1997.11 (英文原版影印英文原版影印)清华大学出版社清华大学出版社参参考考书书目目离散数学是培养抽象思维和逻辑推理的学科，因此要重视基本概念的学习，一定要认真研读教材，特别要从实例和习题中搞清众多概念的涵义。
适当多做习题，至少要按时完成作业，强迫自己通过特定条件下运用所学的概念和理论，才能真正掌握和理解它们，提高分析和解决问题的能力与教材配套的习题解答是离散数学的初学者必备的参考书，钻研习题解答，从中领会典型问题的解题方法不会求解的作业题，可以看习题解答，但务求读懂，决不可一抄了事，养成依赖习惯，白白浪费宝贵的时光！学学习习方方法法建建议议（关机）（关机）作业（及时）作业（及时）考试（改革）考试（改革）约约法法三三章章7/25/20227/25/2022第一篇预备知识第2章计数问题7/25/20227/25/20222.0内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院7/25/20227/25/20227/25/20227/25/20222.1本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 7/25/20227/25/2022表2.2.1开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.757/25/20227/25/20222.2.1乘法原理如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：7/25/20227/25/2022例2.2.2Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。
当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050505050+5050+50505050+5050+5050+50+150+50+1=6377551=6377551个接收者个接收者7/25/20227/25/2022例2.2.3在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，选择第八位每一个位有两种选择，故根据乘法原理，8位编码共有22222222=28=256种取值解每个点有256(=28)种不同的取值7/25/20227/25/20222.2.2加法原理假定X1,X2,Xt均为集合，第i个集合Xi有ni个元素如X1,X2,Xt为两两不相交的集合，则可以从X1,X2,Xt中选出的元素总数为：n1+n2+nt。
即集合即集合即集合即集合X X X X1 1 1 1XXXX2 2 2 2X X X Xt t t t含有含有含有含有n n n n1 1 1 1+n+n+n+n2 2 2 2+n n n nt t t t个元素7/25/20227/25/2022例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？7/25/20227/25/2022例2.2.4解（1）根据乘法原理，可能的选法种数为654=120；（2）法一根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选根据乘法原理，可能的选法种数为254=40；7/25/20227/25/2022例2.2.4解(续)法。