Skip to main content

数学趣题：区分好人与坏人

问题：现有n个人，多于一半是好人，其余为坏人。你并不不知道他们具体谁是好人谁是坏人，然而他们彼此很清楚。
现在你每次可以挑两个人互相指认对方是好人还是坏人，好人总说实话，而坏人则会胡说（不一定是假话）。
请找到一个算法区分所有好人与坏人，并给出所需次数（大致数量级即可）

解答：（以下为大致阐述，对于细节，如是否严格大于或大于等于之类请自行讨论）
对于n较小的情况，如2，3，可以指定一个人T，让他与其余所有人互相指认，因为好人多于坏人，所以看结果是说T是好人的多还是坏人的多，那个多T就是哪个，如果一样多，T是好人。此时虽然是n平方数量级，但也可看作线性。

对n较大的情况，我们希望尽快找到一个好人以便指认出其余人的情况
把n个人两两分组（如有多余暂不考虑，放到下一轮处理），让他们互相指认。结果有如下几种情况：
a.至少一个人说对方是坏人
b.都说对方是好人

对于a, 组里至少一个人是坏人，我们把所有这样的组全部“淘汰”
对于b, 组里两个人必同为好人或同为坏人，我们在这样的组中每组任选一个淘汰。

这样一轮下来，可以知道淘汰掉的坏人不少于淘汰掉的好人，仔细分析还可知道剩下的人当中一定还是好人比坏人严格多。
这样下去直至剩下小于4人的情况，就可以用最开始的方法找到一个好人。
此时所花的次数约为N/2 + N/4 + ..., 大约等于N，然后再用至多N-1次指认就可以分辨所有好人与坏人了。

所以最后的数量级为2N
Labels:

Comments

Post a Comment

Popular posts from this blog

Determine Perspective Lines With Off-page Vanishing Point

In perspective drawing, a vanishing point represents a group of parallel lines, in other words, a direction. For any point on the paper, if we want a line towards the same direction (in the 3d space), we simply draw a line through it and the vanishing point. But sometimes the vanishing point is too far away, such that it is outside the paper/canvas. In this example, we have a point P and two perspective lines L1 and L2. The vanishing point VP is naturally the intersection of L1 and L2. The task is to draw a line through P and VP, without having VP on the paper. I am aware of a few traditional solutions: 1. Use extra pieces of paper such that we can extend L1 and L2 until we see VP. 2. Draw everything in a smaller scale, such that we can see both P and VP on the paper. Draw the line and scale everything back. 3. Draw a perspective grid using the Brewer Method. #1 and #2 might be quite practical. #3 may not guarantee a solution, unless we can measure distances/p...
2 comments
Read More »

[转] UTF-8 and Unicode FAQ for Unix/Linux

这几天,这个东西把我搞得很头疼 而且这篇文章好像太大了,blogger自己的发布系统不能发 只好用mail了 //原文 http://www.cl.cam.ac.uk/~mgk25/unicode.html UTF-8 and Unicode FAQ for Unix/Linux by Markus Kuhn This text is a very comprehensive one-stop information resource on how you can use Unicode/UTF-8 on POSIX systems (Linux, Unix). You will find here both introductory information for every user, as well as detailed references for the experienced developer. Unicode has started to replace ASCII, ISO 8859 and EUC at all levels. It enables users to handle not only practically any script and language used on this planet, it also supports a comprehensive set of mathematical and technical symbols to simplify scientific information exchange. With the UTF-8 encoding, Unicode can be used in a convenient and backwards compatible way in environments that were designed entirely around ASCII, like Unix. UTF-8 is the way in which Unicode is used under Unix, Linux, and similar systems. It is now time to make sure that you are well familiar ...
Post a Comment
Read More »

Moving Items Along Bezier Curves with CSS Animation (Part 2: Time Warp)

This is a follow-up of my earlier article.  I realized that there is another way of achieving the same effect. This article has lots of nice examples and explanations, the basic idea is to make very simple @keyframe rules, usually just a linear movement, then use timing function to distort the time, such that the motion path becomes the desired curve. I'd like to call it the "time warp" hack. Demo See the Pen Interactive cubic Bezier curve + CSS animation by Lu Wang ( @coolwanglu ) on CodePen . How does it work? Recall that a cubic Bezier curve is defined by this formula : \[B(t) = (1-t)^3P_0+3(1-t)^2tP_1+3(1-t)t^2P_2+t^3P_3,\ 0 \le t \le 1.\] In the 2D case, \(B(t)\) has two coordinates, \(x(t)\) and \(y(t)\). Define \(x_i\) to the be x coordinate of \(P_i\), then we have: \[x(t) = (1-t)^3x_0+3(1-t)^2tx_1+3(1-t)t^2x_2+t^3x_3,\ 0 \le t \le 1.\] So, for our animated element, we want to make sure that the x coordiante (i.e. the "left" CSS property) is \(...
3 comments
Read More »