Câu hỏi 72
Một con thỏ vô hình ở tại một trong $N$ đỉnh của đồ thị $G$. Một số thợ săn tìm cách giết con thỏ. Mỗi phút tất cả họ đồng thời bắn: mỗi thợ săn bắn vào một đỉnh, và họ phối hợp chọn các đỉnh mục tiêu. Nếu con thỏ ở đỉnh mục tiêu khi bắn thì cuộc săn kết thúc. Nếu không, con thỏ có thể nhảy sang một đỉnh kề hoặc ở yên tại đỉnh của nó.
Các thợ săn biết một thuật toán cho phép giết con thỏ sau không quá $N!$ lượt bắn. Chứng minh rằng khi đó tồn tại một thuật toán cho phép giết con thỏ sau không quá $2^N$ lượt bắn.
Các thợ săn biết một thuật toán cho phép giết con thỏ sau không quá $N!$ lượt bắn. Chứng minh rằng khi đó tồn tại một thuật toán cho phép giết con thỏ sau không quá $2^N$ lượt bắn.