2010/03/21 / BrainStorm
经久不绝的问题 洞穴奇案
美国著名法学家富勒在《哈佛法律评论》中提出了一个虚拟的人吃人案件，这个名为"洞穴探险"的极端案例被称为"史上最伟大的虚拟案例"。
案例简述：省略很多细节，推荐阅读富勒的原文THE CASE OF THE SPELUNCEAN EXPLORERS和中文Wiki版本，很详细。
因为其涉及到法律的"本性"，甚至是超出法理哲学讨论的范围，像放大镜一样照出了隐藏在道德、法律、规则、正义、文化和制度之间"剪不断理还乱"的紧密联系：
法律在何种条件下才能体现其本意? 在什么条件下牺牲某些人的利益以换取其他人的生存这种做法才能够被接受? 在利益冲突的时候，谁有权威仲裁利益双方行为的合理性? 法律、道德、正义的区别和联系? 在远离社会的自然状态下，社会的法律是否具有管制效力? 如果答案为否，那么当幸存者回到人类社会的时候，该社会的法律是否具有审判他们行为的"合法"权威?...
富勒还在案例后构造了最高法院五名大法官的五份判决意见，(二有罪二无罪一弃权，最高法院五位法官立场2:2的平局，意味着初审法院的判决得到维持，四名被告人被执行死刑)，总结出五种不同的法理观点，代表了法理哲学中的五个流派。每一种观点都振振有词，具有合法或者合理的逻辑基础。
1998年，美国法学家Peter Suber重提洞穴奇案。根据过去几十年法理哲学理论的进展，又增加了九名虚拟大法官(四有罪四无罪一弃权)，一共总结出14种不同观点。实际上，洞穴奇案至今也没有统一的答案。
PS: 历史上的两个真实案例：1842年美国诉霍尔姆斯案(United States v. Holmes) 和1884年的女王诉杜德利与斯蒂芬案(R v Dudley and Stephens)
案例简述：省略很多细节，推荐阅读富勒的原文THE CASE OF THE SPELUNCEAN EXPLORERS和中文Wiki版本，很详细。
引用
4299年5月上旬，在纽卡斯国，五名洞穴探险人不幸遇到塌方，受困山洞，等待外部的救援。十多日后，他们通过携带的无线电与外界取得联络，得知尚需数日才能获救，但水尽粮绝，为了生存，大家约定通过投骰子吃掉一人，牺牲一个以救活其余四人。威特摩尔是这一方案的提议人，不过投骰子之前又收回了意见，其他四人却执意坚持，结果恰好是威特摩尔被选中，在受困的第23天威特摩尔被同伴杀掉吃了。在受困的第32天，剩下四人被救， 随后他们以故意杀人罪被起诉，初审法庭经过特别裁决确认上面所述的事实，根据《刑法典》规定："任何故意剥夺他人生命的人都必须被判处死刑。"法官判定四位被告谋杀威特摩尔的罪名成立，判处绞刑。
因为其涉及到法律的"本性"，甚至是超出法理哲学讨论的范围，像放大镜一样照出了隐藏在道德、法律、规则、正义、文化和制度之间"剪不断理还乱"的紧密联系：
法律在何种条件下才能体现其本意? 在什么条件下牺牲某些人的利益以换取其他人的生存这种做法才能够被接受? 在利益冲突的时候，谁有权威仲裁利益双方行为的合理性? 法律、道德、正义的区别和联系? 在远离社会的自然状态下，社会的法律是否具有管制效力? 如果答案为否，那么当幸存者回到人类社会的时候，该社会的法律是否具有审判他们行为的"合法"权威?...
富勒还在案例后构造了最高法院五名大法官的五份判决意见，(二有罪二无罪一弃权，最高法院五位法官立场2:2的平局，意味着初审法院的判决得到维持，四名被告人被执行死刑)，总结出五种不同的法理观点，代表了法理哲学中的五个流派。每一种观点都振振有词，具有合法或者合理的逻辑基础。
1998年，美国法学家Peter Suber重提洞穴奇案。根据过去几十年法理哲学理论的进展，又增加了九名虚拟大法官(四有罪四无罪一弃权)，一共总结出14种不同观点。实际上，洞穴奇案至今也没有统一的答案。
PS: 历史上的两个真实案例：1842年美国诉霍尔姆斯案(United States v. Holmes) 和1884年的女王诉杜德利与斯蒂芬案(R v Dudley and Stephens)
2009/02/15 / BrainStorm
情人节特别课堂: 稳定婚姻问题
趁着情人节的气氛，给大家介绍一个有趣的问题：稳定婚姻问题，青春期的GGMM一定要看...hehe会有收获的^^
这个问题曾在一个OIER的空间里看到过，他讲得是班级的男女生谈朋友的配对==....其实就是这个问题，可惜现在找不到那个空间了orz...不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题，于是自己修改了下，来给GGMM们上课啦，有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗)，也推荐青春期的GGMM去受教~~)
稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的，这个问题和图论有关(求完全二分图的稳定完备匹配，这是一个NP问题)。对于以前没有接触过这个问题的人，这个理论最出人意外的结论是：传统的求爱、结婚过程是male-optimal(男生主动)的，也就是说，男性能够得到尽可能好的心上人，女性却不然。这里我们就不科普了，直接上问题：
对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身，而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)。
激动人心求婚过程是这样进行的(如果觉得太快了的话，那就认为是表白吧)：
第一天，让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了，不要着急，表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友)，然后，等所有单身男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的，不要犹豫，换之。等到尘埃落定之后，再开始如上所述的新的一轮表白。
依此类推。可以证明的是，这个过程一定是会终止的，也就是说，不会陷入任何死循环。并且一旦终止，每个人都会找到一个伴侣。更关键的是，这个过程最终得到的一定是如前所述的“稳定组合”。
真正有趣的部分还在后面。
阅读全文
这个问题曾在一个OIER的空间里看到过，他讲得是班级的男女生谈朋友的配对==....其实就是这个问题，可惜现在找不到那个空间了orz...不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题，于是自己修改了下，来给GGMM们上课啦，有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗)，也推荐青春期的GGMM去受教~~)
稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的，这个问题和图论有关(求完全二分图的稳定完备匹配，这是一个NP问题)。对于以前没有接触过这个问题的人，这个理论最出人意外的结论是：传统的求爱、结婚过程是male-optimal(男生主动)的，也就是说，男性能够得到尽可能好的心上人，女性却不然。这里我们就不科普了，直接上问题：
引用
给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序(无并列)。具体点说就是每个男生都凭自己好恶给MM排个名次：我最爱a，其次爱b，再次爱c...同样，每个MM也同样给每个男生打分。
问题1：是否存在一种男女配对组合构成一种稳定的组合关系? 稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
问题2：在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式?(如果它存在的话)
问题1：是否存在一种男女配对组合构成一种稳定的组合关系? 稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
问题2：在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式?(如果它存在的话)
对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身，而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)。
激动人心求婚过程是这样进行的(如果觉得太快了的话，那就认为是表白吧)：
第一天，让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了，不要着急，表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友)，然后，等所有单身男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的，不要犹豫，换之。等到尘埃落定之后，再开始如上所述的新的一轮表白。
依此类推。可以证明的是，这个过程一定是会终止的，也就是说，不会陷入任何死循环。并且一旦终止，每个人都会找到一个伴侣。更关键的是，这个过程最终得到的一定是如前所述的“稳定组合”。
真正有趣的部分还在后面。
阅读全文
2009/02/05 / BrainStorm
昨天OIBH上火爆讨论的某概率题
昨天OIBH上一帖so为火爆，不到24小时里就有30楼，300+回复，罪魁祸首就是这道问题： 有A,B两孕妇,已知其中一个怀的是男胎,求生出一男一女的概率 (自己测测对概率的感觉^^)
里面的辩论可真是"激烈"，精彩无处不在orz...(阿拉潜水的飘过)有随机统计结果，有认为题意不明的，有讨论语文水平,IQ的，有搬出生物学多胞胎观点,"Y染色体比X染色体稍微轻一点，所以带Y染色题的精子也会稍微游得快一点"什么都有，囧..."理论代替不了实际""人为和自然"都出来了，最后得到"哲学"的升华...题目,答案是不是假设?
LK大牛: "这是一个假设...."
wy: "整道题目，包括所有答案，都是假设..."
LK大牛: "题目是假设，答案是假设情况下的真理..."
wy: "就连概率本身，也是一个理论、假设。是假设，就和实际有偏差；真理，建立在实际之上；假设下的完全真理，是不存在的..."
难为了大牛了，讨论激烈的地方肯定有学过概率的和没学过概率的人同时存在。真是现在一年一个代沟阿...还是OIer文化课水平...
答案其实是2/3...为什么呢?
组合一共就有4种：男男/男女/女男/女女
已知其中一个怀的是男胎，所以女女不符合题目要求，所以一共有3种合法的组合，2种符合题意...
学过概率的知道有"条件概率"这回事，专业点的解法是这样。
A事件表示两个孕妇分别生一男一女，B事件表示两个孕妇中有一个生男孩，P{A|B}=P(AB)/P(B)=(1/2)/(3/4)=2/3
同样的，我们知道投两个骰子出现的数字和大于10的概率是3/36，但如果事先就知道至少有一个骰子是6点，那么概率变成多少了(或变了没有)? 很显然，如果有一个骰子搞出那么大一个点数那概率肯定变大了。可大于10的情况只有(5,6)、(6,5)和(6,6)，它们本来就含有6阿，为什么概率变了? 其实是总的情况变少了：如果知道其中一个骰子是6点的话，情况数就只有11种了，就不是36种了，所以概率变成了3/11，大了不少。(摘自Matrix67's blog)
那一道算出1/2的估计就是没搞清楚"其中一个怀的是男胎"这一条件造成了组合的减少，或者搞在"男男"权重里的就没搞清楚概率==...
条件概率还有道有意思的Monty Hall Dilemma问题(话说monty hall不是张sc比赛地图么，激动，yy它们之间有什么关系?)，这道题目肯定都听说过，可能比较古董了，看到题目就知道了^^
对于这个问题，十年来涌现出了无数总也想不通的人。为了说服这些人，人们发明创造了十几种说明答案的方法，画表格，韦恩图，决策树，假设法，捆绑法....条件概率也可以解这个问题，我就不多说了，感兴趣的可以移步子宫67的文章~~
里面的辩论可真是"激烈"，精彩无处不在orz...(阿拉潜水的飘过)有随机统计结果，有认为题意不明的，有讨论语文水平,IQ的，有搬出生物学多胞胎观点,"Y染色体比X染色体稍微轻一点，所以带Y染色题的精子也会稍微游得快一点"什么都有，囧..."理论代替不了实际""人为和自然"都出来了，最后得到"哲学"的升华...题目,答案是不是假设?
LK大牛: "这是一个假设...."
wy: "整道题目，包括所有答案，都是假设..."
LK大牛: "题目是假设，答案是假设情况下的真理..."
wy: "就连概率本身，也是一个理论、假设。是假设，就和实际有偏差；真理，建立在实际之上；假设下的完全真理，是不存在的..."
难为了大牛了，讨论激烈的地方肯定有学过概率的和没学过概率的人同时存在。真是现在一年一个代沟阿...还是OIer文化课水平...
答案其实是2/3...为什么呢?
组合一共就有4种：男男/男女/女男/女女
已知其中一个怀的是男胎，所以女女不符合题目要求，所以一共有3种合法的组合，2种符合题意...
学过概率的知道有"条件概率"这回事，专业点的解法是这样。
A事件表示两个孕妇分别生一男一女，B事件表示两个孕妇中有一个生男孩，P{A|B}=P(AB)/P(B)=(1/2)/(3/4)=2/3
同样的，我们知道投两个骰子出现的数字和大于10的概率是3/36，但如果事先就知道至少有一个骰子是6点，那么概率变成多少了(或变了没有)? 很显然，如果有一个骰子搞出那么大一个点数那概率肯定变大了。可大于10的情况只有(5,6)、(6,5)和(6,6)，它们本来就含有6阿，为什么概率变了? 其实是总的情况变少了：如果知道其中一个骰子是6点的话，情况数就只有11种了，就不是36种了，所以概率变成了3/11，大了不少。(摘自Matrix67's blog)
那一道算出1/2的估计就是没搞清楚"其中一个怀的是男胎"这一条件造成了组合的减少，或者搞在"男男"权重里的就没搞清楚概率==...
条件概率还有道有意思的Monty Hall Dilemma问题(话说monty hall不是张sc比赛地图么，激动，yy它们之间有什么关系?)，这道题目肯定都听说过，可能比较古董了，看到题目就知道了^^
对于这个问题，十年来涌现出了无数总也想不通的人。为了说服这些人，人们发明创造了十几种说明答案的方法，画表格，韦恩图，决策树，假设法，捆绑法....条件概率也可以解这个问题，我就不多说了，感兴趣的可以移步子宫67的文章~~
2008/07/21 / BrainStorm
Matrix67.com三周年精选回顾
matrix67大牛的blog今天三周年了~~这是他推出的三周年的精选回顾
全是精华阿
看看下面的这些文章，谁能看出这是个文科生(传说中去北大中文系泡妞?!)原文的地址: http://www.matrix67.com/blog/archives/558
1. 原创科普说明文：递归
假期的一篇作文，叫我们写任一说明文。我把这篇作文发到了我的Blog上。这可能是我Blog最早的技术文章，它确定了我以后类似文章的写作风格。
2. 非常奇妙的证明：图形必在格点之外
翻译的cut-the-knot上的一篇文章。这是我所见到的最elegant的证明之一，在饭桌上提到证明问题时我经常会举这个例子。几个好友很早就开始阅读我的Blog，他们一致认为这是最令人难忘的一篇日志。
3. 几个把平面几何问题的辅助线做到空间去的数学趣题
也是翻译的cut-the-knot上的系列文章，当时觉得确实非常神奇。后来的学习发现，其实射影几何中有更多有趣的例子。
4. 追溯羊与车：Monty Hall Dilemma问题的故事
我们数学老师提到了Monty Hall问题，他的说法是错误的，因此才写下这篇文章。当时写这篇文章主要是给我的同学看，因为那时这个Blog几乎只有我们同学才上。
5. 几个很强的数列
这是我在The On-Line Encyclopedia of Integer Sequences找到的，非常强。不是经常有考什么数列找规律的么？从这里面随便挑一个来，不查数列百科全书的话别人几乎不可能找出规律来。
阅读全文
2008/07/21 / BrainStorm
M12 Puzzle
这个游戏号称是魔方的平面版~~
游戏开始时图上会出现12个数字1-12, 点击“RANDOMIZE”开始游戏。我们要通过“INVERT”和“MERGE”这两种操作, 把这12个数字按顺序排列。如果点错了, 可以“UNDO”返回上一步的状况。实在玩不下去了, 还可以点击“RESET”回到顺序排列的界面。点一下按钮，就可以执行各种操作了。你还可以自定义一系列的操作组合比如M3IM2I（混插3次——颠倒——混插2次——颠倒）, 保存之后, 你可以在“CUSTOM”的下拉菜单里直接点击, 这样就可以轻松地完成一记“组合拳”。你可以在这里阅读原文~~
Play M12 Online: http://www.sciam.com/media/inline/2008-07/puzzles/m12.html
M12的解答在这里有讨论...这里就不说了,反正我是没想出来组合拳==...神奇
http://www.sudoku.com/boards/viewtopic.php?t=6149&start=0&postdays=0&postorder=asc&highlight=&sid=71eac44e4aa2be94bd29f7142b0720c8
下图所示为对顺序排列的数字分别执行两种操作后的结果:
加强版还有M24 Puzzle
在初始状态下, 1到23这23个数字像钟面上的数字一样排成一个圆圈, 而0则置于钟面上12点位置处的圆圈外侧。同游戏M12一样, 游戏M24的目标也是要把打乱排列的数字理顺。此游戏也有两种操作。一种操作叫做旋转, 你只须用鼠标拖拽（按住左键不放）圆盘顺指针和逆时针移动就可以了。另一种操作是“SWITCH”, 即将颜色相同圈内的两个数字的位置互换。同样, 你也可以自定义操作组合来简化操作过程。比如R5SL6（右旋5格——同颜色圈内数字交换——左旋6格）。
Play M24 Online: http://www.sciam.com/media/inline/2008-07/puzzles/m24.html
游戏开始时图上会出现12个数字1-12, 点击“RANDOMIZE”开始游戏。我们要通过“INVERT”和“MERGE”这两种操作, 把这12个数字按顺序排列。如果点错了, 可以“UNDO”返回上一步的状况。实在玩不下去了, 还可以点击“RESET”回到顺序排列的界面。点一下按钮，就可以执行各种操作了。你还可以自定义一系列的操作组合比如M3IM2I（混插3次——颠倒——混插2次——颠倒）, 保存之后, 你可以在“CUSTOM”的下拉菜单里直接点击, 这样就可以轻松地完成一记“组合拳”。你可以在这里阅读原文~~
Play M12 Online: http://www.sciam.com/media/inline/2008-07/puzzles/m12.html
M12的解答在这里有讨论...这里就不说了,反正我是没想出来组合拳==...神奇
http://www.sudoku.com/boards/viewtopic.php?t=6149&start=0&postdays=0&postorder=asc&highlight=&sid=71eac44e4aa2be94bd29f7142b0720c8
下图所示为对顺序排列的数字分别执行两种操作后的结果:
加强版还有M24 Puzzle
在初始状态下, 1到23这23个数字像钟面上的数字一样排成一个圆圈, 而0则置于钟面上12点位置处的圆圈外侧。同游戏M12一样, 游戏M24的目标也是要把打乱排列的数字理顺。此游戏也有两种操作。一种操作叫做旋转, 你只须用鼠标拖拽（按住左键不放）圆盘顺指针和逆时针移动就可以了。另一种操作是“SWITCH”, 即将颜色相同圈内的两个数字的位置互换。同样, 你也可以自定义操作组合来简化操作过程。比如R5SL6（右旋5格——同颜色圈内数字交换——左旋6格）。
Play M24 Online: http://www.sciam.com/media/inline/2008-07/puzzles/m24.html
