HMMT 十一月 2010 · 冲刺赛 · 第 32 题

英文解析

32. [ 20 ] Let T be the set of numbers of the form 2 3 where a and b are integers satisfying 0 ≤ a, b ≤ 5.
    How many subsets S of T have the property that if n is in S then all positive integer divisors of n arein S ?
    a b
    Answer: 924 Consider the correspondence ( a, b ) ↔ 2 3 for non-negative integers a and b . So wecan view T as the square of lattice points ( a, b ) where 0 ≤ a, b ≤ 5, and subsets of T as subsets of thissquare.
    Notice then that the integer corresponding to ( a , b ) is a divisor of the integer corresponding to ( a , b )
    1 1 2 2
    if and only if 0 ≤ a ≤ a and 0 ≤ b ≤ b . This means that subsets S ⊂ T with the desired property,
    1 1 1 2
    Guts Roundcorrespond to subsets of the square where if a point is in the set, then so are all points to the left andsouth of it.
    Consider any such subset S . For each 0 ≤ x ≤ 5, let S be the maximum y value of any point ( x, y ) ∈ S ,
    or − 1 if there is no such point. We claim the values S uniquely characterize S . This is because eachxx
    S characterizes the points of the form ( x, y ) in S . In particular, ( x, z ) will be in S if and only ifxz ≤ S . If ( x, z ) ∈ S with z > S , then S is not the maximum value, and if ( x, z ) ∈ / S with z ≤ S ,
    x x x xthen S fails to satisfy the desired property.
    We now claim that S ≥ S for x < y , so the sequence S , . . . , S is decreasing. This is becausex y 0 1
    if ( y, S ) is in the set S , then so must be ( x, S ). Conversely, it is easy to see that if S , . . . , S isy y 0 1
    decreasing, then S is a set satisfying the desired property.
    We now claim that decreasing sequences S , . . . , S are in bijective correspondence with walks going
    0 5
    only right and down from ( − 1 , 5) to (5 , − 1). The sequence S , . . . , S simply corresponds to the walk
    0 5
    ( − 1 , 5) → ( − 1 , S ) → (0 , S ) → (0 , S ) → (1 , S ) → · · · → (4 , S ) → (5 , S ) → (5 , − 1). Geometrically,
    0 0 1 1 5 5
    we are tracing out the outline of the set S .
    ( )
    The number of such walks is simply , since we can view it as choosing the 6 of 12 steps at which 12
    ( )6
    to move right. Thus the number of subsets S of T with the desired property is = 924.12 6