HMMT 二月 2018 · COMB 赛 · 第 7 题
HMMT February 2018 — COMB Round — Problem 7
题目详情
- A tourist is learning an incorrect way to sort a permutation ( p , . . . , p ) of the integers (1 , . . . , n ). We 1 n define a fix on two adjacent elements p and p , to be an operation which swaps the two elements i i +1 if p > p , and does nothing otherwise. The tourist performs n − 1 rounds of fixes, numbered i i +1 a = 1 , 2 , . . . , n − 1. In round a of fixes, the tourist fixes p and p , then p and p , and so on, a a +1 a +1 a +2 n ( n − 1) up to p and p . In this process, there are ( n − 1) + ( n − 2) + · · · + 1 = total fixes performed. n − 1 n 2 How many permutations of (1 , . . . , 2018) can the tourist start with to obtain (1 , . . . , 2018) after per- forming these steps?
解析
- A tourist is learning an incorrect way to sort a permutation ( p , . . . , p ) of the integers (1 , . . . , n ). We 1 n define a fix on two adjacent elements p and p , to be an operation which swaps the two elements i i +1 if p > p , and does nothing otherwise. The tourist performs n − 1 rounds of fixes, numbered i i +1 a = 1 , 2 , . . . , n − 1. In round a of fixes, the tourist fixes p and p , then p and p , and so on, a a +1 a +1 a +2 n ( n − 1) up to p and p . In this process, there are ( n − 1) + ( n − 2) + · · · + 1 = total fixes performed. n − 1 n 2 How many permutations of (1 , . . . , 2018) can the tourist start with to obtain (1 , . . . , 2018) after per- forming these steps? Proposed by: Kevin Sun Answer: 1009! · 1010! Note that the given algorithm is very similar to the well-known Bubble Sort algorithm for sorting an array. The exception is that in the i -th round through the array, the first i − 1 pairs are not checked. We claim a necessary and sufficient condition for the array to be sorted after the tourist’s process is: for all i , after i rounds, the numbers 1 , · · · , i are in the correct position. Firstly, this is necessary because these indices of the array are not touched in future rounds - so if a number was incorrect, then it would stay incorrect. On the other hand, suppose this condition holds. Then, we can ”add” the additional fixes during each round (of the first i − 1 pairs during the i -th round) to make the process identical to bubble sort. The tourist’s final result won’t change because by our assumption these swaps won’t do anything. However, this process is now identical to bubble sort, so the resulting array will be sorted. Thus, our condition is sufficient. Now, there are two positions the 1 can be in ( p , p ). There are three positions the 2 can be in 1 2 ( p , · · · , p except for the position of 1). Similarly, for 1 ≤ i ≤ 1009 there are 2 i − ( i − 1) = i + 1 1 4 positions i can be in, and after that the remaining 1009 numbers can be arranged arbitrarily. Thus, the answer is 1010! · 1009!.