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

[Bui Ba Anh]

Cho hình vuông có kích thước $9x9$. Hỏi phải tô màu ít nhất bao nhiêu ô vuông đơn vị để luôn chọn được $1$ hình vuông $2x2$ có ít nhất $3$ ô màu đỏ

[hoangtubatu955]

Đầu tiên mình xét với trường hợp  $5x5$.
Để xuất hiện một hình vuông $2x2$ trong bảng $5x5$ thì ta phải cần ít nhất là 16 ô được tô màu.
Thật vậy, ta chia bảng $5x5$ thành như hình vẽ, với $ABCD$ là ô vuông $3x3$. $BGFE$ và $DHIK$ lần lượt là cách hình vuông $2x2$ và phần được tô màu xanh:
+Nếu thì hình vuông $3x3$ có 7 ô được tô màu thì ta có điều phải chứng minh ==> số màu tối đa để tô ô vuông kích thước $3x3$ để không có hình vuông $2x2$ nào thỏa mãn đề bài là 6.

+Nếu mỗi ô vuông $2x2$ có 3 ô được tô màu thì ta có điều phải chứng minh ===> Số màu tối đa để không có hình vuông thỏa mãn đề bài của TH này là 4.

+Còn đối với hình chữ L ở góc, nếu hình này được tô bởi 6 màu thì sẽ tồn tại hình vuông thỏa mãn đề bài ===> số ô tối đa để tô không thỏa mãn là 5.
Như vậy số mày ít nhất để tô trường hợp $5x5$ để tồn tại hình vuông thỏa mãn đề bài là: $6+4+5+1=16$

[hoangtubatu955]

Với k=45. Ta chỉ cần tô 5 cột xen kẽ là 1,3,5,7,9 thì ta thu được một cấu hình không thỏa mãn.
Bây giờ ta sẽ chứng minh k=46 thỏa mãn.
Thật vậy: Chia bảng $9x9$ thành như hình vẽ.
Giả sử rằng tồn tại một cấu hình nào đó mà với $k=46$ không thỏa mãn đề bài.
Chia hình vuông $9x9$ như hình vẽ.
Khi đó hình vuông $5x5$ ở giữa được tô tối đa 15 ô ( vì nếu 16 thì sẽ tồn tại hình vuông $2x2$ thỏa mãn đề bài).
Tương tự thì mỗi hình $2x2$ mỗi hình chỉ được tô tối đa 2 ô.
Còn 2 hình chữ L mỗi hình tối đa chỉ đươc tô  bởi $5$ màu.
Như vậy số màu tối đa để không có cấu hình nào thỏa mãn đề bài là $15+5.2+2.10=45<46$, vô lý.
Vậy $k$ cần tìm là 46.