返回题库

派对分组 I

Party Groups I

专题
Brainteaser / 脑筋急转弯
难度
L6

题目详情

派对上有 50 位来宾。每人把名字写在纸上放入帽子。然后每位来宾依次从帽子里抽一个名字，并与抽到名字的人组成一组。

  • 若抽到自己名字，则自己单独成组。
  • 若形成闭环（例如 A 抽到 B，B 抽到 C，C 抽到 A），则这些人构成一个封闭小组。

问：平均会有多少个小组？四舍五入到 1 位小数。

Your at a party with 5050 guests in total where they are making groups for a game. Each person writes their name on a piece of paper and puts it into a hat. One by one, each guest picks a name from the hat. Each guest will form a group with the guest's name that they pulled out from the hat. If a guest pulls out their own name, they are in a group all by themselves. If Guest A pulls out Guest B's name, Guest B pulls out Guest C's name, and Guest C pulls out Guest A's name, they are all a part of the same closed group and no one else will be able to join them. How many groups will there be on average? Round your answer to the nearest tenth.

解析

等价于随机置换的循环分解。nn 元随机置换的循环个数期望为调和数 Hn=∑k=1n1kH_n=\sum_{k=1}^n \frac{1}{k}。

因此 n=50n=50 时期望为 H50≈4.5H_{50}\approx 4.5（四舍五入到 1 位小数）。

Original Explanation

You can also think of this scenario as each guest acting like a cable that connects nodes. Each cable has an "input" side and an "output" side. In the case where a guest picks their own name, it's like connecting the two ends of the cable together. Otherwise you are connecting two cables together and making one larger cable with one input end and one output end.

Those with a Mathematics background may want to think of this scenario as the expected number of cycles of a random 50−50- permutation.

Either way you want to think about it, the math stays the same. When the first guest picks a name, there is a 150\frac{1}{50} chance that the number of groups does not change and a 4950\frac{49}{50} chance that the number of groups effectively decreases by one (because two groups join together). When the next guest picks a name out of the hat, the given scenario is very similar whether the first guest formed their own group or connected with another guest. Both scenarios have 4949 groups or "cables". The only difference is that there are no closed groups if the first guest picked another person's name and one closed group if they picked their own name. If we keep continuing this for every guest, we add a closed group with probability 1k\frac{1}{k} where kk are the number of names still left in the hat.

Thus the answer is ∑n=1501n≈4.5\sum_{n=1}^{50} \frac{1}{n} \approx 4.5