Author Topic: 多少组发生了争吵  (Read 8602 times)

DAV

  • Newbie
  • *
  • Posts: 8
多少组发生了争吵
« on: 八月 01, 2012, 11:56:07 pm »
某班有120学生。为了准备一个大型的演出,任意四人都进行了一次小组讨论。
但是如果小组中只有两人互为好友,而其他人之间毫无关系,那么小组讨论时就会发生争吵。
请问,最坏的情况下会有多少组发生争吵。
注:好友是相互的。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 多少组发生了争吵
« Reply #1 on: 八月 03, 2012, 12:18:12 am »
是不是漏了什么条件?如果120个人都不是好友,那么所有小组都会吵架。或者说,小组中没有好友的就不吵架?

DAV

  • Newbie
  • *
  • Posts: 8
Re: 多少组发生了争吵
« Reply #2 on: 八月 03, 2012, 03:15:37 am »
可能没表述清楚,吵架的组数和朋友的对数以及分布有关。问的是什么情况下,最多。
吵架的条件是小组4人,其中两人好友,之外无其他好友关系。
比如120人中有3人互为好友,另外所有人无好友关系,则吵架组数=3*117*116/2=20358,这显然不是最多的情况。
« Last Edit: 八月 03, 2012, 03:20:24 am by DAV »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 多少组发生了争吵
« Reply #3 on: 八月 07, 2012, 09:36:38 am »
等了几天没有人回答。

如果总共有N人,其中K人是朋友,那么争吵个数应该是:

K*(K-1)*(N-K)*(N-K-1)/4

显然,最大数是K=N/2的时候。

DAV

  • Newbie
  • *
  • Posts: 8
Re: 多少组发生了争吵
« Reply #4 on: 八月 08, 2012, 12:21:15 pm »
这不是最优解,举个例子,N人分N/3,N/3,N/3每堆中所有人互为好友,吵架数=C(3,1)C(N/3,2)C(N/3,1)C(N/3,1)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 多少组发生了争吵
« Reply #5 on: 八月 12, 2012, 08:45:52 am »
上次利用等飞机的时间在飞机场上网,没有考虑周到。2等分确实不是最佳解。

回家后又想了一下,最佳解应该是5等分。我开始觉得这个5等分与120=5!
有关。后来发现对别的更大的N,最佳解仍然在5等分。准确说起来,应该
在 3+SQRT(3) 左右。5是最接近的整数。其它还有一些细节,可以再想想。

5等分后,吵架个数是:8538560
3等分后,吵架个数是:7488000
2等分后,吵架个数是:3132900

DAV

  • Newbie
  • *
  • Posts: 8
Re: 多少组发生了争吵
« Reply #6 on: 八月 18, 2012, 09:25:17 am »
上次利用等飞机的时间在飞机场上网,没有考虑周到。2等分确实不是最佳解。

回家后又想了一下,最佳解应该是5等分。我开始觉得这个5等分与120=5!
有关。后来发现对别的更大的N,最佳解仍然在5等分。准确说起来,应该
在 3+SQRT(3) 左右。5是最接近的整数。其它还有一些细节,可以再想想。

5等分后,吵架个数是:8538560
3等分后,吵架个数是:7488000
2等分后,吵架个数是:3132900
5等分为最佳解是对的,不过吵架个数貌似算错了,但这也无关大雅。
此题转自网站http://www.cs.cmu.edu/puzzle/solution11.pdf
发现那个网站上的部分好题都在万教授这里也出现过,比如说3只蜘蛛捉苍蝇,灯塔覆盖,不过上面还有很多好题这边没有,因此发到这里分享下。
万教授或其他人如有兴趣,也可以看看。

DAV

  • Newbie
  • *
  • Posts: 8
Re: 多少组发生了争吵
« Reply #7 on: 八月 18, 2012, 09:29:18 am »
顺便再转发一道那个网站上的另一题,发在这个主题下的一个原因是这题也是图论相关的,也算是蛮有趣的。

In the Padurea forest there are 100 rest stops. There are 1000 trails, each connecting a pair of rest stops. Each trail e has a level of difficulty l(e). No two trails have the same difficulty. An intrepid hiker, Sendeirismo has decided to spend a vacation by taking a hike consisting of 20 trails of ever increasing difficulty.
Can he be sure that it can be done?

He is free to choose the starting rest stop and the 20 trails from a sequence where the start of one trail is the end of a previous one.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 多少组发生了争吵
« Reply #8 on: 八月 18, 2012, 09:54:28 am »
谢谢推荐。

K等分的公式应该是: C(K-1,2)*N^3*(N-K)/(2*K^3)
N=120, K=5时应该是 4769280, 上次不知道什么地方写错了。