How many positive integers less than or equal to 1000 can be written as the sum of...
Check the final answer first, then review the worked steps.
Check the final answer first, then review the worked steps.
Powers of 3 $\le 1000$: $3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6$ (7 total).
Number of non-empty subsets with even size: $\sum_{k=1}^3 \binom{7}{2k} = \binom{7}{2} + \binom{7}{4} + \binom{7}{6} = 21 + 35 + 7 = 63$.
Any integer $n \le 1000$ can be uniquely written as $\sum_{i=0}^6 a_i 3^i$ where $a_i \in \{0, 1, 2\}$. This is equivalent to ternary representation. The condition requires the number of terms (where $a_i \neq 0$) to be even, but the problem specifies 'distinct powers of 3', meaning $a_i \in \{0, 1\}$. Thus, we consider subsets of $\{3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6\} = \{1, 3, 9, 27, 81, 243, 729\}$. There are $2^7 = 128$ such sums. Excluding the empty sum (0), we have 127 integers. Exactly half of the non-empty subsets have an even number of elements: $127/2$ is not an integer, so we check the parity. The number of subsets with an even number of elements is $\binom{7}{2} + \binom{7}{4} + \binom{7}{6} = 21 + 35 + 7 = 63$.