003. The Minimum Cardinality of a Set

Given the set $X$ of natural numbers, find the minimum cardinality of $X$ such that the sum of a subset of $X$ can represent all natural numbers between 3000 and 6000.

---

Let $n(X) = m$. Also, define a set $Y = X - \{a\}$ where $a$ is the maximum number in $X$. So, $n(Y) = m - 1$ and the number of subsets of $Y$ is $2^{m - 1}$. It implies that the number of representable numbers by $Y$ is at most $2^{m - 1}$. Let $y$ be any number $Y$ can represent.

(i) $a < 3000$; In this case, $y$ must be in the range $[3000 - a, 6000 - a]$, that is, $(6000 - a) - (3000 - a) + 1 = 3001 \leq 2^{m - 1}$. As such, $m \geq 13$.

(ii) $a = 3000$; In this case, $y$ must be in the range $[1, 3000]$, that is, $3000 \leq 2^{m - 1}$. As such, $m \geq 13$.

(iii) $3000 < a \leq 6000$; In this case, $y$ must be in the range $[1, 6000 - a]$ or $[3000, a - 1]$, that is, $(6000 - a) + (a - 1) - 3000 + 1 = 3000 \leq 2^{m - 1}$. As such, $m \geq 13$.

(iv) $a > 6000$; In this case, $y$ must be in the range $[3000, 6000]$, that is, $3001 \leq 2^{m - 1}$. As such, $m \geq 13$.

Therefore, $m \geq 13$. Meanwhile, note that any natural numbers in $[1_2, 111111111111_2]$ can be represented from a partial sum of $1_2$, $10_2$, $100_2$, $\cdots$, $100000000000_2$ using binary format. Since $111111111111_2 = 2^{12} - 1 = 4095$, $X = \{ 2999, 1, 2^1, 2^2, \cdots, 2^{11} \}$ can represent any number in $[3000, 7094]$. So, the minimum cardinality of $X$ is $13$.