在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
    古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296...  这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 - a^2 - b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 - (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
    古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：

2      0; 30
3      0; 20
4      0; 15
5      0; 12
6      0; 10
8      0; 7, 30
9      0; 6, 40
10     0; 6
12     0; 5
15     0; 4
16     0; 3, 45
18     0; 3, 20
20     0; 3
....    ....

    
    古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。


    古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：

  46 x 22 = 1012
   1   22
   2   44     44
   4   88   + 88
   8  176  + 176
  16  352
  32  704  + 704
          -------
            1012

    上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
    无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。

  46 x 22 = 1012
  46   22
  23   44     44
  11   88   + 88
   5  176  + 176
   2  352
   1  704  + 704
          -------
            1012

做人要厚道
转贴请注明出处

    Morpion Solitaire是一个非常简单的单人棋类游戏。游戏开始前棋盘上摆好了36个棋子，这些棋子排成一个空心的十字架形。以后你放上去的每个棋子都必须和已有的四个子连成一条线（左图所示，就像五子棋那样）。唯一需要注意的是，同一个棋子在同一个方向上只能使用一次（即同一方向上的连线不能重叠，否则你就可以一条直线无限摆下去了）。每放下一个新的棋子你就得到1分，再没有新的棋子可摆时游戏结束。
    人们开始好奇，游戏最多可以走多少步。上面的右图一共走了68步，这个记录从99年开始一直保持了7年，直到06年才有人改进到了74步。最近，又一个新的记录诞生了，有人找到了一种79步的解法。它的解法如下图所示：
  

    这个游戏看似简单，但你真正玩一下你会发现游戏变化莫测。很可能这一次你走了60多步，但下一次你却只能走40多步。这是一个打发时间的绝佳方法，仅仅需要一张纸和一支笔就可以混过大半节古代汉语课，没准一不小心就破了世界纪录。有兴趣的话不妨也写个程序来搜索一下，看看你的程序能不能跑出一个80的解来。目前解的上界是141，下界是79，任何改进都可以发信到这个页面里的电子邮箱。

    这个游戏的另一个版本则是要求构造新的连线时已有的四个子中任两个都还不曾连接过（而不是同一棋子同一方向只能用一次），你可以在这里玩到一个在线的Java版本。这个版本更是变化多端，运气不好只能走出40多步，RP爆发可以超过150步，目前已经证明的上界则是324步。如果你能走到160步，你可以联系这里给出的邮箱地址（为什么我要翻墙才能看到这个页面？）。目前的最好记录是170步，如下图所示：
  

    图灵机是1936年Alan Turing提出的一个计算机模型。这种计算机由一个一维数组（或者叫磁带）构成，还有一个可以左右移动的指针。磁带上每个格子里都有一种颜色（共可从m种颜色中选择），指针本身则可以是n种状态中的一种。给定一个m*n的表格，你就定义了一个图灵机。这个表格告诉机器，如果当前指针的状态是x，它所指的格子的颜色是y，那么下一步机器应该把这个格子染成什么颜色，然后指针应该左移一位还是右移一位，指针的新状态又是什么。有了一个图灵机后，我们便可以把它当做一个计算机进行数据处理了。我们可以给这个图灵机编写一个初始状态（也就相当于现在所说的程序和数据），让它按照这个表格不断执行下去，对数据进行处理并“输出”适当的结果来。
    能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。不是所有的图灵机都是通用的：很多图灵机只能完成一些特定的运算，而只有通用图灵机才能完成更一般的操作，是一台“通用的”机器。这些通用图灵机就像现代计算机一样，可以用来编程执行各种各样的操作，能实现现代计算机的各种功能。我们经常说一种程序语言是图灵完全的(Turing Complete)，指的就是这种语言等价于通用图灵机，能够执行任何一种复杂的数学运算。
    50年代起，科学家们疯狂地寻找通用图灵机，所需要的颜色数和状态数越来越小。最好的结果是1967年由Marvin Minsky得到的，他发现了一个7,4通用图灵机，即一个只需要7种状态，4种颜色的通用图灵机。人们开始好奇，最简单的通用图灵机是什么样子的。2002年，Stephen Wolfram（没错，就是MathWorld的那个Wolfram）做出了一个重大的突破：他发现了一个2,5通用图灵机，并且给出了一个很可能是通用图灵机的2,3图灵机。很早以前人们就证明了，不存在2,2的通用图灵机；因此如果Wolfram提出的2,3图灵机是通用图灵机的话，它就是最小的通用图灵机了。但Wolfram始终不能证明这个2,3图灵机是通用的，于是在今年三月份用25000美元悬赏征解。
    昨天，英国伯明翰大学的一名20岁在校大学生Alex Smith提交了一篇55页的论文，证明了Wolfram的2,3图灵机与另一个已知的通用机器等价，从而证明了2,3图灵机是最简单的通用图灵机，证实了这个很早就已经提出的猜想，解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破，无疑是信息学界中的一件激动人心的大事。

做人要厚道 转贴请注明出处
新闻来源：来源1 来源2

    最近，波士顿Northeastern大学的计算机科学家Daniel Kunkle证明了任何一个魔方可以在26步以内解开。这个结果打破了以往所有的记录。在解魔方的处理过程中，他构造了一些非常具有启发性的算法，这篇文章将简单地介绍一下这些算法。
    一个魔方大约有4.3 x 10^19种可能的初始状态，再牛的机器也不可能搜索完所有的可能。因此Kunkle和他的指导员Gene Cooperman想出了一些对魔方状态进行分类筛选的策略。
    Kunkle和Cooperman首先运用了一个小技巧将问题进行简化。如果魔方的每个面全是一种颜色，我们就认为魔方被解开，不管哪一面是哪一种颜色。换句话说，相互之间可以通过颜色置换得到的初始状态都是等价的。这样，“本质不同”的初始状态就减少到10^18种。
    接下来，他们开始观察一类更简单的问题：如果只允许180度转动(half-turn)，有多少状态可以被解决。在10^18种状态中，只有大约15000种状态可以仅用180度旋转来破解。对于普通计算机来说，这个数目也不大，只需要不到一天的时间就可以搜索出解开所有15000多个魔方各自需要的最少步数。他们发现，这类初始状态中任何一个都可以在13步以内解决。
    然后他们需要做的就是找出，需要多少步才能把任意一种状态转化为这15000种特殊状态中的一个。为了完成这一工作，首先他们把所有的初始状态划分为若干个等价类，每个等价类里的状态都可以仅用180度转动互相得到。这样，同一个等价类中如果任一状态可以变换为其中一种特殊状态，同样的转动步骤也可以使该等价类的其它所有状态都变成特殊状态。最后他们找到了1.4 x 10^12个不同的等价类，需要解决的状态数由最初的4.3x10^19减少到1.4x10^12。但无论如何，10^12仍然是一个恐怖的数字。
    现在他们用了一台超级计算机来完成这个工作，并且使用了一些很有技巧性的决策来加速搜索过程。计算机需要耗费大量的时间读取硬盘上的数据，为了加快速度，Kunkle和Cooperman将数据巧妙地进行了处理，使得数据的排列正好与计算机读取的顺序相符，这样就节省了搜索硬盘的时间。
    “这种方法可以应用在任何一个组合问题上”，Kunkle说。他提到了西洋跳棋、国际象棋、航班安排和蛋白质摺叠等一系列问题。一种类似的组合学方法最近被用于寻找西洋跳棋的最优策略中。
    63小时的计算后，超级计算机得到的答案是，任何一种状态都能在16步以内转化为15000种特殊状态。而这些特殊状态又只需要13步达到最终状态，因此这种方法最终得到的结论是：29步以内可以解决任何一个魔方问题。
    但这个数字还不足以创造出新的记录，去年瑞典就曾经得到过27步内解决魔方问题的结论。Kunkle和Cooperman意识到，要想打破这个记录，他们还需要削减3步才行。
    应用他们现有的算法，只有8x10^7个状态集合还不能做到26步以内出解。再次对这些相对较少的状态进行搜索，最终他们找到了26步以内解决所有魔方的方法。
    7月29日他们在ISSAC(International Symposium on Symbolic and Algebraic Computation,国际符号和代数计算会议)上公布了这一结果。
    现在Kunkle和Cooperman希望把最大步骤数减少到25。他们认为他们可以对所有需要26步的状态进行暴力搜索来寻找更优的方案。
    虽然他们已经获得了很大的成功，但这一结果很可能还有改进的空间。许多学者认为20步以内足以解决任何魔方，但现在没有人能够证明。

Matrix67翻译，原文地址
做人要厚道，转贴请注明出处

注：本日志请勿转载！

    我的第一篇日记是这一年的7月10日写的，因此这一年的5月16日具体发生了什么我已经忘记了。直到看到了这一年的年度总结，我才想起这一天是如何度过的。在04年的年度总结中，我写到：

    年初，我的第一次恋爱（与ZJ）因我的过分要求和渴望、学习压力、突发事件等各方面原因而渐渐走向危险的一端，酝酿半年的感情灾难在5月份突然爆发，一年历程的感情抛物线在2003年12月31日走到最高点，在2004年5月16日落在了x轴下方。2004年5月16日，我的16岁生日的晚上22:20，我到了ZJ的楼下疯狂地呼唤她，幻想能听见她的回答。此后，我俩有意回避，直到她和我进入不同的高中。

    很遗憾，至于那天以及那天的前后到底发生了些什么，上述文字是我唯一能记起的东西。我记得我下了晚自习后快速跑到她回家的必经之路，但却没有等到她。等她的过程中我遇见了另一个同学（忘记是谁了）。后来我沿路返回，又选了另外一条路跑到了她家楼下。很久以后某天我因别的事走过与这完全相同的路线，才发现当时我跑过的路有多么长。很多人说失恋那天会下雨，这是不正确的。我记得那天没有下雨。
    根据一项不完全统计，痴情的我似乎以后注定要踏上OI之路。

    05年10月11日前日记都是在我的PDA上写的，使用的DayNotez软件。10月11日那天在学校大礼堂观看英语歌比赛时PDA撞在了椅子的金属支架上，完全坏了，此后自己用Delphi写了一个程序继续在电脑上写日记。再后来我成功抢救回了PDA上的旧日记，但有一段日记少了几个字节，这段日记包括这年5月16日的日记。
    在这篇不完整的日记里，我看到我当天起床后的第一件事是上网更改了QQ资料的年龄。这是我最后一次更改QQ资料，一个多月后我就放弃QQ开始使用MSN了。当天上午的数学任课老师发生了变动。中午妈妈送了贺卡和一块小蛋糕。下午某个可能是来上门推销的工作人员在我们班的教室安装了一套非常破的英语教学软件，作为教室电脑的管理员我整理了很久。当时我是地理科代表，正负责收书费。到了晚自习时钱仍没有收齐，自己垫钱交给了地理老师。
    晚自习看了科幻世界的一篇文章，王晋康《一生的故事》。它比起《Stories of Your Life》差远了，但我觉得WS可能会喜欢这样的软科幻。于是跑到11班教室去，把这期的科幻世界给她，推荐她看这篇文章，并在里面夹了一张纸条说想请她周末看电影。下了晚自习后我出去在校门口的小书店买了《月亮孩子》。印象中这本书我没有看完，因为我后来渐渐不喜欢看科幻小说了。日记中我写道，WS和DQ没有送我生日礼物。WS和DQ是我认识的好朋友，属于非常少有的那种很感性的女生。她们没有送我生日礼物的唯一可能的原因就是忘记或记错了我的生日。后来我告诉她们我的生日已经过了，20日她们合送了一件短袖T恤。月底我开始喜欢上DQ，年底分手，分手那天的感情记录在了这里。DQ喜欢用23这个名字，因为她的名字中有个字写出来很像数字“23”。
    日记的最后我简单地写道：“晚雨，思ZJ”。那天下了晚自习后我淋着雨站在ZJ经常出现的地方，有一种她似乎随时会出现的感觉。耳边隐隐约约听到她的声音在说，你怎么又没带伞。日记中类似的语言是最后一次出现了。曾经有人向我倾诉说他逃脱不了失恋的阴影，怎么也忘不了那个她。我告诉他，失恋的阴影消失得比你想象中的快，一年以后你将很难再想起她来。
    这可能是我心理最复杂的一个生日。

    这一天离我后来完全停课的时间恰好一个月。谁也没有想到我在这个班级只剩30天的时间了。
    日记的第一句话是“生日，无感”。和前一年恰好相反，人生最重要的一天里我竟然没有任何感慨。若不是我早上来到教室发现桌子上有一颗糖，那天我将永远不会意识到我是在度过我18岁的生日。直到现在我也不知道，那颗糖是谁放在我桌子上的。这个细节我可能永远也忘不了，或许在38岁，48岁时我还会在想当初究竟是谁送了我这个小礼物。除此之外我当天没有收到任何礼物。
    那天我和数学老师讨论了一下第二天公开课的事情，因为我要帮忙制作教学课件。下午年级需要选送一个十佳学生报上去，年级主任把我和班上的一个女生叫到了办公室。我当场把机会让给了那个女生。我只在竞赛方面得过几个破奖，然而她的文艺、主持、英语等各方面能力让她小有名气。下午三四节课年级组织看电影《雷雨》，以配合几天后的语文教学。那一个多小时我一直在睡觉，甚至还梦到了一道OI题。后来语文课上老师叫大家谈《雷雨》观后感时我什么都说不出来。
    这一天是星期二，星期二的晚上有历史听写和新的一集24。晚自习的听写我挂得很惨，这天的24倒是不错。这一年是我第一次追美剧看，原来都是下载的已经结束的剧集。这天的24已经是第五季快结束了，回想一下这个学期竟是每周一集的24陪伴我度过的。

    大家或许会注意到，在这个Blog的标签里，所有以某个人作为标签的算“小猫”最大，这个名字也在友链中排第一。不知道为什么，我对这个矮矮的小女生有一种特别的感觉，直到今天。在手机里，短信数和通话时间最多的应该就是和她了。在这一天，她和我开了一系列让我恼火的玩笑——把我的手表藏在教室里的某个角落让我找。我至今仍不知道她在这一天玩这样的游戏代表什么意思。或许是我自作多情吧，有时女生的一个随意的动作也可能会让我猜想她有没有什么意图。我竭力想装作自己对某些东西看得很轻，然而实际上陷得最深的往往就是我。

    05年的9月份我开始每天记录一个词语作为当天的“单词化日记”。这个想法可能（我也忘记了）是来自安妮宝贝的一本书的彩页，上面是一张张日历，每一天的格子里都写有一个词。虽然我喜欢这种日记形式，但我仍然巨讨厌安妮宝贝这种小女生看的东西，也很不喜欢被她这些东西搞得神经兮兮的女孩子。我很高兴看到很多网友也在进行这种“单词化日记”形式的记录。任何一件事持久做下去都是有意义的，最终会获得好评，比如那个每天照大头像照了几年的人。
    这一天的单词是“暴光”，因为我的MSN Space（那时我在用MSN Space）被一中的同学发现了。OIBH上的很多重庆的OIer，还有我的很多老同学（包括ZJ）都在一中，Blog的读者将很快不再限于我们学校的OI组和班上的同学。从这次“暴光”开始，我的Blog里个人的东西慢慢地少了，日志内容也开始面向更多的OIer。年底我申请了付费空间和国际域名，搭建了私人Blog。很多人写Blog是越写越觉得没劲，但我坚持了下来，这个Blog已经快要两岁了。
    这篇日志就是生日那天我在MSN Space上写的日志。日期是17号可能是因为我是凌晨写的。从这篇日志来看，我的18岁生日是非常普通的一天。

    凌晨2:00。
    我把所有的灯都关了，一个人躺在沙发上，望着漆黑的天花板，iPod里放着S.H.E的新专辑。眼角流出两滴眼泪，并不是因为我伤心，而是因为我困了。但我不想睡觉。这一年我做的最多的事情就是睡觉了。
    前天我回了一趟学校，高三年级要照集体照留念。遇见了理科班的那一帮兄弟，大家仍然是开玩笑地疯打了一会儿。但我悲哀地发现，我几乎无法和我们班的同学交流了。除了四五个要好的朋友外我没有和我们班其他人打招呼。我甚至发现我已经认不出一些同班同学了。
    脱离集体近一年让我真正体会到了什么叫孤独。和其它高三学生一样，我的“高三”心里也是阴暗的。我不能浪费了这些时间，于是我开始学语言，做网页，写文章。只要自己能忙起来就不会觉得孤独了。19岁生日之际，我组织了一次生日邀请赛充实了一下自己的生活，收到了有史以来最多的生日祝福。

    听完了，S.H.E的新专辑非常有个性。我从沙发上起来，打开电脑开始看新的一集Lost。其实这也不算新的一集，只是上个星期留下来的。上个星期比较忙，因此有一集Lost还没看。
    这一集Lost的主角是Ben，故事中穿插了几段Ben的回忆。这一集的故事时间正好是Ben的生日，而每一个回忆的片段都发生在Ben以前某个生日。他这一生的故事由这一串回忆拼凑了起来。很巧，今天也是我的生日。我突然想知道，我的前几个生日又发生了什么。具体我是什么时候记的日记我已经记不清了，可能16岁的时候已经在写日记了吧。16岁到18岁是成人的标志，是人生最重要的阶段，在这期间我到底做过什么？
    我翻看起我的日记来。眼前是许多一闪而过的片段。我曾经失恋，曾经淋雨，我也曾经快乐，曾经辉煌。我想起了一颗糖之谜，想起了糟糕的历史听写，想起了《雷雨》，想起了《一生的故事》……我决定写下我能记起的每一个生日里发生的事。现在我的日记有14.7万字。我希望当我的日记有100万字时我还能像今天这样书写我的故事。
    每个人都有自己的故事。


Matrix67原创
本日志请勿转载！

    想起写这个是因为小方的爸爸上课的时候提到了这个东西。他的说法有很多错误的地方。早些时候我对这个有过一些考究，想在这里写一下。
    这个问题最初发表在美国的一个杂志上。美国有一个比较著名的杂志叫Parade，它的官方网站是http://www.parade.com。这个杂志里面有一个名字叫做Ask Marylin的栏目，是那种“有问必答”之类的一个Q&A式栏目。96年的时候，一个叫Craig.F.Whitaker的人给这个栏目写了这么一个问题。这个问题被称为Monty Hall Dilemma问题。他这样写到：

    Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what's behind the doors, opens another door, say number 3, which has a goat. He says to you, "Do you want to pick door number 2?" Is it to your advantage to switch your choice of doors?

    这个问题翻译过来，就是说，在一个游戏中有三个门，只有一个门后面有车，另外两个门后面是羊。你想要车，但你不知道哪一个门后面有车。主持人让你随便选了一个门。比如说，你选择了1号门。但你还不知道你是否选到了车。然后主持人打开了另一扇门，比如3号。你清楚地看到3号门后面是一只羊。现在主持人给你一个改变主意的机会。请问你是否会换选成2号门？
    对于这个问题，Marylin的回答是：应该换，而且换了后得到车的概率是不换的2倍。
    这个回答引起了争议。大多数人不同意Marylin的回答。一时间，全国上下几乎所有人都在谈论这个问题，因为这个问题是非常吸引人的，它说起来很简单，很好懂，但想起来很麻烦。争执双方都有一套很完整的说法。至少10篇讨论这个的文章刊登出来，有些文章是相当长的。
    事实上，这个争论是毫无意义的。因为概率问题总可以通过多次试验得到近似结果。到底换了好不好做几次试验就知道了。意识到这一点后，搞电脑的开始编程，学校开始组织活动模拟这个游戏。为了让读者有一个满意的答案，Marylin给一位数学老师打了个电话，请求她帮忙做试验。不久，这位数学老师发过去了一个表格，上面记录了试验结果并且列出了所有的可能。这份表格明确地表明，换一扇门可以得到车的概率更大。与此同时，许多人也相继发布了他们的测试结果。这些试验结果使这一看上去荒谬的结论变成了无可争议的事实。最后，这个问题有了科学的解释。人们接受了这一观点。这个问题已经被解决，它已经不再有争议了。
    一个叫S.K.Stein的人写过一本书，名字叫Strength in Numbers。书里面谈到数学家们如何一步步解决问题的时候引用了这个Monty Hall Dilemma问题。他在书中这样说道：

    If, after thinking some more about the question, you still are not sure about the answer and are not ready to explain it, then do the following. (Keep in mind that just citing experimental data is not an explanation. The data may convince you that something is true, but they do not explain it.)
    Get one more canister and perform a similar experiment, using four canisters instead of three. Put a wad of paper in one canister. After your friend chooses a canister, look in the remaining three and show the friend two empty canisters. The friend then faces a choice between the two other canisters. Carry out the same experiments as before. Think over the results you get. What do they suggest? Do you see a way to explain what happens?
    Performing these experiments not only gives you some clues, it also slows you down from the common frenzy of everyday life, so you can focus on just one thing for a period of time.
    If you still do not see how to explain what is going on, then use ten can- isters. Put the wad in one of them. After your friend chooses a canister, look in the other nine. Show your friend eight empty canisters out of those nine and remove all eight. Again that leaves just two canisters. Conduct a similar experiment.
    I am confident that you will solve this problem, so confident that I do not include the answer anywhere in the book, not even in fine print upside down hidden in the back matter. You mill probably, along the way, calculate the fraction of times that switching will pick the car and the fraction of times that not switching will pick the car. Using these fractions, you will be able to explain the brainteaser completely. Then you will have to admit that you can think mathematically. You just needed the opportunity.

    简单地说，Stein想表达这样一个意思。他建议那些还想不到Monty Hall Dilemma问题的答案的人别忙用数学方法去解，先亲自做几次试验来进行一些感性的认识。叫一个朋友当游戏里的主持人，在三个罐子中的其中一个里放一个东西。多玩几次，用心体会。如果做了试验还没有启发，那么他提出了这样一个非常具有启发性的试验的变形：规则不变，只是把三个罐子改成四个罐子。你的朋友会在你选择了一个罐子后打开另外两个空的罐子，再问你是否换一个。如果还没有一点启示，干脆把四个罐子变成十个。如果你真这么做了还没有一点想法那你就彻底地傻了。想想看，假如游戏中三个门变成了十个门，随便选一个选中车的机会将更渺茫。在主持人打开了另外八扇有羊的门后，你不换你肯定傻了。要是是我，我肯定会毫不犹豫要求换成另一个门。是啊，随着羊一只又一只的跑出来，我肯定会越来越激动，心想，那剩下的那个门里肯定是车了。这里有一个很基本的想法：我开先如果选的羊，换了一下就变成车了；如果开先选的是车，换一个门就变成羊了。既然一开始选的多半是羊，我为什么不换呢？
    根据这个思想，我们得到：在Monty Hall Dilemma问题中，第一次选中车的概率是1/3，显然车在另一扇门的概率是2/3。因此，我换门将有2/3的几率拿到车，而不换则只有1/3的概率拿到车。
    这个问题到这里本来应该结束了，但还有一点疑问：为什么主持人打开一扇羊门会改变选择的几率？其实道理很简单，几率本身是没有变的，只是因为主持人在打开门时就有一个选择。这导致了可能的情况减少。
    还想不清楚的话可以看看这样一个问题，这个问题也是由于看似没有影响的条件发生改变而导致概率的变化：说左右各一个人，已知两个人中至少有一个女的，问右边那个是女的的概率是多少？下面给出一个条件：同样两个人中至少有一个女的，现在告诉了你左边那个是女的，那么现在右边那个是女的的概率又是多少？有变化吗？既然至少有一个女的，那么说了左边那个是女的为什么概率也会跟着变呢？
    Monty Hall Dilemma问题传到中国来要稍微晚一些，但也在各大论坛上引起争论。Monty Hall Dilemma这个名字的中文翻译有很多，多数都比较直观，如“羊与车问题”。对这个问题的分析在网上很多地方都有仔细的讲解，到处都找得到。这也是本文着重在介绍这个问题的提出和发展史的原因。

    做人要厚道，转帖请注明出处。

不管结果怎么样，这都是一个转折点，一个有必要记录一下曾经走过的路的转折点。

    2004年9月1日决定参加信息奥赛。
    2004年9月17日晚在阶梯教室上信息奥赛，简介奥赛内容，熟悉进制转换并接触Pascal语言。
    2004年9月29日初上Pascal。
    2004年10月16日下午2:30进行信息奥赛初赛。
    2004年10月27日知信息奥赛初赛成绩。获初赛的三等奖，未进入复赛。因欲上信息奥赛，放弃数学奥赛资格。
    2004年10月28日下午报名正式参加信息奥赛培训。
    2004年11月27日引入数组，难度稍增。
    2004年12月4日指出Zlaner公布的书上习题源程序的错误，引起Zlaner的重视。
    2004年12月5日第一次感到视力下降。
    2004年12月22日试做NOIP2004的题，第一题AC，第二题有思路。
    2004年12月22日继续做NOIP2004的题，合并果子冒泡小数据AC大数据TLE，合唱队形穷举小数据AC大数据TLE。
    2005年1月15日下午信息奥赛上机考试，要求3小时完成4道编程题。4道题分别为数字黑洞、圆环找数、稀疏矩阵和删数游戏。一个半小时全部完成，第一个提前离开考场，赶去和尚静雪、杜巧编排《树人》的目录。
    2005年1月18日知15日考试成绩。最后一题忽略了前导“0”的情况，与嘎嘎并列第一。
    2005年1月29日寒假信息奥赛培训。
    2005年2月2日寒假信息奥赛培训结束。
    2005年2月28日接触Delphi。
    2005年3月2日讲到二叉树，第一次出现了听不很懂的情况。
    2005年3月23日信息奥赛考试，以初赛方式（程序阅读和完善，笔试）进行。
    2005年4月5日开始做TJU。
    2005年4月13日听学校“几何学在并行计算机中的应用”的讲座。
    2005年4月22日建立重庆八中信息奥赛QQ群。
    2005年5月11日发明针对评测系统漏洞的“万能程序”。
    2005年5月13日信息奥赛课后送王雪乔回寝室。
    2005年5月30日信息奥赛课上抢王雪乔饼干吃。
    2005年6月17日晚信息奥赛考试，3小时5道题，结果普遍很差，多数因文件读写错。
    2005年6月24日动态规划上手。
    2005年7月1日因与暑期信息奥赛培训冲突，放弃《三星智力快车》节目录制机会。
    2005年7月11日暑期信息奥赛培训。
    2005年7月24日信息奥赛考试。
    2005年7月25日参加巴蜀中学市NOI集体培训，全天课程持续6天。接触C语言。
    2005年7月30日巴蜀中学市NOI集体培训结束，中午吃自助烧烤，下午集体逃课回家。
    2005年8月27日开学前信息奥赛集训。下午信息奥赛考试。
    2005年8月28日MSN大流行。
    2005年9月26日研究最大匹配问题与匈牙利算法。
    2005年9月28日“是男人就撑20秒”过一分钟。
    2005年10月3日假期信息奥赛集训。
    2005年10月5日连续三天考试，每天一套题。成功破解教师机各密码。
    2005年10月6日再考一套题。火拼泡泡龙大流行。
    2005年10月8日讨论强题——登山机器人。
    2005年10月9日摆脱Zlaner，开始进行自发探索研究。研究并查集和树型动态规划。
    2005年10月14日被迫开始写笔记。
    2005年10月15日信息奥赛NOIP2005初赛。
    2005年10月17日起每天下午都有奥赛培训。
    2005年10月21日做NOIP2003试题。
    2005年10月23日网上模拟赛。发明用rewrite修改C:\windows\notepad.exe等文件的病毒。
    2005年10月25日信息奥赛考试。
    2005年10月26日给李芮简介信息奥赛内容。
    2005年10月29日年级针对信息奥赛采取停课停考政策。下午信息奥赛考试。
    2005年10月30日开始停课搞信息。
    2005年11月3日讨论KM算法。 <---这就是传说中的“KM之夜”
    2005年11月9日TJU的Zroge生日邀请赛。
    2005年11月10日挑战小木棍一题。
    2005年11月11日第二次停课集训开始。
    2005年11月12日网上同步模拟赛。
    2005年11月13日又一网上模拟赛。研究NP问题。
    2005年11月14日强题——Expression。
    2005年11月15日研究凸包。
    2005年11月16日官方发布题目名称。开始猜题。
    2005年11月17日下午集体活动放松，打羽毛球。晚集体外出吃火锅。
    2005年11月19日NOIP2005。
    2005年11月21日信息奥赛结束，恢复正常上课。课程进度严重落下。
    2005年12月6日研究程序算法的不可能问题。网上买的黑书送到。
    2005年12月7日开始看黑书。
    2005年12月11日研究杨式图表、Catalan数列、错排公式、极限、导数。
    2005年12月12日研究Ramsay问题、数论、群论。
    2005年12月18日全国划线。
    2005年12月21日NOI官方网站一等奖获奖名单放出。
    2005年12月23日研究简单的计算几何。做去年选拔赛的Newyear，小数据AC大数据TLE。
    2005年12月24日买《算法导论》。
    2005年12月25日研究矩阵。
    2005年12月30日聚餐七十二行。
    2006年1月1日研究微积分。
    2006年1月5日年级组建第二批信息奥赛团队。
    2006年1月7日Vijos。
    2006年1月10日放弃冬令营。
    2006年1月11日研究各种数列。
    2006年2月1日研究Pólya置换群定理等。
    2006年2月4日买《离散数学》。
    2006年2月7日Zroge大牛讲课。
    2006年2月11日信息奥赛模拟考试，Zroge大牛出题。
    2006年2月13日研究离散变换和反演。
    2006年2月14日研究计算几何等。
    2006年2月15日研究集合论、概率。
    2006年2月16日研究博弈论等。
    2006年2月20日开始直接用GDB命令调试程序。
    2006年2月25日重庆队选拔赛。
    ……
    XXXX年X月X日决定参加ACM团队。