主题：IBM公司的招聘题

试试看，IBM招聘题 村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有枪响。到了第三天传来一阵枪声，问有几条病狗，如何推算得出？ 每天观察一次，然后第主人自己推理是否执行枪毙自己的狗。 这是IBM公司的招聘题，必须在20分钟内答出。各位加油咯！！

如果您想出答案，就请把您分析的过程写一下。谢谢拉~~~~~

再来： 我来贴个最新的ibm7月测试题吧 This is an old problem due to Roy Adler, Wayne Goodwyn and Benjamin Weiss. To our knowledge, it remains unsolved. 　　 　　We are given a collection of N cities and 2N one-way roads. (For example, we are told that the two roads leading out of Pittsburgh lead to Buffalo and Erie, respectively.) Each road leads from one city to another (or possibly back to the same city). Each city has exactly two roads leading out of it, and at least one leading in. We are assured that it is possible to proceed from any city to any other city by legal moves along the roads (that is, in the proper direction). 　　 　　We must impose one other technical condition: 　　Define a “cycle“ to be a route leading from one city through some other cities and back to the starting point (following the roads legally, and without visiting any city twice), and the “length“ of a cycle to be the number of roads traversed. We must assume that for each prime number p there is a cycle whose length is not divisible by p. (For example, not all cycles have length divisible by 3.) 　　 　　Our task is to color each road red or green, so that for each city the two roads exiting that city have different colors, and so that “universal directions“ can be given: namely, if a friend calls up and says “I don’t know where I am; how do I get to Pittsburgh?“, we can respond: “Take the red road out of your present city, then the green road, then the next green road, then red, then green, and then red; then you will be in Pittsburgh.“ 　　 　　Notes: 　　It is not enough to guarantee that these universal directions lead our friend THROUGH Pittsburgh somewhere along the line; she must END UP in Pittsburgh. 　　 　　The problem: Show that (under the given assumptions) we can always color the roads so that the “universal directions“ can be given. Or, give an instance (satisfying the given assumptions) for which there is no such coloring. 　　 　　Example: Suppose we are given three cities A,B,C, and we are given roads (AB), (AC), (BA), (BB), (CB), (CC). 　　(The first is a road from A to B; etc). 　　We decide to color roads (AC), (BB), (CB) green, and color (AB), (BA), (CC) red. 　　Now when someone calls up and asks to get to B, we tell him to take two green roads. 　　If he asks to get to another city, say C, we first direct him to B and then from B to C; so we tell him “Green Green Red Green“. 　　You can check for yourself that no matter where he starts, these directions get him to C.

帮大家翻译一下： 假设现在有N个城市，有2N个单方向的路（比如在深圳有两条路，一条通往广州，一条通往上海）。每条路都可从一城直达另一城（有可能回到原城市）。每个城市有且只有两条路通往城外，有且只有一条别城进入此城的路。我们假定我们可以沿着不同的路走，从而到达任何一个城市（但是必须有一个正确的方向） 　　 　　另外一个重要条件： 　　我们把‘圆’解释为一种从一城穿越其他城市最终回到原城的路线（条件是沿着一条正确的方向，一个城市只能经过一次）。‘圆’的长度为走过的路的数量的总合。我们必须假设任意质数P，都有一个‘圆’的长度是不能被P整除的（比如不是所有的‘圆’的长度都可以被3整除。） 　　 　　我们的任务是将每条路都用红/绿标出，所以每个城市里的2条从此城市发出的道路将由不同颜色表示。所以我们可以用一种‘宇宙示路法’来表示路的走法：如果你的一个朋友打电话对你说‘我不知道我在哪，我怎么可以找到深圳呢？’我们可以告诉他‘走你所在城中红色的那条路，然后走下一条绿色的路，再走红的，再走绿的，再走红的就可以到达深圳啦！’ 　　 　　注意： 　　我们并不保证在‘宇宙示路法’中你的朋友将经过深圳，但是她的终点只能，且必须在深圳。 　　 　　问题： 　　在上文以列出的条件下，请证明我们可以总是用红绿二色来标路，从而得出‘宇宙示路法’。或者，举出一个例子，证明用红绿二色来标路的方法，是不存在的（必须满足上文列出的条件） 　　 　　比如： 　　现有三城ABC，有路（AB），（AC），（BA），（BB），（CB），（CC）。 　　（AB是一条从A城发出通往B城的路，以此类推） 　　我们决定将路（AC），（BB），（CB）标成绿色，将路（AB），（BA），（CC）标成红色。 　　当有人打电话问如何可到达B城时，我们告诉他走两条绿色的路。 　　如果他问怎样可以到达别的城市，比如C城，我们首先告诉他去B的方法，然后再从B到C，所以我们将对他说‘绿绿红绿’ 　　你将发现无论他在哪里开始，通过这条路线，他将到达C城

。。。。。

答对有没有奖哦？ 要是有，可以说一下，呵呵！