Bài toán do Việt Nam đề nghị và được Hội đồng đề sửa đổi số liệu cho dễ hơn, phù hợp với trình độ học sinh.
Topic 11: Chessboard Problems
Problem
a. (Proposed by Vietnam)
With 64 black pawns and 64 white pawns, how many ways are there to place 64 pawns into the 64 squares of the chessboard, each pawn occupying 1 square, such that in each row and in each column the number of white pawns is even?
b. (IMSO 2018) With 16 black pawns and 16 white pawns, how many ways are there to place 16 pawns into the 16 squares of a 4x4 grid, each pawn occupying 1 square, such that in each row and in each column the number of white pawns is even?
Dịch đề
a. (Việt Nam đề nghị) Từ 64 quân tốt đen và 64 quân tốt trắng, có bao nhiêu cách sắp xếp 64 quân tốt vào 64 ô trên 1 bàn cờ vua 8x8, mỗi ô chứa một con tốt, sao cho trên mỗi hàng và mỗi cột số quân tốt trắng luôn là một số chẵn?
b. (IMSO 2018) Từ 16 quân tốt đen và 16 quân tốt trắng, có bao nhiêu cách sắp xếp 16 quân tốt vào 16 ô trên 1 bảng lưới 4x4, mỗi ô chứa một con tốt, sao cho trên mỗi hàng và mỗi cột số quân tốt trắng luôn là một số chẵn?
Lời giải
a. Xét hình vuông OMNP gồm 7 × 7 = 49 ô (1 × 1). Mỗi ô có 2 cách đặt 1 tốt đen hoặc 1 tốt trắng nên có 2^49 khả năng xếp 49 quân tốt tùy ý vào 49 ô.
Ta gọi hàng 1 là hàng điều chỉnh và cột a là cột điều chỉnh số lượng tốt trắng.
Nếu ở hàng thứ k (2 ≤ k ≤ 8) có tổng số tốt trắng là chẵn thì ô điều chỉnh (a;k) đặt tốt đen; còn nếu tổng số tốt trắng là lẻ thì ô (a;k) đặt tốt trắng. Sau điều chỉnh các hàng 2, 3, 4, 5, 6, 7, 8 cùng chứa một số chẵn tốt trắng.
Làm tương tự cho các cột b, c, d, e , f, g, h với các ô (b; 1); (c; 1)...(g; 1); (h; 1) được điều chỉnh để các cột b, c, d, e, f, g, h cùng chứa một số chẵn tốt trắng.
Ta chỉ cần chứng minh với cách sắp xếp trên có 1 cách duy nhất xếp vào ô cuối cùng là ô (a; 1) để số tốt trắng trên cột a và hàng 1 cùng là số chẵn.
Gọi tổng số tốt trắng xếp trong hình vuông OMNP là m; tổng số tốt trắng xếp trên các ô (a; 2), (a; 3) .. (a; 8) là p và tổng số tốt trắng trên các ô (b; 1), (c; 1), ... (g; 1), (h; 1) là q. Do số tốt trắng trên 7 hàng và 7 cột đều là chẵn nên ta có
m + p = 2u và m + q = 2v suy ra p – q = 2(u – v) tứclà p; q có cùng tính chẵn lẻ.
Nếu p và q cùng chẵn thì ô (a; 1) ta đặt tốt đen.
Nếu p và q cùng lẻ thì ô (a; 1) ta đặt tốt trắng.
Như vậy với mỗi cách sắp xếp tùy ý 49 quân tốt trong hình vuông OMNP thì luôn có 1 cách duy nhất để xếp vào các ô điều chỉnh sao cho số tốt trắng trong 8 hàng và 8 cột đều là số chẵn.Vậy có 2^49 cách sắp xếp 64 quân tốt thỏa mãn yêu cầu.
b.Tương tự như câu a, ta có 2^9 = 512 cách sắp xếp.
Solution
1. Consider the square OMNP consisting of 7 × 7 = 49 squares of size 1 × 1.
Each square may be placed with either a white pawn or a black pawn, thus there are 2^49 possible placements of 49 pawns into these 49 squares.
Let the 1st row and the ‘a’ column respectively be the “adjustment” row and the “adjustment” column (i.e. where we “adjust” the corresponding number of white pawns in the rows and columns). If the k-th row (2 ≤ k ≤ 8) has an even number of white pawns, then the adjustment square (a;k) will be placed with a black pawn. On the contrary, if the k-th row has an odd number of white pawns, then the adjustment square (a;k) will be placed with a white pawn. Hence, after adjustment all the rows from the 2nd to the 8th will each contain an even number of white pawns.
By similarly executing this procedure for columns ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’ with corresponding adjustment squares (b; 1) , (c; 1), ... (g; 1), (h; 1), we are guaranteed an even number of white pawns in each of the column ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’.
It remains to prove that for each of the above 249 placements, there exists only one way to place pawns into the last square i.e. square (a; 1), such that the numbers of white pawns in both the 1st row and the ‘a’ column are even.
Let the total number of white pawns placed in square OMNP be m; the total number of white pawns placed on squares (a; 2), (a; 3) .. (a; 8) be p; and the total number of white pawns placed on squares (b; 1), (c; 1), ... (g; 1), (h; 1) be q. Since the numbers of white pawns in the 7 rows and in the 7 columns are both even, we have:
m + p = 2u and m + q = 2v, thus p – q = 2(u – v) i.e. p and q have the same parity.
If p and q are both even, then a black pawn is placed in square (a; 1).
If p and q are both odd, then a white pawn is placed in square (a; 1).
Thus, for each arbitrary placement of 49 pawns into square OMNP, there always exists only one way to arrange the pawns in the adjustment squares such that the numbers of white pawns in each of the 8 rows and 8 columns are even.
In short, there are 2^49 possible placements of 64 pawns that satisfy the given requirements.
b. Similar to problem a, we have 2^9= 512 possible placements.