| Let me avoid the tricky questions you pose, and make some peripheral
remarks.
To see that for k=1, 10 is maximal, remark that each pair of mutually-
attacking queens will "consume" 3 or 4 rows and columns, out of a total
resource limit of 16. Hence 5 pairs is maximal. Here's an example that
attains the maximum.
+---+---+---+---+---+---+---+---+
| | | | Q | | Q | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | Q |
+---+---+---+---+---+---+---+---+
| Q | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | Q |
+---+---+---+---+---+---+---+---+ Each Q attacks exactly 1 others
| | | | | | | | | (10 queens)
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | Q | |
+---+---+---+---+---+---+---+---+
For different size boards than 8, say, n, an upper bound on number
of queens supportable for k=1 is thus 2[2n/3]. I've no real idea whether
this is attainable for large n. A recursive construction would be very
interesting.
For k>=5, no solution exists. A queen in a corner can only attack
3 others maximally, so all the corners are empty. A queen *next* to a corner
can then only attack 4 maximally, so the the square must be empty, and so on.
Thus you can't place *any* queens on the board.
Andrew.
|
| >What is the maximum number of queens that can be placed on a chessboard
>so that each queen attacks exactly k others? For k=1, the answer is 10.
>What is the answer for k = 2, 3, and 4? Below are some examples that
>establish lower bounds.
Gilbert's lower bounds: k=2 --> 14 queens
k=3 --> 18 queens
k=4 --> 21 queens
Good news! Your bounds are maximal. Each queen is located on
eight line segments (two vertical, two horizontal, and four diagonal).
We know that, starting from the queen, by heading out in exactly k of those
directions, we'll hit another queen; by heading out in 8-k directions, we
will hit the edge of the board.
The key observation is that there are exactly 92 ways in which the
edge of the board can be struck: 2*(8+8+15+15). No two queens can share
the same way of hitting the edge of the baord, because they would either
interrupt the other, or be co-located. So if we've got n queens, then:
n(8-k) =< 92
For k=2,3,4 this gives 15,18,23. We're nearly there.
k=2. Suppose there's a solution with n=15. Then 90 out of the
92 line segments are consumed. 8 of the 92 line segments correspond to
the diagonals of length 1 on the board. Hence, at least 3 of the 4
corners of the board must be occupied. Wlog, a1,a8,h1. h8 is then
empty, else each corner queen attacks three others. But then *all* other
line segments must be occupied. In particular, there must be a queen on
the g8-h7 diagonal. Wlog say it's on g8. But then the a8 queen attacks
three queens. Contradiction. So n=14 is best possible.
k=3. Bound is exact.
k=4. A queen in a corner can only attack 3 others, so the 4
corners are empty. But that reduces the number of possible line segments
by 8. So n(k-4) =< 84, and n=21 is the best possible.
This approach doesn't quite work for k=1. There are just too
many diagonals that you're never going to use. You just concentrate on
the horizontal and vertical line segments (32 possible) knowing that each
queen must hit the edge of the board in 3 or 4 of the horizontal directions.
n.3 =< 32
gives n=10 for k=1.
Andrew.
|
| Congratulations! This was an unsolved problem, proposed by Scott Kim;
it appeared in the Journal of Recreational Mathematics, Vol 12, Issue 1,
1979-1980, as problem 811 on page 52. You should write up and send in
your solution.
|