In From knights to kings, we were asked
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?
We found out that for a square board, we can't put all the knights next to their friends when $N>3$. What if we are using a $N\times M$ board ($N\ge M$) instead? For example, if $N=3,M=2$:
A B C
D E F
You only need to swap D and F to get a solution
A B C
F E D
It's fairly obvious that all $N\times 1$ and $N\times 2$ boards will work. What other board sizes will work under these conditions?
Answer
Assuming "castle" maneuvers are not a part of this drill: Also, symmetry is not drawn out; you can always flip these boards around.
Anything 4x4 and larger doesn't have a valid solution. A 4x4 board will generate knights with 4 friends. You can't place 5 friendly kings on a board where each is one move away from the other 4 (neglecting "castle" maneuvers!). That was incorrect reasoning. The "friendliness" is not contagious.
Anything 6x7 and larger definitely doesn't have a valid solution. This size board will result in knights with 8 friends, some of whom have 6 or more non-mutual friends. You can't arrange these 2 such that the first has access to all 8 and the second has access to 6 or more additional friends.
Square 6x6 not allowed.
Can't do 5x6 or larger. You'll end up with two knights that have 8 friends, 0 mutual friends. x has friends a-h, X has friends A-H:
. a . b .
c A . B d
C . x . D
e . X . f
E g . h F
. G . H .
They must go here on the King Board:
. . 0 0 0 . 0 0 0 . 0 0 0 . .
. . 0 x 0 . 0 x 0 . 0 x 0 . .
. . 0 0 0 . 0 0 0 . 0 0 0 . .
0 0 0 . . . 0 0 0 . 0 0 0 . .
0 X 0 . . . 0 X 0 . 0 X 0 . .
0 0 0 . . . 0 0 0 . 0 0 0 . .
Each of the friends of x and X (meaning a-h and A-H) have at least 2 non-mutual friends with the x's. This means none of them can go on the corners of the King Board, since they won't have access to anyone else, nor can they be boxed-in on an edge, so we can't solve this one.
Square 5x5 is not allowed.
Nor can you do 5x4:
a b c d
e f g h
i j k l
m n o p
q r s t
j and k each have 6 friends. Each of j's friends have at least 1 friend that isn't mutual with j (same goes for k). Also, since j and k have 0 friends in common, they must be diagonal from each other. These are the only places on the King Board where j and k could go and have access to 6 friends each. All of them puts one of their friends in a spot where they can't reach all of their own friends:
. . . . . . . . . . . .
. . j . . . j . . . j .
. k . . . . . . . . . .
. . . . . k . . . . k .
. . . . . . . . . . . .
Square 4x4 is not allowed.
3x4 is the largest that's good to go I've solved explicitly so far:
1 2 3
4 5 6
7 8 9
10 11 12
which means (knight: friends)
1: 6,8
2: 7,9
3: 4,8
4: 3,9,11
5: 10,12
6: 1,7,11
7: 2,6,12
8: 1,3
9: 2,4,10
10: 5,9
11: 4,6
12: 5,7
and valid solution:
3 8 1
4 11 6
9 2 7
10 5 12
No comments:
Post a Comment