MathNet 2017-part-01 — 176 bài (EN–VI) Câu hỏi 78

Khu trung tâm của một thị trấn có dạng hình chữ nhật $(2n+1) \times m$ được ghép từ các ô vuông $1 \times 1$. Để chiếu sáng khu vực này, người ta dùng các cột đèn có một bóng. Các cột đèn được đặt tại đỉnh của một số ô, và mỗi đèn chiếu sáng những ô 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 có một bóng đèn bị cháy.
(E. Barabanov, M. Karpuk, A. Voidelevich)