sahadian wrote:
Determine the number of subset $S$ of the set $T = {1, 2,..., 2005}$
such that the sum of elements in $s$ is congruent to 2006 modulo
2048.
We will consider the two sets $T_{0}=\{ 1,2,4,8,16,32,64,128,256,512,1024\}$ and $T_{1}=T\setminus T_{0}$. For any given subset $S\subseteq T$ we can partition $S$ into $S_{0}=S\cap T_{0}$ and $S_{1}=S\cap T_{1}$. For the problem condition on $S$ to hold, it must then follow that:
$\sum_{s\in S_{0}} s\equiv (2006-\sum_{s\in S_{1}} s) \mod{2048}$
Given that $2048=2^{11}$ and $T_{0}$ consists of exactly the powers of $2$ up to $2^{10}$, once the value of $S_{1}$ is known, there will be exactly one $S_{0}\subseteq T_{0}$ satisfying the above congruence. So the answer to the problem is simply the number of possible values for $S_{1}$. Since $T_{1}$ has $2005-11=1994$ elements, the answer to the problem is thus $2^{1994}$.