问题：
在一个聚会上，如果所有的客人都认识其中的一位客人，而这位客人却不认识其他任何一个人，则这个人就称为名人，在一个聚会上，最多只有一个名人，一位若有两个名人，则他们必然相互认识，某个特定的聚会上也可能没有名人，你的任务是在一个聚会上去找一个名人，如果该聚会确实有名人的话，而你只允许向每个客人提问一种类型的问题---询问他是否认识灵位一名客人，每个客人必须如实回答你的问题。利用数学归纳法证明：若聚会上有n位客人，且有一位名人，那么你只需询问3*(n-1)次客人，你就能找到这位名人。
那位高手有思路呀，多谢了

[ 本帖最后由 luckyning 于 2012-10-3 14:02 编辑 ]

你确信没打错字是3 * (n - 1) ？

我分析了一下，应该最多只需要 2 * (n - 1) 次就够了。

恩，是3*(n-1),能否说下思路？谢啦

我可以证明它是2*(n-1)。

如果相信我的结论并想看证明过程，20分全加到这个帖子上。

如果你坚持它是3*(n-1)，请告诉我这道题的出处。

如果出自某本书，告诉我书名 书号(ISBN) 作者，以及这道题在书中的位置。

如果是你们老师布置的作业，请转达我的意见。

如果他依旧坚持，请告诉他我很鄙视他。

当然，最大的可能性还是你把题搞错了。你帖子里还有4个错别字。

[ 本帖最后由 beyondyf 于 2012-10-5 15:42 编辑 ]

楼主可以这么考虑这个问题。

把所有人的相互认识关系搞清楚，是不是可以用一个表格来描述。比如：
表示 A B C 三个人中，只有 A 认识 B，而且其它人都互相不认识了。至于主对角线上的点，你写什么都无所谓。
如果有名人，那么所有人都认识它，它所在的那一列就都为1；又它谁也不认识，所在它所在的行全为 0。

现在问楼主你有好的方法能在表中把满足条件的人找出来吗？

和pangding交流也很久了，还不知道该怎么称呼？

楼主在这里钓鱼呢。这也是我卖关子不回答的原因，不想浪费激情。

版主如果对这个问题有兴趣的话可以把贴子转到C区，毕竟那里人多些。

刚意识到任多版版主的一个好处，可以在这些版块间任意转移贴子。

我开始想争取一下这里的版主了

可以将这里有趣的贴子移到C区讨论——那里人多，便于集思广益。

可以将C区有价值的算法类贴子移到这里保存——这里人少的一个好处是灌水混分的也少。

哦？移过来了，那得顶一下。

学习学习

学习了

呵呵，今天从小曹那里学到了新东西，非常愉悦。

这个题目转到这里也两天了，不卖关子了，说说我的想法。

在聚会上随机选两个人，问两人是否认识对方。这是问了两次。

设这两人为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)都成立

证毕。