a) Cho hình vuông 3 × 3. Nêu cách vẽ sao cho tô ít nhất thoả mãn cho tất cả các hình vuông

a) Giả sử hình vuông 4 × 4 được tô màu một số ô sao cho trong mỗi hình vuông 2 × 2 bất kì có đúng 2 ô được tô màu. Hình vuông 4 × 4 được chia thành 4 hình vuông 2 × 2 nên trong 16 ô vuông nhỏ có đúng 8 ô được tô màu.

Để số ô được tô màu trong hình vuông 3 × 3 là ít nhất thì phải tô nhiều ô nhất có thể ở 7 ô vuông nhỏ phía ngoài.

Đế ý rằng cột 2 và cột 4 số ô tô màu sẽ giống nhau, hàng 2 và hàng 4 số ô tô màu giống nhau, do đó ta có thể tô màu cho nhiều nhất 5 6 trong 7 ô phía ngoài.

Ví dụ ta tô như hình sau:

Vậy cần tô ít nhất: 8 – 5 = 3 (0) ở hình vuông 3 × 3 thoả mãn yêu cầu bài toán. Ví dụ ta tô màu như sau:

b) Giả sử hình vuông 8 × 8 được tô màu một số ô sao cho trong mỗi hình vuông 4 × 4 bất kì có đúng 5 ô được tô màu. Hình vuông 8 ×8 được chia thành 4 hình vuông 4 × 4 nên trong 64 ô vuông nhỏ có đúng 20 ô được tô màu.

Để số ô được tô màu trong hình vuông 7 × 7 là ít nhất thì phải tô nhiều ô nhất có thể ở 15 ô vuông nhỏ phía ngoài.

Đế ý rằng cột 4 và cột 8 số ô tô màu sẽ giống nhau, hàng 4 và hàng 8 số ô tô màu giống nhau, do đó ta có thể tô màu cho nhiều nhất 11 ô trong 15 ở phía ngoài.

Ví dụ ta tô màu như hình sau:

Vậy cần tô ít nhất: 20 – 11 = 9 (ô) ở hình vuông 7 × 7 thoả mãn yêu cầu bài toán.

Ví dụ ta tô màu như sau: