初中生周记大全-打架检讨书

离散数学趣味题目
1,Catalan数
饭后，姐妹洗碗，妹妹把姐姐 洗过的碗一个一个放进碗橱摞
成一摞。共有n个两两相异的碗，洗前也摞成一摞，也许因
为妹妹 贪玩，碗拿进橱子不及时，姐姐就把洗过的碗摞在傍
边：
（1）待洗（2）待摞（3）已摞
问最后小妹摞起的碗摞可能有几种方式？
这个题目有个同解题是这样的：
一队不同 的汽车行进在大街上，它们可以在任何时刻拐进一
个死胡同里去加油，然后再出来加入队伍。问你最后出 城时
汽车队列有多少种可能形式？
呵呵，大家想想，有意思呢！
[简短分析] < br>这是个有趣的组合问题。组合数学是离散数学的一部分，研
究的是组合计数问题。图论原来也是组 合数学的一部分，后
来才分家的：）。组合计数的一个指导性技巧是，如果对于一
个过程的计数 不好研究，就可以找一个和它有一一对应的过
程，而且该过程相对很好研究，这不是很美吗？
你看看，如果碗有n个，姐姐每方下一个，就画一个“（”，
妹妹如果摞一个，就画一个“）”，如果妹 妹不贪玩，刚放
下就能放好，串就是“（）（）（）……（）”，对吧？现在
第 1 页

你来考虑一下，下次我说答案：）。
汽车车队也是如此，车进了胡同就画“（ ”，出来时再画
“）”，而没有进胡同的就是“（）”，呵呵，所以同解呢。
离散的问题，技 巧性很大，初看问题的解没有规律，仿佛量
体裁衣般的，但也有指导性的思路对吧？
2，拉姆赛问题
朴素的方式叙述：
r（p，q）是任意给的人群中必有p人相识或 必有q人彼此
不相识的人群人数之最小值。例如，r（3，3）=6，就是说，
任意个的人群， 最少6个人，一定可满足其中3个人相识，
或3个人互相不认识。r（p，q）就称为拉姆赛数。
图论的方式叙述：
Anyp，qinN,把一个完全图G用红与蓝两色进行边涂色，每
条边一种颜色，其结果或者有一个红色p边形，连同其全部
对角线皆为红色，或者有一个蓝色q边形， 连同其全部对角
线皆为蓝色，G最小的顶点数，能保证出现上述结果，就是
拉姆赛数r（p，q ）。
经过几代人的努力，加上计算机的帮忙，现在人类求的9个
非平凡的拉姆赛数：
r（3，3）=6，r（3，4）=9，r（3，5）=14
r（3，6）=18，r（3，7）=23，r（3，8）=28
r（3，9）=36，r（4，4）=18，r（4，5）=25
第 2 页

呵呵，你来试试，你能给出哪些拉姆赛数的推理过程？
[背景趣闻]
关于求拉姆赛数的艰巨性，著名匈牙利数学家厄尔多斯曾用
下面的话比喻：
某年某月 某日，一伙外星强盗入侵地球，威胁道，若不能一
年内求出r（5，5），他们将灭绝人类！面对如此生 死关头，
人类应当召集全球所有的数学家和计算机专家，夜以继日的
计算r（5，5），以求人 类免于灭顶之灾；如果外星人要我们
求得r（6，6），我们就别无选择了，干脆直接开战，放手一搏：）。
3，梦中情人
约翰的梦中情人长着金黄色的头发，蓝蓝的眼睛，纤细的身
子，高高的个子。他认识阿
黛尔，贝蒂，卡洛尔和多丽丝四位小姐，其中一位是约翰的
梦中情人。（1）只有三位小
姐是蓝眼睛和细身材。（2）只有两位是黄头发和高个子（3）
只有两位是细身材和高个
子。（4）只有一位是蓝眼睛和黄头发（5）阿黛尔和贝蒂眼
睛颜色相同。（6）贝蒂和
卡洛尔头发颜色相同（7）卡洛尔和多丽丝身材不同（8）多
丽丝和阿黛尔身高相同。四
位中谁是约翰的梦中情人？
第 3 页

[简单分析]
呵 呵，显然这是个数理逻辑问题了。可以建立形式化的模型
来分析，也可以用朴素的推理过程来做。很有意 思的，这是
离散数学的魅力！

第 4 页