HMMT 二月 2026 · 团队赛 · 第 8 题
HMMT February 2026 — Team Round — Problem 8
题目详情
- [50] Let n ≥ 2 be a positive integer and let ( a , . . . , a ) be a permutation of the numbers 1 , 2 , . . . , n . 1 n Marin makes a single move on this permutation by performing the following steps: • First, he chooses an integer 1 ≤ k ≤ ⌊ n/ 2 ⌋ . This integer can be different for different moves. • Then, he picks two nonintersecting sets I = { i , i , . . . , i } and J = { j , j , . . . , j } such that 1 2 k 1 2 k 1 ≤ i < i < · · · < i ≤ n and 1 ≤ j < j < · · · < j ≤ n . 1 2 k 1 2 k • Finally, he swaps the numbers a and a in the current permutation for all integers 1 ≤ s ≤ k . i j s s Let f ( n ) denote the smallest positive integer such that it is possible for Marin to reach (1 , 2 , . . . , n ) from any starting permutation in at most f ( n ) moves. Prove that ⌈ log n ⌉ ≤ f ( n ) ≤ ⌈ log n ⌉ . 3 2
解析
- [50] Let n ≥ 2 be a positive integer and let ( a , . . . , a ) be a permutation of the numbers 1 , 2 , . . . , n . 1 n Marin makes a single move on this permutation by performing the following steps: • First, he chooses an integer 1 ≤ k ≤ ⌊ n/ 2 ⌋ . This integer can be different for different moves. • Then, he picks two nonintersecting sets I = { i , i , . . . , i } and J = { j , j , . . . , j } such that 1 2 k 1 2 k 1 ≤ i < i < · · · < i ≤ n and 1 ≤ j < j < · · · < j ≤ n . 1 2 k 1 2 k • Finally, he swaps the numbers a and a in the current permutation for all integers 1 ≤ s ≤ k . i j s s Let f ( n ) denote the smallest positive integer such that it is possible for Marin to reach (1 , 2 , . . . , n ) from any starting permutation in at most f ( n ) moves. Prove that ⌈ log n ⌉ ≤ f ( n ) ≤ ⌈ log n ⌉ . 3 2 Proposed by: Marin Hristov Hristov Answer: N/A Solution 1: Upper bound. We’ll prove that f ( n ) ≤ ⌈ log n ⌉ for all positive integers n ≥ 2 by strong 2 induction on n . The base cases f (2) = 1 and f (3) = 2 are trivial and can be checked directly. For the ©2026 HMMT induction step, fix n > 3 , and let d = ⌊ n/ 2 ⌋ . For a permutation ( a , . . . , a ) of the numbers 1 , . . . , n , 1 n we define I = { i | a > d, 1 ≤ i ≤ d } and J = { j | a ≤ d, d < j ≤ n } . i j Notice that |I| = |J | since if we define L = { ℓ | a ≤ d, 1 ≤ ℓ ≤ d } , then from the definition of I , J ℓ and L it follows that these are pairwise nonintersecting sets. As a result, we get: |I ∪ L| = |{ i | 1 ≤ i ≤ d }| = d = |{ i | a ≤ d }| = |J ∪ L| . i Therefore, |I| = d − |L| = |J | , and this will be our choice of k for the first move (if |I| = |J | = 0 , we simply don’t make a move at this stage). Since I ∩ J = ∅ from above, this value of k is allowed. ′ ′ ′ ′ ′ ′ For the newly formed permutation ( a , a , . . . , a ) we have that ( a , a , . . . , a ) is a permutation of 1 2 n 1 2 d ′ ′ { 1 , 2 , . . . , d } and ( a , . . . , a ) is a permutation of { d + 1 , . . . , n } . n d +1 What remains is to notice that after this point, if we want to make a move ( k , I , J ) on a permutation 1 1 1 of the numbers 1 , . . . , d , and a move ( k , I , J ) on the numbers d + 1 , . . . , n (by interpreting 2 2 2 these numbers the same as 1 , . . . , n − d ), then we would be able to combine them into a single move ( k + k , I ∪ I , J ∪ J ) over the n -element permutation since the structural separation of the 1 2 1 2 1 2 two permutations from above. Therefore, we can use the induction hypothesis for d = ⌊ n/ 2 ⌋ and n − d = ⌈ n/ 2 ⌉ . In this way, we can always reach (1 , 2 , . . . , n ) using at most 1 + max { f ( d ) , f ( n − d ) } ≤ 1 + max {⌈ log ⌊ n/ 2 ⌋⌉ , ⌈ log ⌈ n/ 2 ⌉⌉} = ⌈ log n ⌉ 2 2 2 moves. Thus, we have proven that f ( n ) ≤ ⌈ log n ⌉ for all integers n ≥ 2 , as desired. 2 Here is also an example of the above procedure for n = 8 . In every permutation, the elements of I are bolded, and the elements of the corresponding J are underlined. ( 8 , 4 , 5 , 6 , 2 , 1 , 3 , 7) → (2 , 4 , 1 , 3 , 8 , 5 , 6 , 7) → ( 2 , 1 , 4 , 3 , 6 , 5 , 8 , 7) → (1 , 2 , 3 , 4 , 5 , 6 , 7 , 8) . Lower bound. We will now prove that f ( n ) ≥ ⌈ log n ⌉ for all positive integers n > 1 . 3 Let us call a set of indices I troublesome , if a > a for all indices i < i ∈ I . Consider the starting i i 1 2 1 2 permutation ( n, n − 1 , n − 2 , . . . , 2 , 1) and note that the set of all indices is troublesome. The key observation we will use is that if a permutation has a troublesome set T , then after any move, the ′ resulting permutation has a troublesome set of size | T | ≥ | T | / 3 . Indeed, we can notice that T ∩ I , T ∩ J and T \ ( I ∪ J ) are nonintersecting troublesome subsets of 1 T . Therefore, at least one of them contains at least | T | elements. Therefore, the size of the largest 3 troublesome subset decreases by a factor of at most 3 after each move. Since (1 , 2 , . . . , n ) does not contain a troublesome set with more than one element, we can conclude that f ( n ) ≥ ⌈ log n ⌉ for all 3 integers n > 1 , as desired. Solution 2: We first show the upper bound of ⌈ log n ⌉ . To sort the permutation, consider a recursive 2 routine f ( L, R ) that sorts a , . . . , a . Let M = ⌊ ( L + R ) / 2 ⌋ be the midpoint of this subarray. Notice L R that if k elements in a , . . . , a should have been in a , . . . , a after sorting, there are also k L M M +1 R elements in a , . . . , a that should be in the first half after sorting. M +1 R So, we can just let f ( L, R ) swap the violating elements in the first half with the violating elements in the last half, and recurse down on f ( L, M ) and f ( M + 1 , R ) . Notice that all the swaps on the same level can be done in one choice of I, J . This will complete in ⌈ log n ⌉ moves. 2 To show the lower bound of ⌈ log n ⌉ , denote L ( x ) for sequence of integers x to be the length of the 3 longest increasing subsequence (LIS) of x . Claim 1. If a, b, c are three sequences of not necessarily the same length, consider the set of all sequences S formed by interleaving them (keeping order within a, b, c the same.) Then, the max of L ( x ) over x ∈ S is at most three times its minimum. ©2026 HMMT Proof. This follows from noting that L ( a ) + L ( b ) + L ( c ) max ( x ) x ∈ S min ( x ) ≥ max( L ( a ) , L ( b ) , L ( c )) ≥ ≥ . x ∈ S 3 3