Problem (Combinatorics):
Let $\mathcal{S}$ be the set of integers from 0 to 9999 inclusive whose base- 2 and base- 5 representations end in the same four digits. (Leading zeros are allowed, so $1=0001_{2}=0001_{5}$ is one such number.) Compute the remainder when the sum of the elements of $\mathcal{S}$ is divided by 10,000.

Solution:
The remainders of an integer $N$ modulo $2^{4}=16$ and $5^{4}=625$ uniquely determine its remainder modulo 10000. There are only 16 strings of four 0's and 1's. In addition, because 16 and 625 are relatively prime, it will be shown below that for each such string $s$, there exists exactly one integer $x_{s}$ in the range $0 \leq x_{s}<10000$ such that the base- 2 and base- 5 representations of $x_{s}$ end in the digits of $s$ (e.g., $x_{1001}$ is the unique positive integer less than 10000 such that $x$ 's base- 5 representation and base- 2 representation both end in 1001).

Here is a proof of the preceding claim: Let $p(s)$ be the number whose digits in base 5 are the string $s$, and $b(s)$ be the number whose digits in base 2 are the string $s$. Then the system $x \equiv$ $p(s) \bmod 625$ and $x \equiv b(s) \bmod 16$ can be rewritten as $x=p(s)+625 m$ and $x=b(s)+16 n$ for integers $m$ and $n$. These reduce to the Diophantine equation $16 n-625 m=p(s)-b(s)$, which has solutions $m, n$ in $\mathbb{Z}$, with at least one of $m, n \geq 0$. Assuming without loss of generality that $m>0$ yields $x=p(s)+625 m \geq 0$. To show that there exists an $x_{s}<10000$ and that it is unique, observe that the general form of the solution is $m^{\prime}=m-16 t, n^{\prime}=n+625 t$. Thus if $p(s)+625 m>10000$, an appropriate $t$ can be found by writing $0 \leq p(s)+625(m-16 t)<10000$, which yields $p(s)+625 m-10000<10000 t \leq p(s)+625 m$. Because there are exactly 10000 integers in that interval, exactly one of them is divisible by 10000 , so there is exactly one value of $t$ satisfying $0 \leq p(s)+625(m-16 t)<10000$, and set $x_{s}=625(m-16 t)$.

Therefore there will be 16 integers whose base- 2 and base- 5 representations end in the same four digits, possibly with leading 0 's as in the example. Let $X=x_{0000}+\cdots+x_{1111}$. Then $X$ is congruent modulo 16 to $0000_{2}+\cdots+1111_{2}=8 \cdot\left(1111_{2}\right)=8 \cdot 15 \equiv 8$. Similarly, $X$ is congruent modulo 625 to $0000_{5}+\cdots+1111_{5}=8 \cdot 1111_{5}=2 \cdot 4444_{5} \equiv 2 \cdot(-1)=-2$.

So $X$ must be $8(\bmod 16)$ and $-2(\bmod 625)$. Noticing that $625 \equiv 1(\bmod 16)$, conclude that the answer is $-2+10 \cdot 625=\mathbf{6 2 4 8}$.

Final answer: 6248