Problem 9.3. The sets $M=\{1,2, \ldots, 27\}$ and $A=\left\{a_{1}, a_{2}, \ldots, a_{k}\right\} \subset$ $\{1,2, \ldots, 14\}$ have the following property: every element of $M$ is either an element of $A$ or the sum of two (possibly identical) elements of $A$. Find the minimum value of $k$.

Peter Boyvalenkov
9.3. The elements of $A$ give $\binom{k}{2}+k+k=\frac{k(k+3)}{2}$ sums of the required kind (with two different summands, two equal summands or one summand, respectively). Therefore $\frac{k(k+3)}{2} \geq 27$, whence $k \geq 6$.

If $k=6$ every element of $M$ has a unique representation. This consecutively implies $1 \in A, 2 \notin A, 3 \in A, 4 \notin A, 5 \in A$ and now $6=3+3=1+5$ has two representations, a contradiction. Therefore $k \geq 7$.

Assume that $A=\left\{a_{1}, a_{2}, \ldots, a_{7}\right\}$ has the required property and $a_{1}<a_{2}<$ $\cdots<a_{7}$. Since 1 and 27 have unique representations, we have $a_{1}=1, a_{6}=13$ and $a_{7}=14$. Also, it is easy to see that $a_{2} \in\{2,3\}$ and $a_{3} \leq 5$. The only two possible representations of 25 are $25=13+12=14+11$ and therefore $a_{5}=12$ or $a_{5}=11$.

Case 1. $a_{5}=$ 12. It follows from $23=14+9=13+10=12+11$ that $a_{4} \in\{9,10,11\}$. Then checking all possibilities for 21 we see that $a_{3} \geq 7$, which contradicts to the above restriction $a_{3} \leq 5$.

Case 2. $a_{5}=11$. As in case 1 we conclude that $a_{4} \in\{9,10\}$. On the other hand by $21=14+7=13+8=11+10$ we have $a_{4} \in\{7,8,10\}$ and therefore $a_{4}=10$. Now using $a_{3} \leq 5$ we see that the only possibility for 19 is $19=14+5$. This implies that $a_{3}=5$ and $a_{2}=3$, i.e. $A=\{1,3,5,10,11,13,14\}$. But this set does not have the required property.

The set $A=\{1,3,5,7,9,11,13,14\}$ has cardinality 8 and possesses the required property. Therefore the minimum value of $k$ is 8 .

Remark. The consideration of the case $k=6$ is not obligatory, it only gives an argument which leads to the solution.