Question:
A set $A\subseteq\{1, 2, \dots, n\}$ satisfies: if $x, y\in A$ and $\frac{x+y}{2}\in\mathbb{Z}$, then $\frac{x+y}{2}\in A$. Find the number of such $A$ in terms of $n$.
I thought of this question while reading a book on Math Olympiads. Hence, I do not know if there is a closed-form formula. However, I thought the problem was quite interesting so I decided to post it to gather any ideas. Here is what I have already done.
Claim 1: Let the elements of $A$ be $a_1, a_2, \dots, a_m$ in ascending order. Then, $a_1\equiv a_3\equiv a_5\equiv\dots\pmod2$ and $a_2\equiv a_4\equiv a_6\equiv\dots\pmod 2$, and $a_1\not\equiv a_2\pmod2$
Proof:
It suffices to prove that $a_1\not\equiv a_2\pmod 2$, because we can repeat this argument to prove that $a_2\not\equiv a_3, a_3\not\equiv a_4, \dots \pmod2$, which will yield our desired result.
Suppose by contradiction that $a_1\equiv a_2\pmod 2$. Then, $\frac{a_1+a_2}{2}\in\mathbb{Z}$ so $\frac{a_1+a_2}{2}\in A$. However, $a_1<\frac{a_1+a_2}{2}<a_2$, contradiction.
Claim 2: $2a_{i+1}=a_i+a_{i+2}$. This is very strong as it shows that $A$ is an arithmetic sequence. The proof should be clear.
Edit: The proof is as follows:
For all $i$, we already know that $a_i\equiv a_{i+2}\pmod2$. This would mean that $\frac{a_i+a_{i+2}}{2}\in\mathbb{Z}$, so $\frac{a_i+a_{i+2}}{2}\in A$.
However, $a_i<\frac{a_i+a_{i+2}}{2}<a_{i+2}$, and since $a_{i+1}$ is the only element in $A$ that is in between $a_i$ and $a_{i+2}$, we must have $a_{i+1}=\frac{a_i+a_{i+2}}{2}$. This means that $a_{i+2}-a_{i+1}=a_{i+1}-a_i$. Repeating this argument shows that $A$ is an arithmetic sequence. However, since $a_i\not\equiv a_{i+1}\pmod2$, $A$ must have an odd difference.
Hence, $A$ is an arithmetic sequence with an odd difference. However, I do not know how to compute the number of arithmetic sequences with odd differences. Any ideas will be appreciated.
The number $C_n$ of arithmetic sequences with an odd difference in $[n] = \{1, \ldots, n\}$ can be computed by:
\begin{align*} C_n &= 1 + n + \sum_{a\in[n]}\sum_{d\in\{1,3,5,\ldots\}} \sum_{l=1}^{\infty} \mathbf{1}[\text{$\{a, a+d, \ldots, a+ld\}$ lies in $[n]$}] \\ &= 1 + n + \sum_{a\in[n]}\sum_{d\in\{1,3,5,\ldots\}} \sum_{l=1}^{\infty} \mathbf{1}[a + ld \leq n] \\ &= 1 + n + \sum_{d\in\{1,3,5,\ldots\}} \sum_{l=1}^{\infty} \max\{0, n - ld\} \\ &= 1 + n + \sum_{d\in\{1,3,5,\ldots\}} \sum_{l=1}^{\lfloor n/d \rfloor} (n - ld)\\ &= 1 + n + \sum_{d\in\{1,3,5,\ldots\}} \lfloor n/d\rfloor\left(n - \frac{(\lfloor n/d\rfloor + 1) d}{2}\right) \end{align*}
I am not sure if this can be simplified further to yield a closed-form expression not involving sums. (At least I checked that this formula for $C_n$ correctly computes the number of all arithmetic sequences in $[n]$, including the empty set, using Mathematica.)