查看更多 »

    12. 两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
    答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。

while(!at_other_robots_start) {
  move_right 1
}
while(true) {
  move_right 2
}

    13. 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
      a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
      b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
    答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。

查看更多 »

    偶然进了这个页面，看到几个原来没见过的面试智力题。顺带也翻译一些比较少见、可能有人没见过的题目写在这里。有几个题目在国内流传相当广，什么n个人怎么分饼最公平，屋里的三个灯泡分别由哪个开关控制，三架飞机环游世界，用火柴和两根绳子测量45分钟之类的题目，火星得已经可以考古了，这里就不再说了。个别题目本Blog原来有过详细的介绍，这里也不再提了。

    1. 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
    答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。

    2. 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
    答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。

    3. 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，"abcdefg"移动3位就变成了"defgabc"）。
    答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。

    4. 一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
    答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。

    5. 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1x1的小巧克力？
    答案：N x M - 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M - 1次。
查看更多 »

    Stetson大学的一个非常可爱的MM（以后本Blog将简称她为Stetson MM）和我分享了一个很神奇的东西。她们正在做一个线性代数的课题研究，题目的大致意思是“用矩阵来构造分形图形”。Stetson MM叫我试着做下面这个实验：对于一个坐标点(x,y)，定义下面4个矩阵变换：
    
    然后，初始时令(x,y)等于(0,0)，按照 T1 - 85%, T2 - 6%, T3 - 8%, T4 - 1% 的概率，随机选择一个变换对该点进行操作，生成的点就是新的(x,y)；把它画在图上后，再重复刚才的操作，并一直这样做下去。我心里觉得奇怪，这为什么会得到分形图形呢？于是我写了一个简单的Mathematica程序：
list = {{0, 0}};
last = {{0}, {0}};
For[i = 0, i < 50000, i++, r = Random[];
   If[r < 0.85, last = {{0.83, 0.03}, {-0.03, 0.86}}.last + {{0}, {1.5}},
     If[r < 0.91, last = {{0.2, -0.25}, {0.21, 0.23}}.last + {{0}, {1.5}},
       If[r < 0.99, last = {{-0.15, 0.27}, {0.25, 0.26}}.last + {{0}, {0.45}},
         last = {{0, 0}, {0, 0.17}}.last + {{0}, {0}}
       ]
     ]
   ];
   list = Append[list, First[Transpose[last]]];
]
ListPlot[list, PlotStyle -> PointSize[0.002]]

    程序运行的结果真的是令我大吃一惊：竟然真的是一个分形图形！！我不禁再次对数学产生了一种崇敬和畏惧感！！

查看更多 »

    去年的一篇日志里曾经向大家提到了Smale球面外翻问题：在允许与自身相交的情况下，是否有可能无损地、平滑地、不留折痕地把一个球面的内侧翻到外面来。那篇日志里有一个视频，演示了球面外翻的其中一种解法，但没有再进行任何说明和解释。我曾在Google Video上找到了一段完整的视频，可惜Google Video不对中国大陆开放。当时我非常想看一看这段21分钟的视频，但尝试了各种方法都不行，其它地方也没有找到。今天听说中国大陆可以看Google Video的视频了，首先想到的就是去看这段视频。确实太精彩了！！你可以看到球面外翻问题有解的可能性，以及低维情形下（圆的外翻）为何反而无解。后面多个角度多种方式的动画演示足以让你完全理解这个外翻过程中的每个细节。从第11分钟开始的那个add waves则是整个视频的精华所在，太牛B了！

把地址给出来吧，如果上面这个看不了可以进这里面去看：
http://video.google.com/videoplay?docid=-6626464599825291409

    从古至今，尺规作图一直是数学中备受关注的一个问题。到现在，数学家们已经比较完美的解决了尺规作图的问题，指出哪些图形可以用尺规作图完成，哪些问题不能用尺规作图解决。Mohr-Mascheroni定理告诉了我们一个非常令人吃惊的事实：所有用直尺和圆规可以解决的作图问题，只用圆规也能完成。当然，只用圆规是画不出直线的；但我们可以认为，一条直线已经由两点确定，并不需要画在图上。数学家们向我们展示了：给定四个点，如何用单规找出它们所确定的两条直线的交点；给定一段圆弧和两个点，如何找出两点确定的直线与圆弧的交点。注意到这是直尺仅有的功用，用单规全部解决了后直尺也就不需要了。数学家们还研究过单尺作图：只拿一块直尺到处作直线交过来交过去的又能完成哪些作图问题。显然，只用直尺是不能开平方的，解析几何告诉我们直线与直线的交点只可能是各系数的一个有理表达，这决定了单尺作图不能替代尺规作图。Poncelet-Steiner定理告诉我们，假如事先给定了一个圆和它的圆心，以后只用直尺足以完成任何尺规作图能够解决的问题。这些将在我今后的《什么是数学》笔记中提到。
    昨天，网友浅海里的鱼跟我提到了锈规作图问题，这是我第一次听到这个神奇的东西。现在，假设我们没有直尺，只有一把生锈的圆规。圆规已经被卡住了，只能画出单位半径的圆。在这样的条件下，哪些作图问题仍然能够被解决？锈规作图相当的困难，但并不是没有可能。1983年，D. Pedoe教授惊奇地发现，给定两个点A和B，如果它们的距离小于2，我们可以非常简单地作出点C，使得AC = BC = AB（即△ABC为等边三角形）。

    
    先以A、B为圆心分别作圆。由于它们之间的距离小于2，因此两圆必然相交。以其中一个交点P为圆心作圆，分别交圆A、圆B于点M、N。最后，圆M和圆N的交点即为所求点C。由对称性，△CAB一定是一个等腰三角形。另外，由对称性可知∠ACB=2∠BCP，而圆周角∠BCP的角度又是圆心角∠BNP的一半。由于△BNP是等边三角形，我们可以立即得到∠ACB=∠BNP=60°，△ABC是一个等边三角形。
    D. Pedoe受到启发，提出了以下问题：任给A、B两点，只用锈规是否都能作出C使得AC = BC = AB？若干年后，侯晓荣等人巧妙地解决了这个问题，并以此为基础，借用复数运算等理论，得到了一个出人意料的结论：从给定两点出发，任何尺规作图能够完成的构造，只用锈规也能完成。只用锈规作等边三角形的方法相当精彩，我在这里详细地说一下。觉得牛B的话就在下面叫个“好”。
查看更多 »

昨天在deviantART里逛时还淘到了这张非常漂亮的图，我特别喜欢。和大家分享一下。
图片来源：http://tenshi-no-pocky.deviantart.com/art/calculus-53880878

查看更多 »