MathDB
Counting Subsets that sum to zero mod m

Source: China 2016 TST Day 2 Q6

March 16, 2016
Combinatorial Number Theorynumber theorycombinatorics

Problem Statement

Let m,nm,n be naturals satisfying n≥m≥2n \geq m \geq 2 and let SS be a set consisting of nn naturals. Prove that SS has at least 2n−m+12^{n-m+1} distinct subsets, each whose sum is divisible by mm. (The zero set counts as a subset).
Back to ProblemsView on AoPS