HMMT 二月 2020 · 团队赛 · 第 10 题
HMMT February 2020 — Team Round — Problem 10
题目详情
- [60] Let n be a fixed positive integer, and choose n positive integers a , . . . , a . Given a permutation 1 n a i π on the first n positive integers, let S = { i | is an integer } . Let N denote the number of distinct π π ( i ) sets S as π ranges over all such permutations. Determine, in terms of n , the maximum value of N π over all possible values of a , . . . , a . 1 n
解析
- [60] Let n be a fixed positive integer, and choose n positive integers a , . . . , a . Given a permutation 1 n a i π on the first n positive integers, let S = { i | is an integer } . Let N denote the number of distinct π π ( i ) sets S as π ranges over all such permutations. Determine, in terms of n , the maximum value of N π over all possible values of a , . . . , a . 1 n Proposed by: James Lin n Answer: 2 − n n Solution: The answer is 2 − n . Let D = ( d ) be the matrix where d is 1 if i is a divisor of a and 0 otherwise. For a subset S of [ n ], ij ij j let D be the matrix obtained from D by flipping (0 ↔ 1) every entry d where j / ∈ S . Observe that S ij S = S if and only if ( D ) = 1 for all i . π S π ( i ) i n To show that N ≤ 2 − n we consider two cases. If all the rows of D are distinct, then there exist n different possibilities for S that set a row equal to zero. In this case, there is clearly no π so that n S = S . Thus there are at most 2 − n possible S . Otherwise, if two rows in D are the same, then π π choose an S such that D has two zero rows. Then, the n + 1 sets S that are at most “one element 0 S 0 away” from S are such that D only has one column with nonzero entries in those two rows. This 0 S n makes it impossible for S = S as well, so N ≤ 2 − n − 1. π n Now we construct N = 2 − n by setting a = j . By Hall’s marriage theorem, it suffices to prove the j following: Assuming that D has no completely-zero rows, given a set I = { i , i , . . . , i } there exist at least k S 1 2 k values of j so that there exists an i ∈ I so that ( D ) = 1. Call such j admissible. S ij Without loss of generality assume i < i < · · · < i . 1 2 k Note that if { d | i ∈ I } = { 0 , 1 } , then j is admissible. Therefore the k − 1 numbers i , i , . . . , i are ij 1 2 k − 1 admissible, since for α < k , i divides i but i does not. So we only need to find one more admissible α α k j . Assume that i is not admissible; now it must be the case that all the i are divisors of i . k α k At this point we note that the k = 1 case is easy, since no row of D is zero. Moreover, if k = 2, S { ( D ) , ( D ) } = { 0 , 1 } , so in the row with the zero there must be 1 somewhere, yielding a second S i i S i i 1 1 2 1 admissible column. In the case where k ≥ 3, note that i ≤ i / 3. Therefore i − i ∈ / I , but i divides i − i and i does 1 k k 1 1 k 1 k not. Thus we have found the last admissible column. Having exhausted all cases, we are done.