Hosted by The Math Forum

# The Hex Queen

MacPOW Home || Math Forum POWs || Search MacPOW

## Solution

I received no comments on the hex queen coloring problem. So either you found it too easy or too hard or too uninteresting. Dan Ullman and I think the problem is a nice one and we have just submitted it to a journal, so I will not post the solution here. I am curious whether anyone solved it.

As for the various other hex queen problems, thanks again to Rob Pratt for finding the miracle at n = 20. In general, one can dominate the n + 2 queen graph by just adding in an apex to a solution for the n-graph. Q(6) can be dominated with 3 (just take the central vertical line of 3), and — in a bit of a surprise — Q(7) can be dominated with 3, also:

So the pattern rising from 6 goes

3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9

But Rob Pratt found that new miracle at 20, which can be dominated with 9, as opposed to the 10 that I expected (image at same link). Presumably there are more miracles like this.

In any case, this shows that for n ≥ 18 the upper bounds are as follows:

9, 9, 9, 10, 10, 11, 11, 12, 12

So letting γ denote the domination number,

γ(Q(n)) =

 Floor[(n + 1)/2] for 1 ≤ n ≤ 6 Floor[n/2] for 7 ≤ n ≤ 19 Floor[(n − 1)/2] for 19 ≤ n ≤ 20

One wonders where the next miracle of hex queen domination occurs, and of course, if there are infinitely many such reductions.

http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.

2 October 2013