HMMT 二月 2018 · 团队赛 · 第 6 题
HMMT February 2018 — Team Round — Problem 6
题目详情
- [ 35 ] Let n ≥ 2 be a positive integer. A subset of positive integers S is said to be comprehensive if for every integer 0 ≤ x < n , there is a subset of S whose sum has remainder x when divided by n . Note that the empty set has sum 0. Show that if a set S is comprehensive, then there is some (not necessarily proper) subset of S with at most n − 1 elements which is also comprehensive.
解析
- [ 35 ] Let n ≥ 2 be a positive integer. A subset of positive integers S is said to be comprehensive if for every integer 0 ≤ x < n , there is a subset of S whose sum has remainder x when divided by n . Note that the empty set has sum 0. Show that if a set S is comprehensive, then there is some (not necessarily proper) subset of S with at most n − 1 elements which is also comprehensive. Proposed by: Allen Liu We will show that if | S | ≥ n , we can remove one element from S and still have a comprehensive set. Doing this repeatedly will always allow us to find a comprehensive subset of size at most n − 1. Write S = { s , s , . . . , s } for some k ≥ n . Now start with the empty set and add in the elements s 1 2 k i in order. During this process, we will keep track of all possible remainders of sums of any subset. If T is the set of current remainders at any time, and we add an element s , the set of remainders i will be T ∪ { t + s | t ∈ T } . In particular, the set of remainders only depends on the previous set of i remainders and the element we add in. At the beginning of our process, the set of possible remainders is { 0 } for the empty set. Since we assumed that S is comprehensive, the final set is { 0 , 1 , . . . , n } . The number of elements changes from 1 to n − 1. However, since we added k ≥ n elements, at least one element did not change the size of our remainder set. This implies that adding this element did not contribute to making any new remainders and S is still comprehensive without this element, proving our claim.