Câu hỏi 10
Một chiếc bánh hình vuông $n \times n$ gồm $n^2$ ô vuông đơn vị. Dâu tây được đặt trên một số ô sao cho mỗi hàng và mỗi cột có đúng một quả; gọi cách sắp xếp này là $\mathcal{A}$.
Cho $\mathcal{B}$ là một cách sắp xếp khác cũng có tính chất đó. Giả sử mọi hình chữ nhật theo lưới có một đỉnh ở góc trên trái của bánh đều chứa số dâu tây của $\mathcal{B}$ không ít hơn số dâu tây của $\mathcal{A}$. Chứng minh có thể thu được $\mathcal{B}$ từ $\mathcal{A}$ bằng một số phép chuyển sau:
Chọn một hình chữ nhật theo lưới chỉ chứa hai quả dâu tây, ở ô góc trên phải và ô góc dưới trái; chuyển hai quả đó sang hai ô góc còn lại của hình chữ nhật.
Cho $\mathcal{B}$ là một cách sắp xếp khác cũng có tính chất đó. Giả sử mọi hình chữ nhật theo lưới có một đỉnh ở góc trên trái của bánh đều chứa số dâu tây của $\mathcal{B}$ không ít hơn số dâu tây của $\mathcal{A}$. Chứng minh có thể thu được $\mathcal{B}$ từ $\mathcal{A}$ bằng một số phép chuyển sau:
Chọn một hình chữ nhật theo lưới chỉ chứa hai quả dâu tây, ở ô góc trên phải và ô góc dưới trái; chuyển hai quả đó sang hai ô góc còn lại của hình chữ nhật.