分享
 
 
 

离散数学趣味题目

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

离散数学趣味题目

1,Catalan数

饭后,姐妹洗碗,妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。共有n个两两相异的碗,洗前也摞成一摞,也许因为妹妹贪玩,碗拿进橱子不及时,姐姐就把洗过的碗摞在傍边:

-

- - - -

— — - -

- - — —

(1)待洗 (2)待摞 (3)已摞

问最后小妹摞起的碗摞可能有几种方式?

这个题目有个同解题是这样的:

一队不同的汽车行进在大街上,它们可以在任何时刻拐进一个死胡同里去加油,然后再出来加入队伍。问你最后出城时汽车队列有多少种可能形式?

呵呵,大家想想,有意思呢!

[简短分析]

这是个有趣的组合问题。组合数学是离散数学的一部分,研究的是组合计数问题。图论原来也是组合数学的一部分,后来才分家的:)。组合计数的一个指导性技巧是,如果对于一个过程的计数不好研究,就可以找一个和它有一一对应的过程,而且该过程相对很好研究,这不是很美吗?

你看看,如果碗有n个,姐姐每方下一个,就画一个“(”,妹妹如果摞一个,就画一个“)”,如果妹妹不贪玩,刚放下就能放好,串就是“()()()……()”,对吧?现在你来考虑一下,下次我说答案:)。

汽车车队也是如此,车进了胡同就画“(”,出来时再画“)”,而没有进胡同的就是“()”,呵呵,所以同解呢。

离散的问题,技巧性很大,初看问题的解没有规律,仿佛量体裁衣般的,但也有指导性的思路对吧?

2,拉姆赛问题

朴素的方式叙述:

r(p,q)是任意给的人群中必有p人相识或必有q人彼此不相识的人群人数之最小值。例如,r(3,3)=6,就是说,任意个的人群,最少6个人,一定可满足其中3个人相识,或3个人互相不认识。r(p,q)就称为拉姆赛数。

图论的方式叙述:

Any p,q in N,把一个完全图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

呵呵,你来试试,你能给出哪些拉姆赛数的推理过程?

[背景趣闻]

关于求拉姆赛数的艰巨性,著名匈牙利数学家厄尔多斯曾用下面的话比喻:

某年某月某日,一伙外星强盗入侵地球,威胁道,若不能一年内求出r(5,5),他们将灭绝人类!面对如此生死关头,人类应当召集全球所有的数学家和计算机专家,夜以继日的计算r(5,5),以求人类免于灭顶之灾;如果外星人要我们求得r(6,6),我们就别无选择了,干脆直接开战,放手一搏:)。

3,梦中情人

约翰的梦中情人长着金黄色的头发,蓝蓝的眼睛,纤细的身子,高高的个子。他认识阿

黛尔,贝蒂,卡洛尔和多丽丝四位小姐,其中一位是约翰的梦中情人。(1)只有三位小

姐是蓝眼睛和细身材。(2)只有两位是黄头发和高个子(3)只有两位是细身材和高个

子。(4)只有一位是蓝眼睛和黄头发(5) 阿黛尔和贝蒂眼睛颜色相同。(6)贝蒂和

卡洛尔头发颜色相同(7)卡洛尔和多丽丝身材不同(8)多丽丝和阿黛尔身高相同。四

位中谁是约翰的梦中情人?

[简单分析]

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有