HMMT 十一月 2010 · 冲刺赛 · 第 32 题
HMMT November 2010 — Guts Round — Problem 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 are in S ?
解析
- [ 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 are in S ? a b Answer: 924 Consider the correspondence ( a, b ) ↔ 2 3 for non-negative integers a and b . So we can view T as the square of lattice points ( a, b ) where 0 ≤ a, b ≤ 5, and subsets of T as subsets of this square. 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 Round correspond to subsets of the square where if a point is in the set, then so are all points to the left and south 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 , x or − 1 if there is no such point. We claim the values S uniquely characterize S . This is because each x S characterizes the points of the form ( x, y ) in S . In particular, ( x, z ) will be in S if and only if x z ≤ 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 x then 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 because x 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 is y 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 . ( ) 12 The number of such walks is simply , since we can view it as choosing the 6 of 12 steps at which 6 ( ) 12 to move right. Thus the number of subsets S of T with the desired property is = 924. 6