大学生活的乐趣不光体现在吃喝玩乐上，更重要的是它所提供的自由学习的场所。你可以在网上搜索课表，看看什么时候什么教室有什么牛B课，记在手机中的待办事项中，到时候到那个教室去旁听。旁听的乐趣就在于，你可以去学任何你想学的东西，不用交作业，不用怕点你名，不用记笔记，不用考试，只需要挂个耳朵在那儿听牛B东西就行了。前天一大早就被兔子叫起来，跟着一起去旁听了一节数理逻辑。
课程内容很简单，毕竟也才只讲了两周，一切都是很基础的。老师讲得很好，对联结词、命题公式、真值表等概念都说得很细致，即使完全没接触过这方面东西的人也能弄明白。作为信科的专业课，老师也简单提到了SAT问题：给定一串由AND, OR, NOT, 逻辑变量和括号组成的表达式，是否能给变量取值使得整个表达式为真？如果存在这样的“成真赋值”，我们就称表达式是一个“可满足式”。最简单的例子，p∧q就是可满足的，把p、q都取真即可；p∧(¬p)就不可满足，该式无论如何都为假。判断一个逻辑表达式是否可满足是一个经典的NPC问题，目前除了枚举之外还没有更好的算法。
还有一种逻辑表达式，不管初始值是什么，整个式子恒为真。例如，p∨(¬p)就是永真式。看起来，判定一个式子永真比判定一个式子可满足似乎要困难得多，因为前者比后者要强得多。而事实却是，这两个问题可以（在多项式的时间内）相互转化，它们在复杂程度上并无区别。如果你找到了一种可满足式判定算法，你便立即拥有了永真式判定算法。换句话说，你的算法若能找出一个成真赋值，你就能利用该算法立即得出该式所有赋值结果是否都为真。这个问题的问法很有艺术性，它有意屏蔽掉了永假式判定这一桥梁。事实上，一个表达式要么可满足要么永假，而从永假到永真只有一步之遥——只需要在最前面加一个“非”即可。也就是说，如果有一个程序，它能告诉我逻辑表达式A是否可满足，那么我就把¬A输进去：如果它说¬A不可满足，意即¬A的任何赋值结果均为假，反过来A就是永真的；如果它说¬A可以满足，意即程序找到了¬A的一个成真赋值，反过来便成为了A永真的一个反例。
随记
一个难看的证明和一个漂亮的证明
正逢考试周，抱歉这几天更新很慢。最近6天天天都有考试，今天上午考完英语后，终于有机会喘一口气了。下一次考试是后天下午的古代文学史，打算从明天开始借别人的笔记来背。今天下午先稍微休息一下。
前几天准备考离散数学时，烦躁得真想把课本撕了。北大出的那本《离散数学教程》是我所见过的最破的教材，里面频繁出现一些诸如假设m和n怎么怎么样结果推出了p和q怎么怎么样的印刷错误；在短短三页纸中，“Peano”被拼写错了四次，而且每次错的都不一样。
离散数学本身是相当科学的。离散数学中的证明，特别是图论证明，都是相当有趣的。但是，课本上的证明写得太丑了，符号和语言晦涩难懂，思维缺乏直观性和启发性。于是呢，我深刻体会到了这个Blog存在的必要性。我非常反对缺乏直观思维方式的证明过程。一个合格的教科书需要在严格的形式证明之外附上一段证明思路的直观描述。大家或许注意到了，我在写Blog时很不愿意定义变量，能用自然语言描述的地方就尽可能用自然语言来说。在介绍种种精妙的趣题和证明时，我往往会改变证明步骤的顺序和语言表述的方式，以顺应人的直观思维方式；否则，证明的巧妙性和启发性很难被表现出来。
Original Ideas
首先呢，小小的庆祝一下我的订阅数终于过千了。真可惜，昨天的订阅数1023，差一点就是1024了……
最近不知道为什么，思维特别活跃，脑子里经常蹦出一些牛B的想法。先声明，这篇文章为matrix67.com原创；谁要是用了里面的东西而没署名，或者拿去用作商业用途的话……Alan Shore的模样将会像幽灵一样缠绕着你，出现在你的每一个恶梦中。
关于输入法：为什么能打出“推倒”却打不出“推不倒”？
为什么没有输入法可以依据语法规则生成更多词组？例如，我可以把“睡觉”、“理发”、“洗澡”、“打球”、“吃饭”一类词做一个标记，那么在里面插入“了”、“过”等词也可以直接视为一个词（这些词同样很常用）。这样的话，词库容量大大扩充了，但这种方法本身并不耗费太多的空间和时间。
或者有输入法已经开始这么做了？大家的输入法中，这些词语可以直接打出来么？
睡觉 睡了觉 睡过觉 睡个觉 睡完觉 睡不成觉
理发 理了发 理过发 理个发 理完发 理不成发
洗澡 洗了澡 洗过澡 洗个澡 洗完澡 洗不成澡
打球 打了球 打过球 打个球 打完球 打不成球
吃饭 吃了饭 吃过饭 吃个饭 吃完饭 吃不成饭
事实上，这种结构能够派生出来的短语比你想像的更多，如“睡一睡觉”、“睡不睡觉”、“睡了一小时的觉”、“睡不完的觉”、“你睡你的觉去”、“觉也不睡”、“觉不好好睡”、”觉已经睡过了“等等；同时，这一类词的数量也相当多，漱口刷牙洗脸穿衣服穿鞋拿钥匙锁门开车上班写程序玩游戏下班回家做饭洗衣服上床做爱全是这一类词。因此词类标记的价值显得更大了。
又如，结果补语中间可以插入“不”、“得”变成可能补语。奇怪的是，为什么绝大多数输入法里都有“推倒”这个词，却没有“推不倒”这个词？这明明是在词库里做几个标记就能办到的事情。
推倒 推得倒 推不倒
吃完 吃得完 吃不完
学会 学得会 学不会
长高 长得高 长不高
飞起来 飞得起来 飞不起来
走进去 走得进去 走不进去
思考的乐趣：UyHiP趣题之用最少的块移动实现逆序操作
Michael Brand的Using your Head is Permitted是我最喜欢的谜题挑战网站，很多题目相当精彩。我已经多次翻译了那上面的谜题（点击这里看看）。不过，以往我都是静候月底释出答案，从来没有想过参与挑战。这个月的题相当诱人，只看题目描述的最后一句话我就知道这绝对是我喜欢的类型，于是我有了向本月题目发起挑战的冲动。印象中我真的是很久很久没有像这样疯狂地思考一个问题了。然后呢，我非常得意地告诉大家，哈哈~~~经过昨天一整夜的思考，我终于把它解决了！！于是赶忙写下我的解答过程，再三检查后发到了Michael Brand的邮箱。今天起床时收到了Michael Brand热情洋溢的回信，List of solvers也写上了我的名字，我很是兴奋。自我感觉这是一道非常好的题目，题目简洁有趣而有挑战性，解答本身并不难但也不太好想，很适合大家花一整天的时间仔细琢磨；因此这里也推荐给大家来挑战一下。解答不要发到下面的评论里，也不用发给我，直接发过去好了。期待过几天在List of solvers里看到大家的名字。
在这里简单翻译一下题目。对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。
Update: 为防止进一步讨论，我把评论禁了…
（召集）你喜欢什么类型的数字？
似乎大多数人都喜欢整十整百的数，或者偶数，或者一些因子很多的合数。但我却不一样。我反而讨厌那种整十整百的数。总的说来，我喜欢以下三类数字。
最喜欢的是质数，特别是以3和7结尾的。我的网名是matrix67。我的幸运数字是23。在家时我喜欢吃13个饺子。看电视时，喜欢把电视机音量调节到11、17、23（原来的老电视）或者47、53（新的那台电视）。选手机号时喜欢选奇数结尾的，最好末两位是质数。
第二喜欢的是36, 48, 96, 192一类的数，就是可以表示成两个2的幂之和的数，特别是2^(n-1) + 2^n一类的数（即质因子为n-1个2和一个3）。有时候，对这种数的喜爱甚至要多于2的幂，我也想不通是为什么。出OI题时我很喜欢拿这些数当数据。
第三喜欢的是奇数的幂，比如25、27、81、169、361、729等等。偶尔也把电视机的音量调到25或49。觉得361°的那个数字让人感觉很是亲切。
一直以为这是我独有的癖好，直到刚才看到了这位同志的日志后才猛然想到：难道所有Geek都有类似的癖好？故召集大家说一说自己对数字的一些偏好。
P.S. 另一个很有意思的癖好：别人问我时间时，我把手机翻出来看看，但很多时候并不会照着上面显示的时间念，而是有意在它周围取一个很“特别”的近似告诉对方。比如，8:47我会告诉他8点三刻，14:20我会告诉他2:22，16:18我会告诉他16:16，12:35我会告诉他12:34。
不行了，我要睡了。大家下午见。