A number theoretic function to characterize midpoint free subsets

Question

Recently, I was going over a curious recreational math paper titled "On the Diagonal Queens Domination Problem". The main result of the paper is establishing the minimum value $diag(n)$ of number of queens needed to be kept on the diagonal of a $n \times n$ chessboard so that they attack all the squares on the board.

The authors make use of some clever lemma and make an observation that $diag(n) = n + 1 - r_3(\lceil \frac{n}{2} \rceil)$. Here, $r_3(.)$ denotes the minimum value $k$ such that any $k$-element subset of $[n]$ contains a $k$ term arithmetic progression (a la Roth's theorem statement). In order to prove this statement, authors make use of a number theoretic statement which they do not prove. I also cannot prove i by myself because of my limited number theory background (and maybe because I am dense). The statement says the following

A collection of $k$ even numbers or $k$ odd numbers (the numbers in the collection have same parity, this will keep their sum even) is midpoint free even sum subset of $[n]$ $\mathit{if\ and\ only\ if}$ all the half of the numbers in the collection (rounded down if not integer) is a midpoint-free subset of $\lceil \frac{n}{2} \rceil$.

A few definitions to clarify the question. A subset $X$ of $[n]$ is midpoint free if for any two elements $i,j \in X$ $(i+j)/2 \not\in X$. A subset is even sum if $i+j$ is even for any $2$ elements $i,j \in X$.

I hope the question is clear. In case, its not, I apologize and would request you to kindly let me know whats not clear.

Answer 1

I don't know if understand the problem correctly, since some of the information seems extraneous and I think there is one mistake, so I will first reformulate the question before I answer it. Please let me know if I misunderstood.

Instead of "midpoint-free subset of $\lceil \frac{n}{2} \rceil$", I think you meant "midpoint-free subset of $[\lfloor \frac{n}{2} \rfloor]$". Firstly, the brackets for turning the number into a set were missing, but more importantly, we need the floor and not the ceiling, since otherwise the theorem would fail simply because the set of halves could contain $\lceil \frac{n}{2} \rceil$ and this would prevent the original set from being a subset of $[n]$.

With this out of the way, it seems that neither $k$ nor $n$ nor $[n]$ are actually relevant to the problem, so I will drop all references to them. Also, the property "even-sum" is guaranteed by the collection containing either only even numbers or only odd numbers, so it's a bit confusing to state it as part of the equivalence to be proved.

With these clarifications, I would restate the theorem as follows:

A set $S$ containing either only even numbers or only odd numbers is midpoint-free iff the set $H$ of all halves of its elements (rounded down if not integer) is midpoint-free.

This seems to be a purely "local" property that can be proved by just looking at every pair of numbers individually:

First, let the numbers in $S$ be even, and take two numbers $2m$ and $2n$. Then the halves of these numbers are $m$ and $n$, respectively, and $(2m + 2n) / 2 = m + n$, so the theorem is proved if we can show that $m + n \notin S \Leftrightarrow (m + n) / 2 \notin H$. Now if $m + n$ is odd, this is vacuously true since the odd number $m + n$ cannot be in the set $S$ of even numbers and the non-integer $(m + n) / 2$ cannot be in the set $H$ of integers. If $m + n$ is even, the "$\Leftarrow$" direction is obvious, and the "$\Rightarrow$" direction follows because "S" contains only even integers, so the other number of which $(m + n)/2$ is a (rounded) half, $m + n + 1$, is not in $S$ either. This proves the theorem for $S$ containing only even numbers.

Now let the numbers in $S$ be odd, and take two numbers $2m+1$ and $2n+1$. Then the halves of these numbers, rounded down, are $m$ and $n$, respectively, and $(2m+1 + 2n+1) / 2 = m + n + 1$, so the theorem is proved if we can show that $m + n + 1\notin S \Leftrightarrow (m + n) / 2 \notin H$. Again, if $m + n$ is odd, this is vacuously true since the even number $m + n + 1$ cannot be in the set $S$ of odd numbers and the non-integer $(m + n) / 2$ cannot be in the set $H$ of integers. If $m + n$ is even, the "$\Leftarrow$" direction is again obvious, and the "$\Rightarrow$" direction follows because "S" contains only odd integers, so the other number of which $(m + n)/2$ is a (rounded) half, $m + n$, is not in $S$ either. This proves the theorem for $S$ containing only odd numbers.