返回题库

HMMT 二月 2020 · 团队赛 · 第 10 题

HMMT February 2020 — Team Round — Problem 10

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

题目详情

英文原题

  1. [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
解析

英文解析

  1. [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.