On a NxN chess board $N^2$ knights are placed (one per cell). Each pair of knights, who control each other (i.e. one move away from each other) are friends.
One day all knights are promoted to kings. Is it possible to put them on the board (in different order) that all friends will be similarly one move away from each other?
For N = 1 or 2 it is trivial - there are no friends, so you don't have to change anything.
It is quite easy to do with N = 3. If you number them like this:
1 2 3
4 5 6
7 8 9
then 5-th knight has no friends and all others have 2 friends exacly. So we just place them friend-to-friend in a circle around the 5-th one:
1 8 3
6 5 4
7 2 9
and it is done.
But what about N > 3?
Answer
Unfortunately for the knights, if N>3 there is no way for all of the knights to be next to all of their friends.
Taking oerkelens' logic just a bit farther, we can show that N=6 doesn't work:
. a . a . .
a . . b a b
. . A . . .
a . . . B .
. a b a . .
. . . b . b
Here, A has 8 friends and B has 5, so there's only one arrangement that could possibly work:
a a a .
a A a b
a a B b
. b b b
Let's look at the "a" right next to B (call it C):
. a . a . .
a . . b a b
. . A . c .
a c . . B c
. a b C . .
. c . b . b
Now C has four new friends, and needs to be next to A and one of the "b"s. It won't work to be next to both A and B, so let's put it diagonally next to A (I'll use upper-right, but lower-left would be the same due to symmetry):
. c c c
a a C c
a A a b
a a B b
. b b b
Unfortunately, there's a problem - look at D:
. a . a . .
a d . b a b
. . A . c .
D c . . B c
. a b C . .
. c . b . b
It needs to be next to A, a "b", and a "c", as well as have a free spot open for it's friend "d". However, the only spot next to A that is also next to a "b" and a "c" does not have any space left for "d". So it's not going to work for N=6.
What about N=5?
. a . a .
a . . b a
. . A . .
a . . . B
. a b a .
We can easily fit B's friends in here, even when B is right next to A:
a a a b
a A B b
a a a .
Now that we have only 25 knights total, it is easier to assign letters to them when referring to them:
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Rather than continue to add friends around A and B until we run into a dead end, we'll look at it a different way. First, we'll categorize them by how many friends they have:
2 3 4 3 2
3 4 6 4 3
4 6 8 6 4
3 4 6 4 3
2 3 4 3 2
Obviously a piece can only be moved to a location that has at least as many squares around it as it does friends. That means that only the pieces that were in or near the corners (and have 2 or 3 friends) can be placed in a corner in the solution (where there are only 3 squares in which a friend could be placed). The way we find the problem is by considering the knight-distance (number of knight jumps to get to another location) between these pieces. For example, for A:
A 3 b
c . 1
2 a .
Knight-distance of 3 from B and F
A . . 3a.
. . 1 . 3b
. . . . 2a
. . . 2b.
. . . . .
Distance 3 from D and J, and from P and V (by symmetry)
A . . . 2
. . 1 . .
Distance 2 from E and U
A . . . .
. . 1 . .
. a . . 2
. . c . .
b . . 3 d
and distance 3 from X and T and distance 4 from Y. The distance is important because the king-distance in the solution cannot be greater than the original knight-distance. If we put A in a corner, then Y is the only one other piece that can fit into a corner that can be far enough away from A to actually be in a corner. So none of the pieces in a corner can remain in a corner.
What about B? Since A is distance 3 from each of the next-to-corner pieces, B must be distance 3 from A, E, U, and Y. Also,
. B . 2a.
2g. . . 2b
. . 1 . .
2f. . . 2c
. 2e . 2d .
B is distance 2 from each of the other next-to-corner pieces. This means that if B is in a corner, then none of the other pieces that can fit into a corner are far enough away to fill the other corners.
So it looks like there is no way to fill the corners in a way that satisfies everyone.
What about N=4?
A B C D 2 3 3 2
E F G H 3 4 4 3
I J K L 3 4 4 3
M N O P 2 3 3 2
For A, we have C, H, I, N, and P at distance 2, B, E, L, and O at distance 3, and D and M at distance 5. This suggests that if we put A in a corner, then D or M should be in the opposite corner, and two of B, E, L, and O should be in the two remaining corners. B and E are at distance 2 from each other, as are B and O, so we'll try B and L, like so:
A . . B
. . . .
. . . .
L . . M
Now let's consider the paths between A and B and between A and L:
A->G->I->B, A->J->H->B
A->G->N->L, A->J->C->L
Uh-oh, looks like both G and J are distance 2 from B and L. For any two given corners, here's where distance 2's overlap:
S b . B S a . A
a ab a . . ab b b
. b ab b . ab a a
A . a . . b . B
In both cases, there is only one locations next to the start (S) that is at distance 2 from the two destination corners. This means if A is in a corner, then we can only use one of B, E, L, and O in another corner. However, we can't use both D and M in the other two corners because they aren't far enough away from each other (only distance 2). So using A (and by symmetry D, M, and P) in a corner won't work.
Looks like B is our last chance (bad pun warning - help me, oh B one, you're my only hope). From B, we have distance 1 to H and I, distance 2 to D, E, M, and O, distance 3 to A, C, N, and P, and distance 4 to L. From what we just learned, A and P can't be moved into corners, so the only possibility is to have C, N, and L in the other corners. Unfortunately, this still won't work - C and N are only distance 2 from each other (they are both friends with E), so there's no way both of them can be in a corner.
No comments:
Post a Comment