Let S=4,6,9 and T=9,10,11,,1000.

Question

Let $S=\{4,6,9\}$ and $T=\{9,10,11,\ldots,1000\}$. If $A=\{a_1+a_2+\cdots+a_k : k\in\mathbb{N},\ a_1,\ldots,a_k\in S\}$, then the sum of all elements in the set $T-A$ is equal to \_\_\_\_\_\_\_.

Answer: 11

Accepted Answer

We need numbers expressible as $4x+6y+9z$ with $x,y,z\ge0$ non-negative integers (not all zero). By Chicken McNugget-type reasoning: $6y+9z=3(2y+3z)$ covers all values $\ge2$ (multiples of 3, since $\gcd(2,3)=1$ and Frobenius number of $2,3$ is $1$). Then $4x+3t$ (where $t=2y+3z+$ offset) covers all values from $6$ onward (Frobenius number of $4,3$ is $4\times3-4-3=5$).

Careful analysis shows every integer $\ge12$ is representable, plus $9$ and $10$ are directly representable, but $11$ is not.

$$T-A = \{11\}, \quad \text{Sum} = 11$$

Solutions · 1