100囚犯问题、100囚犯问题加强版与选择公理(上)

    今后决定把较长的文章分段发布,不然大家读着太累。况且篇幅短一些的话,RSS输出也好看些:)

    在讲问题的加强版之前,让我们先来回忆一下经典的100囚犯问题(不是灯泡)。
    100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯,坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后,看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了,他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略,那么最理想的策略是什么?
    囚犯们可以乱猜一通,最坏情况下所有人都猜错,平均下来则会有50个人猜对。这个题有趣的地方就在于,100个囚犯事先可以商量一种策略,也就是说坐在后面的囚犯可以用他的猜测给坐在前面的囚犯透露一些信息。很显然,坐在最后面的囚犯是不可能保证自己猜对的,他猜黑猜白都只有一半的几率猜对,似乎没什么区别;但囚犯可以事先约定好一种暗号,即最后一个囚犯猜黑表示什么意思,猜白表示什么意思。比如,最后一个囚犯可以猜测和他前面的囚犯的帽子一样的颜色,这就相当于用他的猜测告诉了他前面那个囚犯该猜什么,于是坐倒数第二的囚犯可以保证被释放;此时,坐在倒数第三个位置上的囚犯面对与刚才坐最后的囚犯相同的处境,他同样可以用他的猜测提示出他前面那个人的帽子颜色。这样下去,可以保证至少50个人猜对,平均情况则有75个人猜对。这不是最佳的策略。
    不可思议的是,最佳策略可以保证,除了坐在最后面的囚犯以外,其余99个囚犯都能猜对。你能想出这样的策略是什么吗?继续看下去前不妨先想一下。

    前面那种策略的问题在于,坐在最后面的那个人透露出的信息不多。他完全可以透露出与全局相关的一些信息,因此以后所有的人都可以用这条信息。比如,他可以数一数他前面99个人一共有多少顶白帽子,并约定他猜“黑”表示他前面共有偶数顶白帽,他猜“白”表示他前面共有奇数顶白帽。坐倒数第二的那个人也数一数他前面98个人的白帽子个数:如果他数出来的个数与先前透露出的个数一奇一偶,则他自己肯定戴的是白帽子;如果他数出来的和先前透露的结果奇偶性相同,则他自己戴的肯定是黑帽子。这样,坐倒数第二的保证可以猜对了。那接下来咋办呢?不要忘了,其他囚犯能听到刚才那人猜的是什么,并且知道他的猜测保证是对的。这相当于每个人不仅能看到坐他前面的所有人的帽子颜色,还知道他背后那些人的帽子颜色,结合最初的那个奇偶性信息,接下来的每一个人都可以猜出自己脑袋上的帽子颜色。这样下去,至少99个囚犯可以保证被释放。这种策略显然是最佳的,不可能再有什么策略能保证所有人都被释放,因为至少坐最后的那个人不可能保证自己猜对。

    真正有趣的东西来了。下面提出这个问题的加强版,囚犯的数目加强到无穷个!你将看到“无穷”这个神秘的东西再一次开始作怪。

最后报怨一句:刚才不小心看到莲蓬乳了

平面几何趣题:三角形中的四点共圆

        
    任意给定一个三角形ABC。令M为BC上的中点,令H为BC上的垂足。角A的平分线与BC交于点D。过B、C分别向角平分线AD作垂线,垂足分别为P、Q。证明H、P、M、Q四点共圆。
    证明过程不复杂,几句话就说完了。但如果你能独立想出证明过程来的话也不简单。继续看下去前不妨先试试看。

        
    结论看起来似乎很神奇,但证明过程却并没有什么很特别的地方。
    为了说明四点共圆,我们下面说明圆周角∠HQP=∠HMP。首先我们证明,∠HQP=∠ACB。由于∠AHC=∠AQC=90°,因此A、H、Q、C四点共圆,于是圆周角∠HQP=∠ACB。然后我们证明,∠ACB=∠HMP。延长BP后你会发现,P是BR的中点(AP既是角平分线又是垂线,等腰三角形三线合一),而M是BC的中点,于是PM∥RC,当然就有∠ACB=∠HMP。

题目来源:http://www.cut-the-knot.org/Curriculum/Geometry/BalticDarij1.shtml
平面几何真好玩啊……怀念一下初中的美好时光。

趣题:用奇数个相同的多联骨牌组成轴对称图形

    由单位正方形拼接而成的图形叫做多联骨牌(Polyomino)。一个有趣的问题是,能否用奇数个相同的多联骨牌拼成一个对称图形?答案是肯定的。右图显示了如何用奇数个相同的多联骨牌拼接出中心对称图形和沿对角线方向轴对称的图形。
    下面的问题该轮到你来回答了。你能否用奇数个相同的多联骨牌拼接出一个左右轴对称的图形?当然,你所使用的多联骨牌本身必须是不对称的。为了方便起见,下文我们所说的“轴对称”均不再考虑沿对角线方向对称的情况。
    五联骨牌共有12种。令人吃惊的是,对于上述问题,所有这12种骨牌都有至少一个解。其中长条形、十字架形、T字形和U字形这4种是本来就对称的。你能否找出其余8种五联骨牌的解?
    并非所有的多联骨牌都是有解的,有一些六联骨牌就没有解。你能否找出一个没有解的多联骨牌,并证明它确实不可能有解?

    其实,用奇数个相同的多联骨牌拼出左右轴对称的图形是完全有可能的,并且这样的情况非常之多。下面随便举几个例子。你刚才都想到了哪些?
  

    对于这个问题,8种非对称的五联骨牌都是有解的。下面就是这8个图形的解:
  

    下面我们证明,你永远不可能用奇数个h形六联骨牌排成一个左右轴对称的图形。
  
    像国际象棋棋盘一样对拼出来的图形进行染色(图1),你会发现同一块h形骨牌里两种颜色的格子数量始终不等(图2),奇数个骨牌加起来两种颜色的总格子数目显然也就不会相等;但一个沿格子边线轴对称的图形,两种颜色的格子应该一样多才对。现在的问题是,如果对称轴在格子内的中心线上咋办。为此,我们还需要对拼出来的图形进行带状染色(图3)。注意到不管这些骨牌怎么放,同一个骨牌中每种颜色的格子都是奇数个(图4),奇数个骨牌加起来,每种颜色的格子总数也都还是奇数个。而在拼接出来的图形里,对称轴所在的那些格子全是一种颜色,另一种颜色的格子则左右对称分布,这种颜色的格子数应该有偶数个才对。这样我们就证明了,用奇数个h形六联骨牌不能拼出轴对称的图形。

更多的结论可以在这里看到:http://www.monmouth.com/%7Ecolonel/oddities/index.html

非传递性骰子:A比B好,B比C好,A不一定比C好

    在数学中,比较运算是有传递性的。如果A>B,且B>C,那么一定有A>C。但现实生活中却不一定是这样。三个人两两之间进行比赛,有可能A比B要强,B比C要强,但C反过来赢了A。事实上,这种现象即使在数学中也是存在的。在一些概率事件中,类似的“大小关系”很可能并不满足传递性。
    右边有四颗骰子,分别用A、B、C、D来表示。我让你先选择一颗你自己认为最好的骰子,然后我再从剩下的三个骰子中选一个。抛掷各自所选的骰子后,谁掷出的数字大,谁就赢了。那么,你应该选哪颗骰子好呢?
    其实,不管你选哪一个骰子,我获胜的概率总是要大一些,因为剩下的三个骰子中总有一个骰子比你的要好。事实上,在这四颗骰子中,A赢B的概率是2/3,B赢C的概率是2/3,C赢D的概率是2/3,D赢A的概率还是2/3,因此不管你选的是哪一个骰子,只要我选择它左边的那一个(如果你选的是最左边的,则我选择最右边的),我总保证有2/3的概率获胜。你认为这样的事情有可能吗?对你来说这样的事情合乎情理吗?

    如果你不信的话,我们可以一起来算一算:
    A和B比时,只要A扔出4的话A就赢了,这有2/3的概率;
    B和C比时,只要C扔出2的话B就赢了,这有2/3的概率;
    C和D比时,若C扔出6则C一定能赢,若C扔出2则胜负几率对等,因此C获胜的概率是(1/3) + (2/3)*(1/2) = 2/3;
    D和A比时,若A扔出0则D一定能赢,若A扔出4则胜负几率对等,因此D获胜的概率是(1/3) + (2/3)*(1/2) = 2/3。

有趣的C语言问题 测试你对C语言的熟悉程度

下面这个程序输出什么?
enum {false,true};
int main()
{
        int i=1;
        do
        {
                printf("%dn",i);
                i++;
                if(i < 15)
                        continue;
        }while(false);
        return 0;
}

你相信么?下面这个程序输出的两行东西不一样!
  #include <stdio.h>
  #define f(a,b) a##b
  #define g(a)   #a
  #define h(a) g(a)

  int main()
  {
          printf("%sn",h(f(1,2)));
          printf("%sn",g(f(1,2)));
          return 0;
  }

下面的程序看似完全正确。你能看出它为什么通不过编译吗?
看出问题前不要去试着编译,不然你会后悔你没看出来这个低级的语法错误。
#include<stdio.h>

void OS_Solaris_print()
{
        printf("Solaris - Sun Microsystemsn");
}

void OS_Windows_print()
{
        printf("Windows - Microsoftn");

}
void OS_HP-UX_print()
{
        printf("HP-UX - Hewlett Packardn");
}

int main()
{
        int num;
        printf("Enter the number (1-3):n");
        scanf("%d",&num);
        switch(num)
        {
                case 1:
                        OS_Solaris_print();
                        break;
                case 2:
                        OS_Windows_print();
                        break;
                case 3:
                        OS_HP-UX_print();
                        break;
                default:
                        printf("Hmm! only 1-3 :-)n");
                        break;
        }

        return 0;
}

为什么下面这个程序的输出不是NONE?看你多久才能看出来。
  #include<stdio.h>
  int main()
  {
          int a=10;
          switch(a)
          {
                  case '1':
                      printf("ONEn");
                      break;
                  case '2':
                      printf("TWOn");
                      break;
                  defa1ut:
                      printf("NONEn");
          }
          return 0;
  }

下面这个程序输出什么?
#include <stdio.h>
int main()
{
        int i=43;
        printf("%dn",printf("%d",printf("%d",i)));
        return 0;
}

下面这个程序输出什么?
  #include<stdio.h>
  int main()
  {
      int a=1;
      switch(a)
      {   int b=20;
          case 1: printf("b is %dn",b);
                  break;
          default:printf("b is %dn",b);
                  break;
      }
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
      int i;
      i = 10;
      printf("i : %dn",i);
      printf("sizeof(i++) is: %dn",sizeof(i++));
      printf("i : %dn",i);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  #include <stdlib.h>

  #define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))

  #define PrintInt(expr) printf("%s:%dn",#expr,(expr))
  int mai
n()
  {
      /* The powers of 10 */
      int pot[] = {
          0001,
          0010,
          0100,
          1000
      };
      int i;

      for(i=0;i<SIZEOF(pot);i++)
          PrintInt(pot[i]);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
    int a=3, b = 5;

    printf(&a["Ya!Hello! how is this? %sn"], &b["junk/super"]);
    printf(&a["WHAT%c%c%c  %c%c  %c !n"], 1["this"],
       2["beauty"],0["tool"],0["is"],3["sensitive"],4["CCCCCC"]);
    return 0;
  }

下面这个程序输出什么?
#include <stdio.h>
int main()
{
        int i=23;
        printf("%d %dn",i++,i++);
        return 0;
}

为什么下面这个程序的输出不是10?我故意取消了语法高亮:)
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %dn",#expr,(expr))
  int main()
  {
      int y = 100;
      int *p;
      p = malloc(sizeof(int));
      *p = 10;
      y = y/*p; /*dividing y by *p */;
      PrintInt(y);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
      int i = 6;
      if( ((++i < 7) && ( i++/6)) || (++i <= 9))
          ;
      printf("%dn",i);
      return 0;
  }

下面这段代码是否合法?
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %dn",#expr,(expr))
  int max(int x, int y)
  {
      (x > y) ? return x : return y;
  }

  int main()
  {
      int a = 10, b = 20;
      PrintInt(a);
      PrintInt(b);
      PrintInt(max(a,b));
  }

这是什么意思?有什么潜在的问题?
  #define SWAP(a,b) ((a) ^= (b) ^= (a) ^= (b))

这是什么意思?
  #define ROUNDUP(x,n) ((x+n-1)&(~(n-1)))

一些C语言的教材上会给出一个很经典的宏定义
  #define isupper(c) (((c) >= 'A') && ((c) <= 'Z'))
但这种宏定义的方法存在不足之处,一旦遇到下面这种情况就出问题了:
  char c;
  /* ... */
  if(isupper(c++))
  {
      /* ... */
  }

为了避免这种问题,应该怎样来定义isupper?

怎样用printf函数打印"I can print %"?别忘了百分号是用于格式化输出的。
不用任何比较运算符,写一个程序找出三个数中的最小数。
不用+号,(用位运算)实现加法运算。

最有趣的一个问题:不用分号,写一个Hello World程序。
这是有可能的,而且办法非常简单,只用到了最基本的语法规则。
实在想不出来再看答案吧(白色的):
#include <stdio.h>
int main()
{
    if (printf("Hello World")){}
}

查看更多:http://www.gowrikumar.com/c/