Câu hỏi 167
Chúng ta xem xét một hình chữ nhật $m \times n$ được tạo thành từ các hình vuông đơn vị $m n$. Hai trong số các ô vuông đơn vị của nó được gọi là liền kề nếu chúng có một cạnh chung, và một đường dẫn là một chuỗi các ô vuông đơn vị trong đó hai phần tử liên tiếp liền kề nhau.
Mỗi đơn vị hình vuông của hình chữ nhật có thể được tô màu trắng hoặc đen. Nếu tất cả các hình vuông đều được tô màu thì hình chữ nhật được tô màu.
Gọi $N$ là số tất cả các cách tô màu sao cho có ít nhất một đường màu đen từ cạnh trái sang cạnh phải của hình chữ nhật. Hơn nữa, gọi $M$ là số tất cả các cách tô màu mà có ít nhất hai đường màu đen từ cạnh trái sang cạnh phải của hình chữ nhật không chứa một hình vuông chung.
Chứng minh rằng $N^{2} \geq M \cdot 2^{m n}$.
Mỗi đơn vị hình vuông của hình chữ nhật có thể được tô màu trắng hoặc đen. Nếu tất cả các hình vuông đều được tô màu thì hình chữ nhật được tô màu.
Gọi $N$ là số tất cả các cách tô màu sao cho có ít nhất một đường màu đen từ cạnh trái sang cạnh phải của hình chữ nhật. Hơn nữa, gọi $M$ là số tất cả các cách tô màu mà có ít nhất hai đường màu đen từ cạnh trái sang cạnh phải của hình chữ nhật không chứa một hình vuông chung.
Chứng minh rằng $N^{2} \geq M \cdot 2^{m n}$.