tailieunhanh - Báo cáo toán học: "Queens on Non-square Tori"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Queens on Non-square Tori. | Queens on Non-square Tori Grant Cairns Department of Mathematics La Trobe University Melbourne Australia 3086 Submitted January 29 2001 Accepted June 11 2001. MR Subject Classifications 05C69 05B99 Abstract We prove that for m n the maximum number of nonattacking queens that can be placed on the n X m rectangular toroidal chessboard is gcd m n except in the case m 3 n 6. The classical n-queens problem is to place n queens on the n X n chessboard such that no pair is attacking each other. Solutions for this problem exist for all for n 2 3 1 . The queens problem on a rectangular board is of little interest on the n X m board for m n one can obviously place at most m nonattacking queens and for 4 m n one can just take a solution on the m X m board and extend the board. Moreover the reader will easily find solutions on the 3 X 2 and 4 X 3 boards and so these give solutions on the n X 2 and n X 3 boards for all 3 n and 4 n respectively. In chess on a torus one identifies the left and right edges and the top and bottom edges of the board. On the n X n toroidal board the n-queens problem has solutions when n is not divisible by 2 or 3 3 and the problem of placing the maximum number of queens when n is divisible by 2 or 3 is completely solved in 2 . The traditional n-queens problem and the toroidal n-queens problem are closely related both logically and historically see 4 . However unlike the rectangular traditional board the queens problem on the rectangular toroidal board is interesting and non-trivial and yet it seems that it has not been studied. In order to work on the toroidal board we use the ring zi z i which we identify with 0 . i 1 and the natural ring epimorphism z zi x x i where x i is to be interpreted as the remainder of x on division by i. We give the squares of the n X m toroidal board coordinate labels x y x 2 m y 2 T n in the obvious way. The positive resp. negative diagonal is the subgroup P x m x n x 2 z resp. N x m x n x 2 z . .