chuyên toán 9 – T's Lab

Trưa nay tôi được hỏi câu V trong đề thi tuyển sinh vào lớp 10 Chuyên toán năm học 2024-2025 của Hà Nội. Trong bài này tôi sẽ phát biểu bài toán tổng quát và giới thiệu một lời giải của bài toán đó.

Bài toán. Cho một số nguyên $n$ lớn hơn $1$ và một bảng ô vuông cỡ $n\times n$ . Ban đầu một số ô vuông của bảng được tô màu đỏ. Sau đó mỗi giây, các ô vuông có chung cạnh với ít nhất hai ô đỏ sẽ được tô đỏ. Hỏi ban đầu cần tô ít nhất bao nhiêu ô vuông để sau một thời gian, tất cả các ô của bảng đều được tô đỏ?

Lời giải. Cần tô màu ít nhất $n$ ô để sau một thời gian, tất cả các ô của bảng đều được tô đỏ.

Mỗi ô vuông con được xem là có cạnh $1$ . Gọi $k$ là số ô được tô đỏ ban đầu, và ở mỗi thời điểm gọi $S$ là tổng chu vi của các vùng được tô đỏ. Ta thấy ban đầu $S\leq 4k$ và nếu tất cả các ô của bảng mang màu đỏ thì $S=4n$ . Để ý rằng sau mỗi giây $S$ không tăng. Vì thế, nếu sau một thời gian các ô đều mang màu đỏ thì $4k\geq 4n$ , suy ra $k\geq n$ .