HMMT 二月 2022 · COMB 赛 · 第 4 题

HMMT February 2022 — COMB Round — Problem 4

Compute the number of nonempty subsets S ⊆ {− 10 , − 9 , − 8 , . . . , 8 , 9 , 10 } that satisfy | S | + min( S ) · max( S ) = 0.

解析

Compute the number of nonempty subsets S ⊆ {− 10 , − 9 , − 8 , . . . , 8 , 9 , 10 } that satisfy | S | + min( S ) · max( S ) = 0. Proposed by: Akash Das Answer: 335 Solution: Since min( S ) · max( S ) < 0, we must have min( S ) = − a and max( S ) = b for some positive integers a and b . Given a and b , there are | S | − 2 = ab − 2 elements left to choose, which must come from the set {− a + 1 , − a + 2 , . . . , b − 2 , b − 1 } , which has size a + b − 1. Therefore the number of a + b − 1 possibilities for a given a, b are . ab − 2 In most cases, this binomial coefficent is zero. In particular, we must have ab − 2 ≤ a + b − 1 ⇐⇒ ( a − 1)( b − 1) ≤ 2. This narrows the possibilities for ( a, b ) to (1 , n ) and ( n, 1) for positive integers 2 ≤ n ≤ 10 (the n = 1 case is impossible), and three extra possibilities: (2 , 2), (2 , 3), and (3 , 2). In the first case, the number of possible sets is 2 3 10 2 3 10 11 2 + + · · · + = 2 + + · · · + = 2 = 330 . 0 1 8 2 2 2 3 In the second case the number of possible sets is 3 4 4