HMMT 二月 2023 · 冲刺赛 · 第 30 题
HMMT February 2023 — Guts Round — Problem 30
题目详情
- [23] Five pairs of twins are randomly arranged around a circle. Then they perform zero or more swaps , where each swap switches the positions of two adjacent people. They want to reach a state where no one is adjacent to their twin. Compute the expected value of the smallest number of swaps needed to reach such a state.
解析
- [23] Five pairs of twins are randomly arranged around a circle. Then they perform zero or more swaps , where each swap switches the positions of two adjacent people. They want to reach a state where no one is adjacent to their twin. Compute the expected value of the smallest number of swaps needed to reach such a state. Proposed by: Amy Feng 926 Answer: 945 Solution: First, let’s characterize the minimum number of swaps needed given a configuration. Each swap destroys 0, 1, or 2 adjacent pairs. If at least one pair is destroyed, no other adjacent pairs can be formed. Therefore, we only care about the count of adjacent pairs and should never create any new ones. In a maximal block of k adjacent pairs, defined as k consecutive (circular) adjacent pairs, we k need at least d e swaps. Maximal blocks are independent as we never create new ones. Thus, we need 2 ∑ k i d e over maximal blocks. i 2 Now we focus on counting the desired quantity over all configurations. As the expression above is linear and because expectation is linear, our answer is the sum of the number of 1 − maximal blocks, 2 − maximal blocks, . . . , 5 − maximal blocks. Note that there can’t be a 4 − maximal block. This can be computed as E [ AA ] − E [ AABB ] + E [ AABBCC ] − E [ AABBCCDDEE ] , where AA . . . denotes a (not necessarily maximal) block of adjacent pairs and E [ AA . . . ] is the expected count of such. (This counts a block of AA as 1, a block of AABB as 1, a block of AABBCC as 2, and a block of AABBCCDDEE as 3 overall, as desired). Lastly, we compute this quantity. Say there’s n pairs. Let’s treat each of the 2 n people as distin- guishable. The expected number of k consecutive adjacent pairs (not necessarily as a maximal block) equals ( ) 1 n k n k !(2 n − 2 k )!2 n 2 k ( ) n The first n comes from choosing the start of this chain, from choosing which pairs are in this chain, k k k ! from permuting these pairs, 2 from ordering the people in each pair in the chain, and (2 n − 2 k )! from permuting the other people. 926 We plug in n = 5 to obtain . 945