Câu hỏi 81
Cho $G$ là một đồ thị có đường kính $2$ với $2019$ đỉnh. $62$ cảnh sát và $1$ tên trộm được đặt tại các đỉnh của đồ thị $G$. Mọi người đều nhìn thấy tất cả những người khác, và họ di chuyển theo lượt. Ở mỗi lượt, mỗi người có thể đứng yên tại đỉnh của mình hoặc đi tới một đỉnh kề bất kỳ (mỗi cảnh sát đứng yên hay di chuyển độc lập với những người khác và các cảnh sát phối hợp hành động trong suốt trò chơi). Tên trộm đi trước, sau đó các cảnh sát di chuyển (đồng thời), rồi tên trộm lại di chuyển, rồi đến các cảnh sát, v.v. Tên trộm bị bắt nếu hắn ở tại đỉnh có cảnh sát. Chứng minh rằng các cảnh sát có thể bắt được tên trộm.