Bài toán tổ hợp tô màu

Bài: Vùng nọ có khu đất vàng 100 × 100 m, chia ra làm 100 lô, mỗi lô 10 × 10 m. Vua bãi rác muốn lấn chiếm khu đất này nên sai tay chân đổ rác vào một số ô. Nếu một ô nào chưa có rác mà có ít nhất hai ô cạnh nó (có chung cạnh) đã bị đổ rác thì (đáng tiếc) hôm sau nhân dân cũng sẽ đổ rác vào ô đó. Nếu đến một ngày nào đó tất cả các ô đều bị đổ rác thì vua bãi rác sẽ chiểm khu đất. Nếu vua bãi rác muốn chiếm khu đất này thì lúc đầu cần đổ rác vào ít nhất mấy ô?

Giải

Ta đưa bài toán về mô hình bảng ô vuông kích thước 10 × 10 và mỗi ô bị đổ rác thì sẽ được tô đen. Mỗi bước biến đổi tương ứng với việc ta tô đen một ô chưa được tô và chung cạnh với ít nhất hai ô được tô đen. Do đó, ta chỉ cần tìm số ô đen được tô ban đầu sao cho sau một số hữu hạn bước biến đổi, ta có thể tô đen cả bảng. Gọi p là chu vi của tất cả các phần được tô đen. Ta chứng minh rằng sau mỗi bước biến đổi thì p không tăng. Thật vậy, do ở mỗi bước biến đổi ta tô đen một ô khi nó phải chung cạnh với ít nhất hai ô đen. Ta có các trường hợp sau: Chu vi không đổi, chu vi giảm 2 đơn vị, chu vi giảm 4 đơn vị.

Khi cả bảng được tô đen thì p' = 10 × 4 = 40. Do đó, để tô đen cả bảng ban đầu p ≥ p' = 40. Mà mỗi ô có chu vi là 4. Suy ra ban đầu cần tô ít nhất p/4 = 10 ô. Ta tô mười ô trên cùng một đường chéo chính thì sau hữu hạn bước biến đổi thì cả bảng sẽ được tô đen. Ban đầu vua cho đổ rác vào mười ô trên một đường chéo chính số 1. Ngày hôm sau các ô trên hai đường chéo chính số 2 sẽ bị đổ rác (do mỗi ô đều kề hai ô ở đường chéo số 1). Tiếp tục như vậy thì đến ngày thứ 10 cả khu đất sẽ bị đổ rác. Đáp số: 10 ô.