最近cut-the-knot上的一些新东西比较有意思。今天下午没事干，我翻译一些我觉得好玩的和大家分享。
    上图显示了用直线将一个四分之一圆分为面积相等的两份的三种方法。这三条线段中，哪一个最长，哪一个最短？
    答案在下面。

    第一种方案的线段长度等于圆的半径；
    第二种方案的线段长度显然大于半径，因为红色线段和半径长度相等，但它还不足以平分扇形面积。
    第三种方案的线段长度显然小于半径。

因此，线段长度为②>①>③。

    今天回学校，有人说我智商降低了。我仔细想了一下，这段时间的数理思考确实少了些；但也不能说我完全废了，我还出了一次模拟赛的题呢。摆脱应试教育的思维模式后，不知道我的智商是上升了还是下降了。我开始在想如何检测我的思维是否还和原来一样敏捷。
    刚才看到OIBH上又在讨论数理逻辑，然后网上找到了这几道逻辑题来想。实践证明，我的思维能力仍然还不错。我把这些题目写在下面大家可以试一下。
    这是一类问题，这类问题的命题中包含有条件判断的形式。

Following are several problem from the island of knights and knaves where knights always tell truth whereas knaves always lie.

   1. A makes the following statement: "If I am a knight then so is B." What are A and B?
   2. Someone asks A, "Are you a knight?" He replies, "If I am a knight then I'll eat my hat". Must he eat his hat?
   3. A says, "If I am a knight then 2+2=4." Is A a knave or a knight?
   4. A says, "If B is a knight then I am a knave." What are A and B?

    不知道大家见过没有，我今天偶然看到，在这里写一下。
    箱子里有两个信封：“一个信封里有1元钱，另一个有10元”有1/2的概率；“一个信封里有10元钱，另一个有100元”有1/4的概率；“一个信封里有100元钱，另一个有1000元”有1/8的概率……也就是说，有1/2^n的概率发生这样的事情，一个信封里有10^(n-1)元钱，另一个信封里有10^n元钱。现在你拿到一个信封，看到了里面有x元钱。给你一次机会换成另外那个信封，问你换不换。
    举个例子，假如我们拿到了100元钱的信封，那么换一个信封得到1000元的概率是得到10元的概率的一半。也就是说，如果我们拿到了x元钱，换一个信封的话有1/3的概率多得9x元，有2/3的概率失去0.9x元。它的期望值是增加2.4x元，这告诉了我们换一个信封显然更好。
    现在的问题是，既然总是换个信封好些，那么为什么我们不一开始就选择另外那个信封呢？

大家可以在下面讨论
我就不参与讨论了，虽然我也不知道是怎么回事

    这个问题让我想到了Newcomb悖论，说有个妖精可以预言你将拿一个箱子还是两个箱子，大家一定见过。

    A highly superior being from another part of the galaxy presents you with two boxes, one open and one closed. In the open box there is a thousand-dollar bill. In the closed box there is either one million dollars or there is nothing. You are to choose between taking both boxes or taking the closed box only. But there's a catch.
    The being claims that he is able to predict what any human being will decide to do. If he predicted you would take only the closed box, then he placed a million dollars in it. But if he predicted you would take both boxes, he left the closed box empty. Furthermore, he has run this experiment with 999 people before, and has been right every time.
    What do you do?
    On the one hand, the evidence is fairly obvious that if you choose to take only the closed box you will get one million dollars, whereas if you take both boxes you get only a measly thousand. You'd be stupid to take both boxes.
    On the other hand, at the time you make your decision, the closed box already is empty or else contains a million dollars. Either way, if you take both boxes you get a thousand dollars more than if you take the closed box only.

    Newcomb悖论是很荒唐的，很不具有数学的科学性。但这篇日志介绍的悖论在科学性上是可以承认的。

    七等分正方形，四笔串连3×3的点阵，12根火柴棍摆出面积为1的封闭图形，这些题目见多了，再整人已经没用了。今天我第一次自己想了一个好玩的这类题目。
    有个OI题的大意是，给你一个不超过200位的字符串，请问它第一次出现在串"1234567891011121314…"的什么位置。这道题可以用O(n^3)的枚举AC。
    今天和arthas聊天时突然想到一个问题，使得输出结果最大的字符串（最坏情况下的输入数据）是什么样的。
    你的答案是什么？想好答案前请先别往下看。

    我起初以为是9999999…，但是9999999….可以从中间分开来。比如，六个数字9有可能出现在899999,900000中。我开始怀疑，是否所有的串都可以像这样分开来。

    后来我想到是900000000…，这样就不能从中间分开来了（否则有前导0）。然而这仍然不是最坏的情况。
    很少有人想到正确答案吧：0000000000…. (200个0)  这个答案显然是正确的。我也是后来才突然想到，因为我们忽略了输入是字符串，习惯性地以为输入数据是一个数，而且这个数越大越好。

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

Problem: game 取数游戏
题目来源：Matrix67根据经典问题改编

问题描述
    选数游戏是一个两人游戏。两人将轮流从1到9这九个数字中取数，取过的数不能再取。我们规定，谁取到的数里能找到三个数，使得这三个数的和为15，谁就获得了这次游戏的胜利。如果A取了1、6、7三个数，B取了2、3、5，若这时该A继续取数，则A取8可以获得胜利，因为当A获得了数字8后，出现了1+6+8=15。
    在游戏的每一着中，你可以得到此时游戏的状态。请你编程选择一种赢得游戏的最佳策略。

输入格式
    第一行输入若干个用空格隔开的数，表示你已经取了的数。这些数递增排列。
    第二行输入若干个用空格隔开的数，表示对手已经取了的数。这些数递增排列。
    当某一行没有数字（某个游戏者还没有选数）时，该行仍然会留出位置。

输出格式
    输出你认为此时你的最佳选择。

样例输入
1 6 7
2 3 5

样例代码
    下面的代码演示了游戏的这样一个策略：每一次总是选择最大的没有被取过的数。

program game;
var
   hash:array[1..9]of boolean;
   i:integer;
begin
   assign(input,'game.in');
   reset(input);
   repeat
      read(i);
      hash[i]:=true;
   until eof;
   close(input);

   for i:=9 downto 1 do
      if not hash[i] then break;
   assign(output,'game.out');
   rewrite(output);
   writeln(i);
   close(output);
end.

评分方法
    该题目将通过选手之间的循环赛进行评分。
    在某两个选手对抗时，测试程序将导入这两个选手的源程序并进行编译，然后轮流为选手编写输入文件实时描述对战情况。选手的输出文件将作为此次选手的决策提交上来。当游戏已经出现获胜方或无法继续进行时，测试程序自动结束。每两个选手比赛时将分两场进行，一场对抗后先行者将进行交换。任一次对抗中，选手胜一场得2分，负一场得-2分，平一场得0分（这个分数不是选手该题的最后得分）。对比赛得分进行排名后，若总选手数为n，你的排名为i，那么你的得分为(n-i+1)*100/n。得分为小数则取下整。排名相同则平分该段得分。
    选手程序出现以下情况将作为该次对抗的负者处理：
        选手程序单着运行时间超过1秒；
        选手内存占用超过64M；
        选手程序未输出决策或输出错误；
        选手程序非正常退出；
        选手程序发生错误导致评测程序非法退出。

    大家有没有看出来，这个游戏就是一个井字棋游戏。3个数加起来等于15一共有8种情况，而这8种情况恰好对应一个3阶幻方中的三个横行、三个纵列和两个对角线。也就是说，如果把这个游戏想成在下面的棋盘中进行，那就和井字棋游戏没什么两样了。

   +—+—+—+
   | 8 | 1 | 6 |
   +—+—+—+
   | 3 | 5 | 7 |
   +—+—+—+
   | 4 | 9 | 2 |
   +—+—+—+

    关于井字棋游戏，之前我曾有过研究。
    原来学博弈论之类的东西时，我曾写过一个程序，计算井字棋游戏的最佳策略。但不管我怎么搞，这个程序总是先走最角落的位置，这是十分可笑的。我一直在想，我的程序哪点儿有问题。后来我想到了。我的程序没有任何问题，而是人的习惯性思考出的错。我的程序计算出来的结果是对的，在井字棋游戏中开局占领一个角的胜算最大。

    比如说，现在我占了最左下角的那一个位置。那么下一步如果你走的是画了“X”的位置，你就输了。

   +—+—+—+
   | X | X | X |
   +—+—+—+
   | X |   | X |
   +—+—+—+
   | O | X | X |
   +—+—+—+

    下面的图1到图4这四个棋谱，它包含了除第二步走中间以外所有的分支情况。可以看出，如果你第二步不占领中间的话，你是必败的。
    图5告诉我们，即使对手占住了中间，第四步棋也有2/6个陷阱可以置他于死地。而另外4/6将导致棋局最终打平。假设每一步对方都是随机走的话，打到图6的情况概率为(1/8) * (4/6)，约为8.33%。反过来，我的胜算超过了90%。这在理论上可能是最大的了。
    当然，对手没有那么傻。面对这种情况，理智的人第二步总会想要占领中间的格子。考虑到这一点的话，胜算或许不到50%。

    仔细思考，你会发现，如果你第一步占领了中间的话，胜算是可以达到50%的。图7表明了这样一种情况，如果你第一步走中间，而对手不小心走到了边上，那么他就完了。比起前面的那些来，这里的陷阱可能更隐蔽一些。
    剩下的三个图表明，对手走了4个角中的一个后，最终结果必然是平局。

    至于以上这么多棋谱到底该选用哪一个，这个决策是属于自己的。

    我们考虑自己先行的所有情况的同时，也看清了自己作为后行者可能遇到的陷阱。对照以上棋谱，我们可以轻易获得平局的结果。

    由于井字棋游戏的总的情况数也只有那么多，变数不大，因此这个东西是一个非常入门级的东西。实际写程序的时候，分类讨论的效果比博弈树更好。

Matrix67原创
转贴请注明出处