Topic 39. CHESSBOARD PROBLEMS ON FINITE MAXIMA
Problem: Some chess pieces are put on a 8 × 8 chess board, with at most 1 piece in each square. After taking all pieces on any chosen 4 rows and 4 columns, there is at least 1 piece left on the board. Find the least number of pieces originally on the board.
Dịch đề: Người ta xếp một số quân cờ lên bàn cờ 8 × 8 sao cho mỗi ô vuông chỉ xếp tối đa một quân cờ. Khi lấy đi hết các quân cờ trên 4 hàng và 4 cột bất kỳ, thì bàn cờ luôn còn lại ít nhất một quân cờ. Hỏi ban đầu trên bàn cờ xếp ít nhất bao nhiêu quân cờ?
Lời giải:
Giả sử ban đầu trên bàn cờ có không quá 12 quân cờ. Nếu có ít nhất 4 hàng có nhiều hơn 1 quân cờ: Sau khi lấy hết quân cờ trên 4 hàng đó thì trên bàn cờ còn lại nhiều nhất 12 – 4 × 2 = 4 quân cờ. Các quân này có thể xếp trên nhiều nhất 4 cột, tiếp tục lấy hết quân cờ trên 4 cột đó thì không còn lại quân cờ nào. Vậy không thỏa mãn yêu cầu luôn còn lại ít nhất một quân cờ.
Nếu có ít hơn 4 hàng có nhiều hơn 1 quân cờ: Sau khi lấy hết quân cờ trên 4 hàng có nhiều quân cờ nhất, thì 4 hàng còn lại đều có không quá một quân cờ. Các quân này có thể xếp trên nhiều nhất 4 cột, tiếp tục lấy hết cờ trên 4 cột đó thì không còn lại quân cờ nào. Vậy không thỏa mãn yêu cầu.
Hình dưới đây chỉ ra một cách xếp 13 quân trên bàn cờ sao cho khi lấy hết cờ trên 4 hàng và 4 cột bất kỳ vẫn luôn còn lại một quân cờ.
Để ý rằng khi lấy hết quân cờ trên k hàng và (5 – k) cột với k = 1, 2, 3, 4, thì cũng không thể lấy hết quân cờ trong hình vuông 5 × 5 ở góc trên bên trái bàn cờ. Và cách duy nhất để lấy hết quân cờ trong hình vuông 3 × 3 ở góc dưới bên phải bàn cờ là lấy hết quân cờ trên 3 hàng hoặc 3 cột.
Lưu ý: Không phải tất cả cách xếp 13 quân lên bàn cờ đều thỏa mãn yêu cầu. Chúng tôi đưa ra một số ví dụ không thỏa mãn như sau: 4 hàng bị lấy hết cờ được đánh dấu bằng đường thẳng màu xanh, 4 cột bị lấy hết cờ tô màu vàng.
Kết luận: Số quân cờ ít nhất có thể trên bàn cờ ban đầu là 13.
Solution:
Suppose the total number of pieces is no more than 12. If there are at least 4 rows each with chesses more than 1, cover 4 such rows, the remaining pieces is at most 12 – 4 × 2 = 4, which can be covered by 4 columns, contradiction to that there is at least one piece left.
If there are less than 4 rows with pieces more than 1, covering 4 rows with the most pieces will leave all remaining row each contains no more than one piece. The remaining pieces can be covered by 4 columns, contradiction.
Put 13 pieces in the squares as the picture below will ensure that any 4 rows and 4 columns cannot cover all pieces. Note that pieces in the upper left 5 × 5 square cannot be covered by k rows and (5 – k) columns for any k = 1, 2, 3, 4; pieces in the lower right 3 × 3 square can be covered only by totally 3 rows (columns).
It worth mentioning that some construction of 13-piece-arrangement is not correct, (please see the figure in the Vietnamese solution for your reference). The 4 covered rows are indicated by blue lines, and the 4 covered columns are indicated by the yellow area.
To summarize, the least number of pieces is 13.