Câu hỏi 70
Khu trung tâm của một thị trấn có dạng hình vuông $n \times n$, được tạo thành từ các ô gạch $1 \times 1$. Để chiếu sáng khu vực này, người ta dùng các cột đèn, mỗi cột có một bóng đèn. Các cột đèn được đặt tại đỉnh của một số ô, kể cả trên biên của khu vực. Đèn trên một cột chiếu sáng tất cả các ô có một đỉnh tại vị trí cột đèn, và chỉ những ô đó.
Tìm số cột đèn ít nhất cần dùng để chiếu sáng toàn bộ khu vực, ngay cả khi một trong các bóng đèn bị cháy.
Tìm số cột đèn ít nhất cần dùng để chiếu sáng toàn bộ khu vực, ngay cả khi một trong các bóng đèn bị cháy.