Problem:
Find the number of the subsets of the set having the following property: the sum of the elements of is congruent to modulo .
Solution
Solution:
Let us consider the set . Since every number from to can be represented in a unique way as a sum of powers of (elements of our set), we conclude that for every , , there is a unique subset of such that the sum of its elements is equal to ( corresponds to the empty set).
We now consider a set with the following property: for every the number of the subsets of such that the sums of their elements are congruent to modulo does not depend on . It is easy to see that for every the set has the same property. Since , we conclude that the number of the subsets of such that the sums of their elements are congruent to modulo is equal to and this is the required number.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.