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 naπ on the first n positive integers, let S = { i | is an integer } . Let N denote the number of distinctiππ ( 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 naπ on the first n positive integers, let S = { i | is an integer } . Let N denote the number of distinctiππ ( 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 Linn
Answer: 2 − nn
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 jlet 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
To show that N ≤ 2 − n we consider two cases. If all the rows of D are distinct, then there existnn different possibilities for S that set a row equal to zero. In this case, there is clearly no π so that
S = S . Thus there are at most 2 − n possible S . Otherwise, if two rows in D are the same, thennπ πchoose an S such that D has two zero rows. Then, the n + 1 sets S that are at most “one element
0 Saway” from S are such that D only has one column with nonzero entries in those two rows. This 0
0 Snmakes it impossible for S = S as well, so N ≤ 2 − n − 1.
Now we construct N = 2 − n by setting a = j . By Hall’s marriage theorem, it suffices to prove thenπjfollowing:
Assuming that D has no completely-zero rows, given a set I = { i , i , . . . , i } there exist at least k
S 1 2 kvalues 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 areij 1 2 k − 1
admissible, since for α < k , i divides i but i does not. So we only need to find one more admissibleα α kj . 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,
{ ( D ) , ( D ) } = { 0 , 1 } , so in the row with the zero there must be 1 somewhere, yielding a second s
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 knot. Thus we have found the last admissible column. Having exhausted all cases, we are done.