number of nonattacking king config on an nxn chess board, $100 Prize

[imfatandugly]

I worked on this for awhile, couldn't find anything really worth mentioning. I'll give $50 for an implicit solution (not involving matrices), $50 for an asymptotic estimate, $75 for a generating function, and $100 for an explicit solution. I'll pay the first person to answer any of these, but no more (i'm not that rich).

Just so we are clear for n=1, there are only two configurations, 1 king or no kings. For n=2, there are 5, 4 where there is a king on a corner and one where there are no kings on the board.

[neverforgetlol]

interesting problem, you are going to have 1 + n^2 possibilities using 0 or 1 king, just have to figure out for two and add that.

here's what I have for two kings for n = 3. so answer would be 1 + 3^2 + 28 = 38

<font class="small">Code:</font><hr /><pre>
4 3 4
3 0 3
4 3 4</pre><hr />

for n = 4. 1 + 4^2 + 156 = 173.

<font class="small">Code:</font><hr /><pre>
12 10 10 12
10 7 7 10
10 7 7 10
12 10 10 12</pre><hr />

So when n is even we just need to find the numbers for one quarter of the box. For n odd do the same but the middle square is counted seperately.

[neverforgetlol]

Continuing on this

Consider an n x n board. Each corner has itself and three squares the king cannot be on, so n^2-4 configs for the other king. Every other square on the outside border has six squares the other kind cannot be on, so n^2-6. Every other square (that is, not on the edge or a corner) has n^2-9 possible squares for the other king.

for a n x n board, You should have 1 [0 kings]+ n^2 [1 king] + 4(n^2-4) [corners] + (4n-8)(n^2-6) [edges] + (n^2-4n+4)(n^2-9) [inner squares] possible configs.

[neverforgetlol]

reducable to

(33-24n-3n^2+4n^3) + (n-2)^2 *(n-3)(n+3)

= n^4 - 8n^2 + 12n - 3

pm for pay info [img]/images/graemlins/tongue.gif[/img]

[bigpooch]

I get a different number of configurations for n=3: 35. If
S(n,k) denotes the number of configurations on an nxn board
with k nonattacking kings, then as you stated, clearly

S(n,0)=1, and S(n,1)=n^2.

S(3,0)=1, S(3,1)=9, S(3,2)=16, S(3,3)=8, S(3,4)=1 and
S(3,k)=0 for k&gt;=5.

A useful note is that the maximum number of kings on an
nxn board with none of them attacking another is given by
(m^2)/4 where m is the least even number &gt;=n (I found this
at Wolfram Mathworld: "Kings Problem").

A "nice" proof of the explicit solution may require more
than one "key idea".

[neverforgetlol]

I just realized for n = 3 the corners should all be 5, not 3, giving an answer of 42 not 38.. So my equation is right for any n!! ship the money!

[BruceZ]

[ QUOTE ]
interesting problem, you are going to have 1 + n^2 possibilities using 0 or 1 king, just have to figure out for two and add that.

[/ QUOTE ]

I think he wants any number of kings, not just 0,1, or 2. If he only wanted legal positions, he wouldn't consider 0 or 1 king. If he just needs to add the result for 2 kings to 1 + n^2, the result for 2 kings is 0 for n &lt; 3, and for n &gt;= 3 it is

C(n^2,2) - 2*(n-1)*n - 2*(1+2+3 +...+ n-1 + n-2 ... + 1)

= C(n^2,2) - 2*(n-1)*n - 2*(n-1)^2

= C(n^2,2) - 2*(n-1)*(2n-1).

That is, there are C(n^2,2) total ways to choose 2 squares, minus (n-1)*n adjacent horizontal squares and another (n-1)*n adjacent vertical squares, minus (1+2+3 +...+ n-1 + n-2 ... + 1) = (n-1)^2 diagonal adjacent pairs in each of 2 directions. This ignores the color of the kings.

I checked these for n=3 which gives 16, and n=4 which gives 78, and these appear to be correct (for 2 kings).

[neverforgetlol]

Well I didn't get that impression.. anyway my equation is right for 0-2 kings. damnit. Mine assumes color matters of course, which is why I get twice your answer.

[BruceZ]

[ QUOTE ]
Well I didn't get that impression.. anyway my equation is right for 0-2 kings. damnit. Mine assumes color matters of course, which is why I get twice your answer.

[/ QUOTE ]

Actually I started the same way you did (perhaps you saw what I had up here briefly?), but that method has a double counting problem for n &gt;=5.

[neverforgetlol]

[ QUOTE ]
[ QUOTE ]
Well I didn't get that impression.. anyway my equation is right for 0-2 kings. damnit. Mine assumes color matters of course, which is why I get twice your answer.

[/ QUOTE ]

Actually I started the same way you did (perhaps you saw what I had up here briefly?), but that method has a double counting problem for n &gt;=5.

[/ QUOTE ]

I didn't see anything you did until I finished my own work [img]/images/graemlins/smile.gif[/img]

I am a bit of a numbers guy.. I just did a different method.

Are you saying my method doesn't work for large n? If order matters (that is, color) it works just fine.