Let $S = \{10^n + 1000: n = 0, 1, \dots\}$. Compute the largest positive integer not expressible as the sum of (not necessarily distinct) elements of $S$.

[i]Proposed by Ankan Bhattacharya[/i]
1. **Define the Set \( S \)**:
   The set \( S \) is given by:
   \[
   S = \{10^n + 1000 : n = 0, 1, 2, \ldots\}
   \]
   This means \( S = \{1001, 1010, 1100, 2000, \ldots\} \).

2. **Claim**:
   We claim that the largest positive integer not expressible as the sum of (not necessarily distinct) elements of \( S \) is \( \boxed{34999} \).

3. **Proof that 34999 is not expressible**:
   Suppose \( 34999 \) was expressible as a sum of elements from \( S \). To minimize the sum, we would need to use the smallest elements of \( S \) as much as possible. The smallest elements are \( 1001, 1010, \) and \( 1100 \).

   - Using 9 of each of these smallest elements:
     \[
     9 \cdot 1001 + 9 \cdot 1010 + 9 \cdot 1100 = 9009 + 9090 + 9900 = 27999
     \]
     This sum is \( 27999 \), which is less than \( 34999 \).

   - Any other combination that includes more of the larger elements (like \( 2000 \)) would exceed \( 34999 \). For example:
     \[
     19 \cdot 1001 + 8 \cdot 1010 + 9 \cdot 1100 = 19019 + 8080 + 9900 = 36999
     \]
     This sum is \( 36999 \), which is greater than \( 34999 \).

   - To make up the difference \( 34999 - 27999 = 7000 \) using only \( 2000 \)'s is not possible because \( 7000 \) is not a multiple of \( 2000 \).

4. **Proof that every number greater than 34999 is expressible**:
   Suppose the last four digits of the number are \( \overline{abcd} \). We need to show that for every choice of \( b, c, \) and \( d \), there exists an expressible number with \( a \) odd and another with \( a \) even.

   - Consider \( d \) 1001's, \( c \) 1010's, and \( b \) 1100's:
     \[
     (b+c+d) \cdot 1000 + (100b + 10c + d)
     \]
     This value is always less than \( 27999 \) and the parity of \( b+c+d \) is the parity of \( a \) for this number.

5. **Claim**:
   If a number with at least one \( 1010 \) tile is expressible, then that number plus \( 9000 \) is also expressible.

   - Proof: To see this, add \( 10 \) 1001's and take away one 1010:
     \[
     10 \cdot 1001 - 1010 = 10010 - 1010 = 9000
     \]
     Therefore, adding \( 9000 \) to an expressible number is also expressible.

6. **Conclusion**:
   By adding \( 9000 \) repeatedly, we can achieve every number from \( 35000 \) to \( 36999 \), which implies that every number greater than \( 34999 \) is expressible.