PUMaC 2017 · 个人决赛（B 组） · 第 3 题
PUMaC 2017 — Individual Finals (Division B) — Problem 3
题目详情
- Let X = { 1 , 2 , . . . , 2017 } . Let k be a positive integer. Given any r such that 1 ≤ r ≤ k , there exist k subsets of X such that the union of any r of them is equal to X , but the union of any fewer than r of them is not equal to X . Find, with proof, the greatest possible value for k . 1
解析
- Let [ n ] = { 1 , 2 , . . . , n } , so that X = [2017]. Define a k -tuple ( X , . . . , X ) of subsets of [ n ] to 1 k be r -valid iff the union of any r of them is [ n ] while the union of any fewer than r of them is not equal to [ n ]. First, we will show that there exists a k -tuple of r -valid subsets of [ n ] iff ( ) k n ≥ . r − 1 If such subsets exist, then for any collection of r − 1 of them, there must be an element in none of them. These elements must be distinct because otherwise there would be r subsets whose union does not contain some element. Thus, there must be at least as many elements as there ( ) k are collections of r − 1 of the subsets, so n ≥ . r − 1 ( ) ( ) k k Conversely, suppose n ≥ . Let m = . If X , . . . , X are subsets of [ m ] such that 1 k r − 1 r − 1 ( X , . . . , X ) is r -valid, then if Y = X ∪ ([ n ] − [ m ]), then Y , . . . , Y are subsets of [ n ] such 1 k i i 1 k ( Y , . . . , Y ) is r -valid. Therefore, it suffices to show that there exists a k -tuple of r -valid 1 k subsets of [ n ] when n = m . Assuming n = m , assign each element of [ n ] to a unique collection of r − 1 elements of { 1 , 2 , . . . , k } . Let X be the set of all elements of [ n ] that are not assigned to a collection i containing i . We will show that X , X , . . . , X is r -valid. Indeed, given any S ⊆ { 1 , . . . , k } , 1 2 k ( ) ⋃ [ n ] − X i i ∈ S 1 is the set of all elements of [ n ] that are assigned to a collection containing S . If | S | ≤ r − 1, then such a collection certainly exists, while if | S | = r , then no such collection exists. ( ) k Altogether, this means that we must find the greatest value of k for which 2017 ≥ for r − 1 ( ) ( ) 13 14 each 1 ≤ r ≤ k . Since ≤ 2017 < , the answer is 13 . 6 7 Problem written by Matt Tyler 2