BALTIC-WAY 2015 Problem 10

A subset $S$ of $\{1,2, \ldots, n\}$ is called balanced if for every $a \in S$ there exists some $b \in S, b \neq a$, such that $\frac{a+b}{2} \in S$ as well.

(a) Let $k>1$ be an integer and let $n=2^{k}$. Show that every subset $S$ of $\{1,2, \ldots, n\}$ with $|S|>\frac{3 n}{4}$ is balanced.

(b) Does there exist an $n=2^{k}$, with $k>1$ an integer, for which every subset $S$ of $\{1,2, \ldots, n\}$ with $|S|>\frac{2 n}{3}$ is balanced?

Solution of part (a). Let $m=n-|S|$, thus $m<\frac{n}{4}$ and (as $n$ is a multiple of 4 ) $m \leq \frac{n}{4}-1$. Let $a \in S$. There are $\frac{n}{2}-1$ elements in $\{1,2, \ldots, n\}$ distinct from $a$ and with the same parity as $a$. At most $m$ of those elements are not in $S$, hence at least $\frac{n}{2}-1-m \geq \frac{n}{4}$ of them are in $S$. For each such $b$, the number $\frac{a+b}{2}$ is an integer, and all of these at least $\frac{n}{4}$ numbers are distinct. But at most $m<\frac{n}{4}$ of them are not in $S$, so at least one is a member of $S$. Hence $S$ is balanced.