一个趣题

Standard

复习离散数学看到逻辑的部分时,突然想起高三的时候刘鑫权告诉我的一道趣题(忘记了原来的题目描述):

假设你在奇怪的地方迷路了,前方有两条路(不妨成为甲路和乙路),据你所知这两条路有一条是安全的,另一条十分凶险,但两条路看上去完全一样,你不知道走哪条,这时出现了一个神,它的目的要么是帮你,要么是坑你,但你根本看出来。神说:”我可以帮你解答一个问题,记住,只有一个,并且这个问题的答案要么是真,要么是假“。如果神是来帮你的,那他就会如实回答该问题的真假,如果是来坑你的,那它就会将真说成假,将假说成真。如何才能通过这一个问题的答案知道哪条路是安全的呢?

Continue reading

Dilworth 定理

Standard

今天想起高中搞算法竞赛的时候的一个题目:NOIP1999导弹拦截。当时并不明白第二问的做法为什么是正确的,现在又看了一遍离散数学书后总算知道了。这个问题的第二问是要求出一个序列最少能被多少个不上升序列覆盖,比如\((1,4,3,2,6,7)\)可以分解成\((1,4,6,7),(3),(2)\)这三段不上升序列,并且这是最少的划分,而通过Dilworth定理就可以得出这最少划分数和这个序列的最长不升子序列长度的关系,比如,在刚才这个例子中\((4,3,2)\)是最长不升子序列,它的长度也是3。

Dilworth定理更加一般的阐述了这种对应的关系,接下来介绍这个定理:

首先,定义“\(\leq\)”是一个偏序关系(例如集合的包含关系、正整数的整除关系都是偏序关系),下面的例子阐述的是\(A=(1,2,3,5,6,10,15,30,60)\),\(B=(1,2,3,4,6,8,12,24)\)以及\(C=A\cup B\)整除关于整除关系的哈斯图(从下往上看,每条连线上面的元素意味着能被下面的元素整除,并且传递关系被省略不写)

哈斯图

描述整除关系的哈斯图(图片来源

在A集合中\((30,15,5,1)\)之中任何两个元素都是“可比的”(在这个例子当中意味着一方可以被另一个整除,比如15能被5整除),我们把元素集合的这样一个子集称之为“”。而5不能被3、2整除,反之也不能,所以5和3、2是不可比的,一个反链指的是一个任何两个不同的元素都不可比的集合,比如在A中\({5,3,2}\)就是一个反链(实际上也是A种最长的反链,另外\({15,10,6}\)也是最长的反链)。集合的一个链划分指的是将集合分成若干个交为空的链,并且使得它们的并是整个集合,比如对于A集合来说\((1,5,10,30),(3,15),(2,6)\)构成了一个链划分(这个划分中链的个数是所有划分中最少的)

Dilworth定理:集合中 最长的 反链长度  等于  把集合 链划分 的 最小 链个数。

在C集合中,{8, 10, 12, 15}是个最长的反链,而C可以被链划分成 { {5, 15}, {1, 10, 30, 60}, {3, 6, 12}, {2, 4, 8, 24} }。

另外Dilworth定理也意味着:

集合中 最长的 链长度  等于  把集合 反链划分 的 最小 反链个数。(反链划分的定义和链划分类似)

现在回头看把一个序列划分成最少的不上升子序列的问题——显然,“小于等于”和“大于”关系在某全序集合A(全序意味着集合中任意元素可比)上是互补的,也就是说在偏序集\(<A,\leq>\)中的最大反链长其实就是\(<A,>>\)中的最大链长,也就是说要求出不升序划分(链最少的不升序链划分)就等于是求最长上升序列的长度!于是问题就解决了。

练习题

 

又一起暴力枪击案!

Standard

无意中看到了发生在巴黎的枪击案

法国讽刺漫画杂志《查理周刊》枪击事件目前统计已有12人死亡。据警方介绍,凶手屠杀过程中使用了卡拉什尼科夫自动步枪(AK系列)和火箭筒。

视频中看到歹徒远距离枪击受害者在其倒地后又上前近距离射击,在地上徒劳挣扎的受害者随即失去生命迹象。

一直以来都知道流血事件在我们的世界从来没有停息过,但是看到在巴黎发生事情,以及查阅了一下近年来发生的暴力事件及其起因后,我才意识到问题的严重之程度超过我的想象。还记得前几天看了看当年911事件的现场视频,两座大厦被高速飞机,还记得2014年3月昆明火车站大屠杀

这些席卷全球的暴力事件的肇事者总是穆斯林!!

我并没有认识任何穆斯林朋友,几乎完全不了解伊斯兰文化,但在这21世纪,任何血腥的暴力都不应该被人们忘记!我们从赤贫的原始社会走来、腥风血雨的一路走来,决不能忘记历史上的惨剧,吸取教训。频繁的发生这种恶劣的事情实在难以原谅。

 

观看2015年维也纳新年音乐会!

Standard
标志

标志

黑管

黑管

竖琴

竖琴

大厅

大厅

黑管

黑管

小提琴

小提琴

整个音乐会分为上下两场一共近3个小时,印象最深的就数“电磁波尔卡”“蒸气快速波尔卡”“香槟加洛普”“爆炸波尔卡”,当然,还有相当经典的“蓝色多瑙河”“拉德斯基进行曲”

这些波尔卡十分诙谐幽默,比如“蒸汽快速波尔卡”演奏当中能听到尖锐的机车汽笛声,也有能发出“咔哒咔哒”的火车经过的声音,“香槟加洛普”演奏当中总会突然听到开酒瓶的“嘭”声,在结束的时候大家也喝起了香槟,场面十分有趣。

这次的第一个加演曲目“爆炸波尔卡”给我们了一个惊喜——在曲子结束的时候在现场真的发生了“爆炸”,礼炮打响,五彩缤纷的纸片纷纷扬扬,真想去现场感受一下这种惊喜的感觉:D

礼花爆炸后整个音乐会想起经久不息的掌声,在热情洋溢的氛围中乐队象征性的演奏了“蓝色多瑙河”和“拉德斯基进行曲”,整个音乐会就圆满的结束了。

记得小学的时候爸爸买了一碟莫扎特的交响乐,有很多时候都是听着那交响乐睡觉,从那时候起我就非常喜欢古典音乐,也参加小学的军乐团学会了吹单簧管(不过现在早已忘记的差不多喽)。但是竟然今年才注意到“维也纳新年音乐会”!那是一次与万子钰闲聊得知的,于是下定决心这次一定不能错过。看完整个音乐会,我像是从音乐中看到了整个西欧的文化(我当然知道一个音乐会所包含的信息与西欧文化相比实在太少,我只是通过过度夸张来表现我的感受XD),深深切切的感受到了浓郁的欢度节日的风情——典雅、传统、幽默、活泼!

一篇文章

Standard

从三皇五帝、苏美尔人、古埃及人开始,人类到现在已有上千年的文明历史,人们始终没有停下对世界规律的追寻和思考,我们现在享受着的科学技术、依赖着的文化传统无不是先人靠努力耕耘、用智慧创造的结果,而这一切,与数学哲学密不可分。

这里所说的“数学”远远不止于人们印象当中的“数学”,人类的数学在漫长的发展中逐渐脱离了“数字”本身,研究的内容越来越抽象,越来越普适,数学早已从研究解决算术问题演化成了描述世界规律的宏大学科,我们用习得的数学知识预测未来、生产创造、管理人类复杂的社会…可以说没有数学的发展,我们的社会将会停滞不前。

我认为人类的数学就是我们自己思考方式的体现——世界原来并没有“一个两个三个”这种概念,我们按照一定的方式把物质世界的物品映射到一个抽象世界——当你认为你看到两个物品的时候,就是将你看到的东西抽象成了“2个”这个只存在在脑中的概念,当你比较两个东西的时候也是把要比的东西抽象成了大小、长短这种概念之后按照先前建立的法则进行比较,这些概念在物体本身上并不存在。所以我对那个争论已久的问题——“是人类发明了数学还是发现了数学”的回答是:是我们发明了数学!事实上我认为我们认识到的一切都在我们的身体里,脑中的结构是我们将接受器官收集到的外部的信息的一种映射,所以我们认知的事物实际上是人体内的一部分,思考和计算则是按照一定的算法将这些结构得到的信息融合、映射成新的结构。

我对一切事物都感到好奇,包括历史地理经济政治等等被称之为“文科”的学问,因为从这些东西当中也能发现很多我们思考的规则,但是人的一生实在有限,目前我认为能从现有的数学和理学中获得更多的启发,尤其是数学当中非常抽象的理念。

所以我目前以及未来很久的时间将主要思考前人遗留下来的数学知识、整理并加以补充。

 

这是专业导论课的论文