Cho bảng ô vuông kích thước $2023 \times 2023$, ô vuông có kích thước $1 \times 1$ được gọi là ô

Câu hỏi số 798812:

Vận dụng

Cho bảng ô vuông kích thước $2023 \times 2023$, ô vuông có kích thước $1 \times 1$ được gọi là ô vuông đơn vị. Mỗi ô vuông đơn vị của bảng được tô bằng một trong 2 màu đen hoặc trắng, sao cho mỗi ô vuông đơn vị tô màu đen được kề với ít nhất 3 ô vuông đơn vị tô màu trắng (2 ô vuông đơn vị có cạnh chung được gọi là kề nhau). Hỏi số ô vuông đơn vị được tô màu đen nhiều nhất là bao nhiêu?

Quảng cáo

Xem lời giải

Câu hỏi:798812

Phương pháp giải

Chứng minh. Ta chứng minh bài toán tổng quát: với mỗi bảng $\left( {2n + 1} \right) \times \left( {2n + 1} \right)$ thì số ô được tô đen tối đa là $2n\left( {n + 1} \right)$.

Từ giả thiết suy ra $d_{1} + d_{2} + t_{1} + t_{2} = {(2n + 1)}^{2} = 4n^{2} + 4n + 1$ và $d_{1} + t_{1} = 8n$

Rõ ràng 4 ô ở 4 góc đều phải tô màu trắng. Như vậy còn $t_{1} - 4$ ô được tô màu trắng nằm ở đường biên, nhưng không nằm ở góc.

Giải chi tiết

Chứng minh. Ta chứng minh bài toán tổng quát: với mỗi bảng $\left( {2n + 1} \right) \times \left( {2n + 1} \right)$ thì số ô được tô đen tối đa là $2n\left( {n + 1} \right)$. Thật vậy, gọi $d_{1},d_{2}$ lần lượt là số ô được tô màu đen ở các đường biên và số ô được tô màu đen ở giữa. Tương ứng $t_{1},t_{2}$ lần lượt là số ô được tô màu trắng ở các đường biên và số ô được tô màu trắng ở giữa.

Từ giả thiết suy ra $d_{1} + d_{2} + t_{1} + t_{2} = {(2n + 1)}^{2} = 4n^{2} + 4n + 1$ và $d_{1} + t_{1} = 8n$

Rõ ràng 4 ô ở 4 góc đều phải tô màu trắng. Như vậy còn $t_{1} - 4$ ô được tô màu trắng nằm ở đường biên, nhưng không nằm ở góc.
Trước hết, ta chứng minh $d_{1} \leq 4n$. Thật vậy, nếu $d_{1} \geq 4n + 1$ thì theo nguyên lí Dirichlet, phải có 1 trong 4 đường biên có ít nhất $n + 1$ ô tô đen. Mà vì chỉ có $2n - 1$ ô (trừ 2 ô ở 2 góc), ta suy ra có 2 ô tô đen kề nhau ở biên. Điều này vô lí, vì mỗi ô đen này kề tối đa 2 trắng. Do đó $d_{1} \leq 4n$ và $t_{1} \geq 4n$. Tiếp theo, ta tính số ô trắng kề các ô đen thì thấy:

+) Với 4 ô trắng ở góc, mỗi ô kề tối đa 2 ô đen, nên được tính tối đa $2 \cdot 4 = 8$ lượt.

+) Với $t_{1} - 4$ ô trắng ở biên trừ góc, mỗi ô kề tối đa 3 ô đen, nên được tính tối đa $3\left( {t_{1} - 4} \right)$ lượt.

+) Với $t_{2}$ ô trắng ở giữa, mỗi ô kề tối đa 4 ô đen, nên được tính tối đa $4t_{2}$ lượt.

Mà mỗi ô đen trong nhóm $d_{1}$ thì kề đúng 3 ô trắng, mỗi ô đen trong nhóm $d_{2}$ kề ít nhất 3 và nhiều nhất 4 ô trắng. Từ đó ta tính tổng số lượt ô trắng được đếm thì suy ra:

$3d_{1} + 4d_{2} \leq 8 + 3\left( {t_{1} - 4} \right) + 4t_{2}$

Do đó, $7d_{1} + 8d_{2} + t_{1} \leq 4\left( {t_{1} + t_{2} + d_{1} + d_{2}} \right) - 4 = 16n^{2} + 16n.$

Mà $t_{1} \geq 4n \geq d_{1}$, nên $8\left( {d_{1} + d_{2}} \right) \leq 16n^{2} + 16n$, hay $d_{1} + d_{2} \leq 2n\left( {n + 1} \right)$. Tức là tổng số ô đen được tô không vượt quá $2n\left( {n + 1} \right)$.
Mặt khác, nếu ta tô bảng trên theo hình bàn cờ (các ô vuông ở góc tô màu trắng) thì được $2n\left( {n + 1} \right)$ ô tô đen, thỏa mãn điều kiện đề bài.
Áp dụng vào bài toán, với bảng $2023 \times 2023$ thì $n = 1011$, nên số ô tô đen tối đa là $2022 \cdot 1012$.

PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. PH/HS tham khảo chi tiết khoá học tại: Link