呵呵,今天从小曹那里学到了新东西,非常愉悦。
这个题目转到这里也两天了,不卖关子了,说说我的想法。
在聚会上随机选两个人,问两人是否认识对方。这是问了两次。
设这两人为A和B。
如果A认识B,B不认识A,那么A不是名人,B可能是名人。
如果A不认识B,B认识A,那么B不是名人,A可能是名人。
如果A认识B,B也认识A,那么A、B都不是名人。
如果A不认识B,B也不认识A,那么A、B都不是名人(这里解释一下,如果他们中有一个是名人,那么另一个肯定认识他)。
由此,经过两次提问,我们至少可以排除其中一人肯定不是名人。
这样,我们将N位客人两两一组如上提问,问过N个问题之后,我们可以排除N/2不是名人的人。
各位先不要纠结N是奇数的情况,或者说实际操作时多出的一个不问问题。
之后,对剩下的N/2人再两两一组如上提问。
这样每一轮问的问题数构成一个等比数列 N、N/2、N/4...
直到最后问到只剩两个人,再如上提问,即可确认谁是名人(或者没有名人也是可以确认的)。
如此,这个数列的长度为logN(注意,这里logN的底是2,它可能是个小数,先不要纠结在这里,听我慢慢道来)
那么这数列的前logN项的和为
S = N * (1 - (1/2)^logN) / (1 - 1/2)
= 2 * (N - N/(2^logN))
= 2 * (N - N/N)
= 2 * (N - 1)
写这个罗嗦是会了让大家看到2^logN这一步变化,虽然logN可能是小数,但2^logN是个精确的整数,即 N。
由此,得到结论,对于有N位客人的聚会,最多只需2 * (N - 1) 次提问即可确定名人是谁。
我想可能有人还在为logN而困惑。好,现在再用数学归纳法证明一下这个结论。
当N = 1时,聚会就一个人,一个人的聚会还有什么名人不名人的? 也不需要问,所以 f(0) = 2 * (1 - 1) = 0,结论成立
当N = 2时,f(2) = 2 * (2 - 1) = 2,即问两次可以确定名人。根据上文开头的论述可知,结论成立
现在假设当N = k时,结论也成立,即 f(k) = 2 * (k - 1)
那么当 N = k + 1时
我们可以通过f(k)次提问,排除其中k - 1个人,将剩下这位可能是名人的人与还未参与问答的第k + 1人组成一组问是否认识对方,这样可以确定他们中谁是名人
即
f(k + 1) = f(k) + 2
= 2 * (k - 1) + 2
= 2 * ((k + 1) - 1)
由此,当N = k + 1时,结论仍成立
综上所述 f(N) = 2 * (N - 1) 对于任意的N(N > 0)都成立
证毕。