Câu hỏi 116
Cho $m$ và $n$ là các số nguyên dương. Có $mn$ người trong một bữa tiệc, đứng thành một lưới $m \times n$. Một số người trong đó là cảnh sát, những người còn lại là khách. Một số vị khách có thể là tội phạm. Mục tiêu là xác định xem trong số các vị khách có tội phạm hay không.
Hai người được gọi là *kề nhau* nếu họ có chung một cạnh. Mỗi cảnh sát nhìn thấy những người kề mình và biết mỗi người đó có phải tội phạm hay không. Mặt khác, mỗi tội phạm sẽ đe dọa giết đúng một người kề mình (rất có thể là một cảnh sát!). Một cảnh sát bị đe dọa sẽ sợ hãi đến mức phủ nhận sự tồn tại của bất kỳ tội phạm nào trong số những người kề mình.
Tìm số cảnh sát ít nhất sao cho họ có thể đứng ở các vị trí trong bữa tiệc để đạt được mục tiêu. (Chú ý rằng số tội phạm là không biết trước và có thể không có tội phạm nào.)
Hai người được gọi là *kề nhau* nếu họ có chung một cạnh. Mỗi cảnh sát nhìn thấy những người kề mình và biết mỗi người đó có phải tội phạm hay không. Mặt khác, mỗi tội phạm sẽ đe dọa giết đúng một người kề mình (rất có thể là một cảnh sát!). Một cảnh sát bị đe dọa sẽ sợ hãi đến mức phủ nhận sự tồn tại của bất kỳ tội phạm nào trong số những người kề mình.
Tìm số cảnh sát ít nhất sao cho họ có thể đứng ở các vị trí trong bữa tiệc để đạt được mục tiêu. (Chú ý rằng số tội phạm là không biết trước và có thể không có tội phạm nào.)