Task 4. Determine the number of sets $A=\left\{a_{1}, a_{2}, \ldots, a_{1000}\right\}$ of positive integers with $a_{1}<a_{2}<\ldots<a_{1000} \leq 2014$, for which the set

$$
S=\left\{a_{i}+a_{j} \mid 1 \leq i, j \leq 1000 \text { and } i+j \in A\right\}
$$

is a subset of $A$.
Solution. We prove that there are $2^{14}$ such sets. In particular, we prove that the sets $A$ that satisfy the conditions are of the form $B \cup C$, with $C$ a subset of $\{2001, \ldots, 2014\}$ and $B=\{1,2, \ldots, 1000-|C|\}$. Call sets of this form "nice". Since there are $2^{14}$ subsets of $\{2001, \ldots, 2014\}$, there are $2^{14}$ nice sets. We first show that every nice set $A$ satisfies the conditions. Suppose that $i, j \leq 1000$ with $i+j \in A$. Then $i+j \leq 2000$, so $i+j \in B$. There then exists a $k$ such that $k \leq 1000-|C|$ and $i+j=a_{k}(=k)$. Since $a_{k} \leq 1000-|C|$, it also holds that $i, j \leq 1000-|C|$, so $a_{i}=i$ and $a_{j}=j$. This means $a_{i}+a_{j}=i+j=a_{k}$ and that is an element of $A$. Therefore, every element of $S$ is an element of $A$, which implies that $A$ satisfies the conditions.

We now show that every set $A$ that satisfies the conditions is nice. Suppose first that there exists a $k$ with $1 \leq k \leq 1000$ such that $a_{k} \in\{1001, \ldots, 2000\}$. Then $a_{k}=1000+i$ for some $i$ with $i \leq 1000$, so $a_{1000}+a_{i}$ is an element of $S$ and must therefore also be an element of $A$. However, $a_{1000}+a_{i}>a_{1000}$, a contradiction. Therefore, such an $a_{k}$ cannot exist. This means that $A$ can be written as the disjoint union $B \cup C$, with $C \subseteq\{2001, \ldots, 2014\}$ and $B \subseteq\{1,2, \ldots, 1000\}$. Let $b$ be the number of elements of $B$. Then $b \geq 986$, because $C$ has at most 14 elements. To prove that $A$ is nice, we need to prove that $B=\{1,2, \ldots, b\}$. It is sufficient to prove that $a_{b}$, the largest element of $B$, is equal to $b$. Therefore, assume for the sake of contradiction that $a_{b}>b$. For $i$ with $i=a_{b}-b$, it then holds that $b+i=a_{b} \leq 1000$, so $i \leq 1000-b \leq 14<b$. Therefore, $a_{i} \leq 1000$ and thus $a_{b}+a_{i} \leq 2000$. Since $i+b=a_{b} \in A$, it follows that $a_{b}+a_{i} \in S \subset A$, but then $a_{b}+a_{i}$ is a larger element of $B$ than $a_{b}$, the maximal element. Contradiction. Therefore, $a_{b}=b$, which implies that $B=\{1,2, \ldots, b\}$. Thus, $A$ is nice.