Maths Olympiad Prep

Library / /51 of 104

Combinatorics Difficulty 5.7 AIME, harder Prove it Bulgaria

Problem:
Find the number of the subsets BB of the set {1,2,,2005}\{1,2, \ldots, 2005\} having the following property: the sum of the elements of BB is congruent to 20062006 modulo 20482048.

Solution

Solution:
Let us consider the set {1,2,22,,210}\{1,2,2^{2}, \ldots, 2^{10}\}. Since every number from 00 to 20472047 can be represented in a unique way as a sum of powers of 22 (elements of our set), we conclude that for every ii, 0i20470 \leq i \leq 2047, there is a unique subset of {1,2,22,,210}\{1,2,2^{2}, \ldots, 2^{10}\} such that the sum of its elements is equal to ii (00 corresponds to the empty set).

We now consider a set AA with the following property: for every ii the number of the subsets of AA such that the sums of their elements are congruent to ii modulo 20482048 does not depend on ii. It is easy to see that for every aa the set A{a}A \cup\{a\} has the same property. Since {1,2,22,,210}{1,2,3,,2005}\{1,2,2^{2}, \ldots, 2^{10}\} \subset \{1,2,3, \ldots, 2005\}, we conclude that the number of the subsets BB of {1,2,3,,2005}\{1,2,3, \ldots, 2005\} such that the sums of their elements are congruent to ii modulo 20482048 is equal to 220052048=22005211=21994\frac{2^{2005}}{2048} = \frac{2^{2005}}{2^{11}} = 2^{1994} 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.