返回题库

HMMT 二月 2018 · COMB 赛 · 第 7 题

HMMT February 2018 — COMB Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. A tourist is learning an incorrect way to sort a permutation ( p , . . . , p ) of the integers (1 , . . . , n ). We
    1 ndefine a fix on two adjacent elements p and p , to be an operation which swaps the two elementsi i +1
    if p > p , and does nothing otherwise. The tourist performs n − 1 rounds of fixes, numberedi 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
    How many permutations of (1 , . . . , 2018) can the tourist start with to obtain (1 , . . . , 2018) after per-2
    forming these steps?
解析

英文解析

  1. A tourist is learning an incorrect way to sort a permutation ( p , . . . , p ) of the integers (1 , . . . , n ). We
    1 ndefine a fix on two adjacent elements p and p , to be an operation which swaps the two elementsi i +1
    if p > p , and does nothing otherwise. The tourist performs n − 1 rounds of fixes, numberedi 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
    How many permutations of (1 , . . . , 2018) can the tourist start with to obtain (1 , . . . , 2018) after per-2
    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 anarray. 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: forall i , after i rounds, the numbers 1 , · · · , i are in the correct position. Firstly, this is necessary becausethese indices of the array are not touched in future rounds - so if a number was incorrect, then it wouldstay incorrect. On the other hand, suppose this condition holds. Then, we can ”add” the additionalfixes during each round (of the first i − 1 pairs during the i -th round) to make the process identical tobubble sort. The tourist’s final result won’t change because by our assumption these swaps won’t doanything. 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!.