Can you partition the set of 9 consecutive integers 1 to 9 in 2 sets, s.t. no member of either set is the mean of two other members of the same set?

Question

Is it possible to partition the set $\Omega=\{1,2,3,4,5,6,7,8,9\}$ in two subsets $\Omega=A\cup B$, $A\cap B=\emptyset$, such that no member of either subset is the mean of two other members of the same subset, i.e. such that the following condition holds? $$ \forall X\in\{A,B\}\forall x\in X\forall y,z\in X\setminus\{x\}\bullet y\neq z\implies x\neq\frac{y+z}{2} $$

The answer is: no, such a partition is impossible. This can be proven, e.g. by creating a tree of all possible partitions, and excluding each leaf.

I managed to write a proof that is more elegant than the brute-force method just described, but even so, it isn't particularly enlightening. I wonder if there is some insightful way of proving this result succinctly, possibly making a clever use of the Pigeonhole Principle.

Answer 1

In other words, can the set $[9]=\{1,2,3,4,5,6,7,8,9\}$ be partitioned into two sets, neither of which contains a $3$-term arithmetic progression? The answer is no because the Van der Waerden number $W(2,3)$ is equal to $9$. It took me a few minutes to verify this by hand with the obvious backtrack algorithm.

Of course $9$ is best possible here since $$[8]=\{1,2,5,6\}\cup\{3,4,7,8\}=\{1,3,6,8\}\cup\{2,4,5,7\}=\{1,4,5,8\}\cup\{2,3,6,7\}.$$

Here is my work showing that $W(2,3)=9$. The notation $0010011$ means that the numbers $1$, $2$, $4$, and $5$ go into one set, while the numbers $3$, $6$, and $7$ go into the other set, and putting $8$ into either set will create a $3$-term A.P.

$0010011$
$001011$
$00110011$
$0011010$
$0011011$
$0100101$
$010011$
$0101100$
$01011010$
$01100110$
$011010$
$011011$

Answer 2

Notice your question is really can I partition $S=\{1,2,3,4,5,6,7,8,9\}$ into two sets $A$ and $B$ such that there are no three-term arithmetic progressions in either set. From here after a bit of messing around one might suspect that every $5$ term subset must contain an arithmetic progression of three terms, but this turns out to be false as the set $\{1,3,4,8,9\}$ exists. With this our hopes of a pigeonhole-based solution kind of go out the window, and for this reason, the proof for this modified version of the question is generally something of the following form.

$1$. Pick an arithmetic triple, say $(1,5,9)$, and notice we are forced to partition them into one of the following $\{(1,5),(9)\}$ or $\{(1,9),(5)\}$. (Using the mapping $x\mapsto{10-x}$ we see that $\{(1,5),(9)\}$ is equivalent to $\{(5,9),(1)\}$.)

$2$. Now place $1$ and $5$ in $A$ and $9$ in $B$, then $3$ also can't be in $A$ so place it in $B$, but then $6$ must go in $A$, and going through the mental gymnastics we end up with $A=\{1,5,6,8\}$ and $B=\{3,4,7,9\}$ and we see that $2$ can't go in either set so we are done with this case.

$3$. Consider $1$ and $9$ in $A$ and $5$ in $B$, then we are left to do two sub-cases, one where some other term, say $2$ is in $A$ and another case with $2$ in $B$. Either way, we see that it's impossible to not have a three-term arithmetic progression once more and so the proof is complete.

For a potential glimmer of hope regarding some pigeonhole-based proof notice for any given term in $S$, there are at least $4$ arithmetic progressions containing that term. For instance $9$ has $(7,8,9)$, $(5,7,9)$, $(3,6,9)$, and $(1,5,9)$. You might be able to find a way to work with that, but I haven't seen anything thus far.