Một phòng máy tính có 5 × 5 bàn sắp xếp thành 5 hàng 5 cột. Người ta muốn treo các camera an ninh sao cho mỗi camera đặt ở một bàn có thể nhìn thẳng theo hàng, cột và hai đường chéo (như mô tả của hình...

Để giải quyết bài toán này, ta cần xác định cách đặt camera sao cho tất cả các bàn đều nằm trong vùng giám sát của ít nhất một camera. Mỗi camera có thể giám sát theo hàng, cột và hai đường chéo. Bước 1: Xác định vị trí đặt camera 1. Đặt camera ở trung tâm: - Đặt một camera ở bàn trung tâm (hàng 3, cột 3). Camera này sẽ giám sát toàn bộ hàng 3, cột 3 và hai đường chéo chính của ma trận 5x5. 2. Giám sát các hàng và cột còn lại: - Để giám sát các hàng và cột còn lại, ta cần thêm camera ở các vị trí khác. 3. Đặt camera ở các góc: - Đặt camera ở các góc của ma trận (hàng 1, cột 1), (hàng 1, cột 5), (hàng 5, cột 1), và (hàng 5, cột 5). Mỗi camera ở góc sẽ giám sát một hàng và một cột. Bước 2: Kiểm tra vùng giám sát - Camera ở trung tâm giám sát hàng 3, cột 3 và hai đường chéo. - Camera ở góc (1,1) giám sát hàng 1 và cột 1. - Camera ở góc (1,5) giám sát hàng 1 và cột 5. - Camera ở góc (5,1) giám sát hàng 5 và cột 1. - Camera ở góc (5,5) giám sát hàng 5 và cột 5. Kết luận Với cách bố trí này, tất cả các bàn trong phòng đều nằm trong vùng giám sát của ít nhất một camera. Do đó, cần ít nhất 5 camera để giám sát toàn bộ phòng.