Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
BTW, LaTeX tip: \mathit should be used only for mathematical symbols that need to be in italics, not for text like "if and only if" (it looks ugly). :-) You can use \textit (or, here on StackExchange, simply enclose it within asterisks: *if and only if* produces if and only if.) –  ShreevatsaR Feb 8 '11 at 8:56
    
thanks for the tip shreevastavR –  Akash Kumar Feb 8 '11 at 12:59
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
yes joriki, you are right about the fact that it should be n/2 floored and not ceiled. also, let me thank you for your solution. it really helped. –  Akash Kumar Feb 8 '11 at 12:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.