Chủ đề này có 1 trả lời

[IHateMath]

Cho bàn cờ với kích thước $n \times n$. Ta tô màu một số ô vuông trên đó sao cho không có một bảng vuông con $2 \times 2$ nào có $3$ ô được tô màu. Hỏi có thể tô màu được nhiều nhất bao nhiêu trên bàn cờ đó? (Tính theo $n$)

[IHateMath]

Kí hiệu $f(n)$ thay cho số lớn nhất các ô vuông được tô màu.

Đáp số: $f(n)=\frac{n^2}{2}$ nếu $n$ chẵn và $f(n)=\frac{n(n+1)}{2}$ nếu $n$ lẻ.

Chứng minh

Trường hợp $n$ chẵn là hiển nhiên. Ta chỉ xét trường hợp $n$ lẻ. Ta sẽ chứng minh bằng quy nạp. Trong trường hợp cơ sở $n=1$ hiển nhiên $f(1)=1$, đúng. Giả sử ta đã chứng minh được rằng $f(2k-1)=(2k-1)k$ với $k$ nguyên dương nào đó. Trước hết ta sẽ chứng minh

$$f(2k+1)\leq(2k+1)(k+1)\quad (1)$$ 

Thật vậy ta cắt bảng $(2k+1)\times (2k+1)$ thành các bảng con như sau: một bảng $(2k-1)\times (2k-1)$ sao cho nó có chung một đỉnh với bảng lớn và phần còn lại cắt thành các bảng con $2\times 2$ chừa ra một hình L - Tetramino (là hình gồm 4 ô vuông xếp với nhau tạo thành hình chữ "L").

Theo giả thuyết quy nạp, trên bảng con $(2k-1)\times (2k-1)$ tô được nhiều nhất $(2k-1)k$ ô vuông còn trên hình L - Tetramino tô được nhiều nhất $3$ ô (điều này khá hiển nhiên), các bảng con $2\times 2$ (có đúng $2k-1$ bảng như vậy) thì tô được nhiều nhất $2$ ô, nên trên bảng ban đầu ta tô được nhiều nhất:

$$(2k-1)k+2(2k-1)+3=(2k+1)(k+1).$$

Điều này chứng tỏ $(1)$ đúng.

Giờ ta sẽ chỉ ra rằng dấu "=" trong $(1)$ là có thể xảy ra. Phần này thì khá đơn giản, chỉ cần tô xen kẽ các hàng là xong.

Vậy công thức đã cho cũng đúng với $n=2k+1$. Chứng minh kết thúc.

Bình luận: Trong trường hợp $n=5$ bài toán từng xuất hiện trên tạp chí THTT.