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 iffor 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 (notnecessarily 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 iffor 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 (notnecessarily 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 iin 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 remaindersiwill be T ∪ { t + s | t ∈ T } . In particular, the set of remainders only depends on the previous set ofiremainders and the element we add in.
At the beginning of our process, the set of possible remainders is { 0 } for the empty set. Since weassumed 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 ourremainder set. This implies that adding this element did not contribute to making any new remaindersand S is still comprehensive without this element, proving our claim.