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次。
查看更多 »

    昨天本来写了很大一段文字的。经过再三的考虑，我还是决定删掉了和古汉MM及其现任男友相关的一些很纠结的文字。到底我写了些啥，大家自己YY去。
    长话短说，昨天上午发生牛B事儿了。有人发个短信来，问我参不参加ACM选拔赛。我以为是什么牛B人搞到我手机号码了呢，结果古汉MM来一短信，说他男友要了我的手机号来找我组队来了。本来一直在说，大学只在道上混，不搞ACM的；但当ACM真正来到我身边时，我开始犹豫了。有趣的是，若不是古汉MM她男友发短信来找我，我还真不知道有ACM选拔赛这回事。我在BBS上寻找今年ACM选拔赛的消息，开始盘算我还需要复习多少东西。找到了一份去年的题目，看见最后一道题名字叫“选课”，心想估计是那个著名的多叉转二叉。看来这个选拔赛的难度还是比较适中的。我在想，信科的竞赛班现在应该还不会涉及多叉转二叉的树形DP吧，那个信科的看到了肯定立马就愣了。我开始考虑是否需要另外找人组队，不要那个信科的了。然后我毫无防备地点开链接，“叭”的一声晕倒在地上：

Description
教务网站如期的在选课之日出问题了，这次的问题是登陆窗口的验证码无法显示了，同学们只能靠猜验证码来登陆选课。教务的登陆系统刚刚经过改进，改进后的验证码均为1..N的一个排列。一般的同学们在试验的时候都是按照所有排列的字典序逐个试验，但是TN发掘这样试验很乏味，所以他决定每次尝试前一个排列后面的第M个排列。
但是一段时间之后他发现，寻找一个排列后面的第M个排列并不是一件容易的事情，所以他希望你帮助他。
Input
Line 1： N (1 <= N <= 10000)
Line 2： M (1 <= M <= 100)
Line 3： 1..N的一个排列
Output
所求的排列

    看来，和传说中的一样，PKU的ACM果然抓得没有那么紧。我又开始犹豫，到底要不要去参加这个选拔赛，又要不要跟古汉MM的男友一起合作。如果有谁心烦了想虐题的，我负责去找些信科的作业来。
    大家上得了这个网页不？点那个“竞赛题目”进入愉快的虐题之旅吧。07年的那个页面貌似有几个死链。06年的题目很全，我在这里发一下。长期被题目虐？准备开始虐一下传说中PKU的ACM选拔赛吧。顺便给某个跟我说想学Computer Science的MM看看，信息学会涉及一些什么样的问题。
查看更多 »

    我承认我确实N久没更新了，整天写那个该死的现文史论文。昨天终于写完了，休息一下，今天又来更新~~
    中文系里的课程也有比较科学的，我觉得现代汉语是所有中文系必修课程中最科学的课。上学期讲完语音后，这学期进入了语法部分。我一直想写一点与语言学相关的东西，骗些理科小MM来这个专业玩。这里先说一些最近几次课上比较有趣的东西，一些比较系统的汉语语言学小知识留着以后再说吧。下次课我们可能还会学到一些类似的东西，到时候我接着在这儿更新。
    下面是一些有趣的题目，它们可以从另一个角度来考验你的思维能力。先不忙着看答案，看你能想出多少来。

1. 找一个动词，它前面不能加“不”
2. 找一个动词，它前面不能加“没”
3. 找一个动词，它前面既不能加“不”，也不能加“没”
4. 找一个动词，它后面不能加助词“着”、“了”、“过”
5. 找一个动词，它前面可以直接加“很”来修饰
6. 找一个形容词，它前面不能加“不”
7. 找一个形容词，它前面不能加“很”
8. 找一个形容词，它不能直接用作定语
9. 找一个形容词，它不能重叠使用（如“高高的”、“高高兴兴的”）
10. 找一个名词，它前面不能加数量词来修饰
11. 找一个名词，它不能用作主语
12. 找一个名词，它不能用作宾语
13. 找一个名词，它后面可以加上“地”用作状语
14. 找一个名词，它可以直接用作状语（不加“地”）
查看更多 »

    IMO 2001第三题：21个女生和21个男生一起参加了一场数学竞赛。结果显示，每个参赛者最多做对了6道题，并且对于任一对男生和女生，至少有一道他们都做对了的题。
    求证：存在这样的一道题，至少有三个女生和三个男生同时做对。

    当然，这个题目背景无趣而又生硬。如果是我的话，我肯定会把题目改成下面这个样子：21个女生和21个男生参加速配游戏，每个人独立地在自己的纸上写下不超过6种兴趣爱好。结果显示，对于任一对男女，他们都写下了至少一个相同的爱好。求证，存在某一个兴趣爱好，有至少三男三女都把它写上了。
























    我是一个忠实于原题的好娃娃，因此还是用数学竞赛来当题目背景。对于每个问题，如果有至少3个男生答对了，就给这个问题添加一个标记“B”；如果有至少3个女生答对了，就给这个问题添加一个标记“G”。然后我们画一张21x21的表格，横行代表男生，纵列代表女生。每一个格子都代表一道对应的男女同时做对的题（不同的格子可能对应相同的题目），我们把对应的题目的“B”、“G”标记填进格子里。
    下面我们说明，每一横行里至少有11个格子标了“G”，每一个纵列里至少有11个格子标了“B”。考虑某一个特定的人，他（她）与每一个异性参赛者都有同时答对的题目，但他（她）自己最多只做出6道题。这6道题目需要“分配”给21个异性参赛者。我们希望知道最多有多少道题被不超过2个异性参赛者答对。显然，最极端的情况就是其中的5道题目每道分别被2个异性做对，剩下的第6道题被其余11个异性做对。反过来这也就是被至少三个人答对的题目最少的情况，因此每一行（列）里都有至少11个格子标有异性的标记。
    这样，我们就有了至少21*11个标有“G”的格子，和至少21*11个标有“B”的格子。但21*11*2 > 21*21，因此总有一个格子被同时标上了“G”和“B”。

来源：http://www.cut-the-knot.org/pigeonhole/BoysGirlsProblems.shtml

  

来自Johns Hopkins大学的一次期末考题……
这是昨天AsukaNoKaze到我寝室来给我看的一个巨牛B的东西。

    北大自主招生的数学考题就只有5道题，考生反映“巨难无比”，考完立马就郁闷了，哇啦哇啦地哭。我收集到的信息不多，得到的消息也没有一一去证实。我把这5道题大致写一下，题目描述可能不准确，但基本意思就是这样。

1. 证明：边长为1的正五边形的对角线长为(1+√5)/2

2. 已知一个六边形AB₁CA₁BC₁，AB₁=AC₁，CB₁=CA₁，BA₁=BC₁，∠A+∠B+∠C=∠A₁+∠B₁+∠C₁。证明：三角形ABC面积为六边形的一半。

3. 某次球赛实行单循环赛制，规定赢一场得1分，输一场得0分。比赛队伍分为南方和北方，南方比北方多9支球队，且最后南方总分数是北方的9倍。求证：南方某支球队的得分最高。

4. 已知实数a1、a2、a3、b1、b2、b3满足：
a1+a2+a3 = b1+b2+b3, a1^2 + a2^2 + a3^2 = b1^2 + b2^2 + b3^2
且min{a1, a2, a3}≤min{b1, b2, b3}
证明：max{a1, a2, a3}≤max{b1, b2, b3}

5. 空间解析几何题，涉及到旋转体和光源。题目看了半天都不懂是啥意思，估计原题有附图。哪位有更准确的题目描述麻烦请在下面留言告诉我。 网上找的题目没有“圆周”两个字，怪不得半天不懂是啥意思。
立体直角坐标系xyz，在xy平面上有图形0<=y<=2-x^2，将此图形绕y轴旋转得到一个不透光的几何体V。在点P(1,0,1)处有一点光源，xy平面上有一以原点为圆心的圆，此圆的圆周上被照亮的部分长度为2π，求未被照亮的部分的长度。（感谢dd）

另据了解，清华的数学题题量较大，题目也稍微简单一些。有两道题非常有意思，我也一起写在这里。
证明：任意给定一个四面体，则至少存在一个顶点，使得过该顶点的三条棱可以构成一个三角形。
证明：以原点为对称中心、面积大于4的矩形至少覆盖除原点外的另外两个格点。

    下面这道题来自今年的Virginia Tech Rigeonal数学比赛（不知道该咋翻好）。比赛时间为两个半小时，一共有7道题，这是第5题：
    找出下面这个数小数点后第三位上的数字：(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))

    这个问题有趣的地方就是，你真的可以用一个简单的办法估算出答案来。为什么不先试试看？











































    我们需要求出(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))小数点后第三位上的数。首先，(1+√2)^(-1)就等于(√2-1)，而二项式展开后你会发现(√2 + 1)^(2n) + (√2 - 1)^(2n)总是一个整数（根号2的奇数次幂总是一正一负抵消）。同样地，((√5 + 2)^(2n) + (√5 - 2)^(2n)) * ((√2 + 1)^(2n) + (√2 - 1)^(2n))也是一个整数，于是(√5 + 2)^(2n) * ((√2 + 1)^(2n) + (√2 - 1)^(2n))和(√5 - 2)^(2n) * ((√2 + 1)^(2n) + (√2 - 1)^(2n))的小数部分是互补的（相加为1），我们可以依据后面这个数的小数部分来确定前面这个数（也即题目要求的数）的小数部分。而当n较大时，后面这个数很可能会变得非常小。事实上，当n=50时，

  (√5 - 2)^100 * ((√2 + 1)^100 + (√2 - 1)^100)
< (√5 - 2)^100 * 2((√2 + 1)^100)
< (1/4)^100 * 2((5/2)^100)
= 2(5/8)^100

    可以断定，这是一个非常非常小的数，小数点后面紧跟着的0至少有10个。这足以说明，题目里那个数的小数点后面十几位全部是9。事实上，
(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))
= 94158733601034420664808450657998303298219601745567527892456021922994
  873597395955752869490271254871747.9999999999999999999999996186915243
  507242961564029332966750212181162222265977213142686546252118999....
    小数点后一共有24个9。

本文来源：http://www.cut-the-knot.org/arithmetic/PowersOf10.shtml