阿里巴巴2013年9月14日笔试题最少比赛次数的有关问题

阿里巴巴2013年9月14日笔试题最少比赛次数的问题

5个人进行比赛，共需要C(5,2)*2=20最简单的一种情况如下：

每个人分别占一边，其余的人占另一边，最多需要5次比赛完成。

每次5个人分为2，3刚完成6次比赛，则比赛次数n满足如下：

[20/6]<=n<=5

即 4<=n<=5;

假设n=4时

若分配情况中存在1对4的情况，只需要查看另外四个的最少分配情况，然后给每种分配情况的右方加1即可，即P(5)=P(4)+1;

令P(4)=3，平均每场比赛C(4,2)*2/3=4场，四个人分为2对2最多四场，且要保证不重复，易证其不存在。

简证：

1 2->3 4

下面差个 1->2

1 3->2 4 1 4->2 3 都重复，即4个人3次不能比赛完成。

=》即若要四次完成5个人的比赛，每次比赛只能为2对3 或3 对2.

假设第一场比赛如下：

1 2->3 4 5

=>1 3->2 4 5 或 1 3 4-> 2 5

对于第一种情况，2和3已经比较完成，则2与3可以看为一个整体，23需要在左边出现一次（差2->1 ,3->1）即23 4->1 5 则下一次只能为4 5->123，得知差5->4，即不满足。

对于第二种情况，同样的2和3可以看为一个整体，同样需要23分别在左右各出现一次。

即 23->1

4 5->12 3(由于23分在右边时，右边已经三个了，所以45只能在左)

再分析还没有比较的，还有5->4,将其添加到23->1中，为2 3 5->1 4

最后结果比赛为：

最少需要四次。