Nhóm nghiên cứu của bạn đã tìm thấy một loại vi rút thời tiền sử,
được bảo tồn trong lớp bằng vĩnh cửu,
và tách nó ra để nghiên cứu.
Sau một đêm dài làm việc,
khi bạn đóng cửa phòng thí nghiệm thì một trận động đất bất ngờ ập đến,
và làm mất nguồn điện.
Khi máy phát điện dự phòng khởi động, điều bạn lo sợ nhất được thông báo,
những lọ chứa mẫu đã bị vỡ.
Vi rút vẫn chưa thoát ra,
nhưng nếu bạn không tiêu diệt nó
cửa thông gió sẽ mở và một bệnh dịch chết chóc sẽ lan truyền.
Bạn ngay lập tức mặc bộ đồ bảo vệ,
và sẵn sàng giải cứu thế giới.
Phòng nghiên cứu gồm 16 khu được xếp theo hình vuông,
với lối vào ở góc hướng tây bắc, và lối ra ở góc hướng đông nam.
Mỗi phòng đều nối với phòng sát nó bằng một cửa không khí,
và vi rút đã lan khắp các phòng ngoại trừ lối vào,
Để tiêu diệt nó, bạn phải đi vào từng phòng bị nhiễm
và kéo công tắc tự hủy diệt.
Nhưng có một quy tắc:
Bởi vì hệ thống an ninh đang ở chế độ khẩn cấp,
một khi bạn bước vào phòng nhiễm vi rút,
bạn không thể thoát ra nếu không kích hoạt công tắc tự huỷ.
Một khi bạn đã kéo công tắc,
bạn không thể bước vào lại căn phòng đó.
Bạn bắt đầu vẽ ra lộ trình thích hợp trên một mảnh giấy,
nhưng không có cách nào giúp bạn thoát được,
mà không bỏ lỡ ít nhất một phòng.
Làm sao để bạn tiêu diệt vi rút trong tất cả các phòng,
mà vẫn sống sót để kể lại câu chuyện?
Dừng ở đây nếu bạn muốn tự tìm lời giải.
Ba.
Hai.
Một.
Nếu bản năng đầu tiên của bạn là vẽ thử các đường đi có thể lên giấy,
thì bạn đã có ý tưởng đúng rồi đấy.
Câu đố này liên quan đến bài toán tìm đường đi của Hamiltonian,
được đặt tên theo nhà toán học Ireland ở thế kỉ 19, William Rowan Halmilton
Thử thách của bài toán
là tìm ra một sơ đồ có đường đi dạng Hamiltonian.
Đó là đường đi qua tất cả các điểm chứa trong nó chính xác 1 lần.
Bài toán này là bài toán NP đầy đủ,
sẽ cực kì khó giải khi sơ đồ đủ lớn.
Mặc dù có thể dễ dàng xác minh lời giải,
nhưng không có công thức hay lối tắt nào để tìm ra nó,
hay chứng minh nó tồn tại.
Và cũng không chắc rằng liệu máy tính
có thể chắc chắn tìm ra lời giải hay không.
Câu đó này làm bài toán đường đi Hamiltonian thêm khó,
rằng bạn phải bắt đầu và kết thúc tại những điểm cố định.
Nhưng để tránh mất công vẽ một đống sơ đồ,
trước tiên bạn nên biết rằng, một đường đi Hamiltonian
sẽ không tồn tại với những điểm kết thúc như vậy.
Bởi vì các phòng được xếp hình lưới với một số chẵn số phòng ở mỗi cạnh.
Đối với cấu trúc như thế,
không thể có đường đi Hamilton bắt đầu và kết thúc tại những góc đối diện nhau.
Để hiểu tại sao lại như vậy,
hãy liên tưởng đến một bàn cờ với một số chẵn hình vuông mỗi cạnh,
mọi con đường sẽ liên tục là trắng và đen.
Tổng số ô của bàn cờ cũng là số chẵn,
bởi vì tích của hai số chẵn cũng là số chẵn.
Do đó, đường đi Hamiltonian nếu bắt đầu ở ô đen,
thì phải kết thúc ở ô trắng.
Và một khi bắt đầu ở ô trắng thì phải kết thúc ở ô đen.
Tuy nhiên, bàn cờ với mỗi cạnh đều là số chẵn,
thì hai góc đối diện nhau lại cùng màu,
nên không thể có đường Hamiltonian bắt đầu và kết thúc ở hai góc đối diện.
Có vẻ như bạn đã hết cách,
nếu bạn không quan sát kĩ yêu cầu và chú ý một ngoại lệ.
Đúng là một khi bạn đã kích hoạt công tắc trong phòng nhiễm vi rút,
nó sẽ bị phá hủy và bạn không thể quay lại.
Nhưng có một phòng không bị nhiễm là lối vào,
Có nghĩa là bạn không cần phải phá hủy nó trong lần đầu đi qua,
và trở lại sau khi đã phá hủy một trong hai căn phòng sát bên.
Căn phòng này có thể bị nhiễm vi rút khi ô thông gió mở,
nhưng không sao cả.
vì bạn có thể phá hủy căn phòng sau khi quay trở lại.
Việc quay trở lại này cho bạn bốn lời giải khác nhau,
và tương tự nếu bạn chọn phá hủy căn phòng này trước.
Chúc mừng. Bạn vừa ngăn ngừa một bệnh dịch với quy mô khủng khiếp.
Sau thử thách cam go này, bạn cần nghỉ ngơi.
Có lẽ bạn nên chấp nhận lời đề nghị và thử làm một người bán hàng rồi đấy.