返回题库

派对分组 II

Party Groups II

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

题目详情

同上分组规则下（50 人形成若干封闭循环小组），问：平均每个小组的大小是多少？四舍五入到 1 位小数。

At a party with 5050 guests, each guest writes their name on a piece of paper and places it in a hat. Guests take turns drawing a name from the hat. Each guest forms a group with the person whose name they draw. If a guest draws their own name, they form a group alone. If a guest draws another guest's name and this continues in a cycle, they form a closed group. If Guest AA pulls out Guest BB's name, Guest BB pulls out Guest CC's name, and Guest CC pulls out Guest AA's name, they are all a part of the same closed group and no one else will be able to join them. What is the average group size? Round your answer to the nearest tenth.

解析

平均组数为 H50H_{50}，总人数为 50。

因此平均组大小为

50H50≈11.1.\frac{50}{H_{50}}\approx 11.1.

Original Explanation

In the precursor to this problem, Party Guests, we found that there are ∑k=1501k\displaystyle \sum_{k=1}^{50} \dfrac{1}{k} groups on average, and since there are 5050 people total, the average size of a given group is 50∑k=1501k≈11.1\dfrac{50}{\sum_{k=1}^{50} \frac{1}{k}} \approx 11.1. This is correct and we are going to show this using the "cycles" interpretation from the previous part of the question.

There are (n!/k)(n!/k), k−k-cycles among the permutations, while there are n!⋅Hnn! \cdot H_n total cycles in all of the permutations (adding up the cycles of each length), where Hn=∑k=1n1kH_n = \displaystyle \sum_{k=1}^n \dfrac{1}{k}. Therefore, the probability that a given cycle is a k−k-cycle is n!/kn!Hn=1kHn\dfrac{n!/k}{n!H_n} = \dfrac{1}{kH_n}. Therefore, the expected length of a cycle would be

∑k=1nk⋅1kHn=nHn\displaystyle \sum_{k=1}^n k \cdot \dfrac{1}{kH_n} = \dfrac{n}{H_n}

Solving this yields the same answer we achieved before 11.111.1.