Hosted by The Math Forum

Problem of the Week 1166

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.

[Back to Problem 1166]

© Copyright 2013 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


2 October 2013