Can you solve the virus riddle? - Lisa Winer

Bạn có thể giải câu đố vi rút không? - Lisa Winer

Translator: Thanh Nhi Nguyen Reviewer: Lam Nguyen

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ử,

Your research team has found a prehistoric virus

preserved in the permafrost

được bảo tồn trong lớp bằng vĩnh cửu,

and isolated it for study.

và tách nó ra để nghiên cứu.

Sau một đêm dài làm việc,

After a late night working,

you're just closing up the lab when a sudden earthquake hits

khi bạn đóng cửa phòng thí nghiệm thì một trận động đất bất ngờ ập đến,

and knocks out the power.

và làm mất nguồn điện.

As the emergency generators kick in, an alarm confirms your worst fears:

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,

all the sample vials have broken.

những lọ chứa mẫu đã bị vỡ.

The virus is contained for now,

Vi rút vẫn chưa thoát ra,

but unless you can destroy it,

nhưng nếu bạn không tiêu diệt nó

the vents will soon open and unleash a deadly airborne plague.

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ệ,

Without hesitation, you grab your HazMat suit

and get ready to save the world.

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,

The lab is a four by four compound of 16 rooms

với lối vào ở góc hướng tây bắc, và lối ra ở góc hướng đông nam.

with an entrance on the northwest corner and an exit at the southeast.

Each room is connected to the adjacent ones by an airlock,

Mỗi phòng đều nối với phòng sát nó bằng một cửa không khí,

and the virus has been released in every room except the entrance.

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

To destroy it, you must enter each contaminated room

và kéo công tắc tự hủy diệt.

and pull its emergency self-destruct switch.

But there's a catch.

Nhưng có một quy tắc:

Because the security system is on lockdown,

Bởi vì hệ thống an ninh đang ở chế độ khẩn cấp,

once you enter the contaminated room,

một khi bạn bước vào phòng nhiễm vi rút,

you can't exit without activating the switch,

bạn không thể thoát ra nếu không kích hoạt công tắc tự huỷ.

and once you've done so,

Một khi bạn đã kéo công tắc,

you won't be able to go back in to that room.

bạn không thể bước vào lại căn phòng đó.

You start to draw out possible routes on a pad of paper,

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,

but nothing seems to get you to the exit

without missing at least one room.

mà không bỏ lỡ ít nhất một phòng.

So how can you destroy the virus in every contaminated room

Làm sao để bạn tiêu diệt vi rút trong tất cả các phòng,

and survive to tell the story?

mà vẫn sống sót để kể lại câu chuyện?

Pause here if you want to figure it out for yourself.

Dừng ở đây nếu bạn muốn tự tìm lời giải.

Answer in: 3

Ba.

Answer in: 2

Hai.

Answer in: 1

Một.

If your first instinct is to try to graph your possible moves on a grid,

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,

you've got the right idea.

thì bạn đã có ý tưởng đúng rồi đấy.

This puzzle is related to the Hamiltonian path problem

Câu đố này liên quan đến bài toán tìm đường đi của Hamiltonian,

named after the 19th century Irish mathematician William Rowan Hamilton.

được đặt tên theo nhà toán học Ireland ở thế kỉ 19, William Rowan Halmilton

The challenge of the path problem

Thử thách của bài toán

là tìm ra một sơ đồ có đường đi dạng Hamiltonian.

is to find whether a given graph has a Hamiltonian path.

That's a route that visits every point within it exactly once.

Đó 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 đủ,

This type of problem, classified as NP-complete,

is notoriously difficult when the graph is sufficiently large.

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,

Although any proposed solution can be easily verified,

we have no reliable formula or shortcut for finding one,

nhưng không có công thức hay lối tắt nào để tìm ra nó,

or determining that one exists.

hay chứng minh nó tồn tại.

And we're not even sure if it's possible for computers

Và cũng không chắc rằng liệu máy tính

to reliably find such solutions, either.

có thể chắc chắn tìm ra lời giải hay không.

This puzzle adds a twist to the Hamiltonian path problem

Câu đó này làm bài toán đường đi Hamiltonian thêm khó,

in that you have to start and end at specific points.

rằng bạn phải bắt đầu và kết thúc tại những điểm cố định.

But before you waste a ton of graph paper,

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

you should know that a true Hamiltonian path

isn't possible with these end points.

sẽ không tồn tại với những điểm kết thúc như vậy.

That's because the rooms form a grid with an even number of rooms on each side.

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ế,

In any grid with that configuration,

a Hamiltonian path that starts and ends in opposite corners is impossible.

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.

Here's one way of understanding why.

Để hiểu tại sao lại như vậy,

Consider a checkerboard grid with an even number of squares on each side.

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,

Every path through it will alternate black and white.

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,

These grids will all also have an even total number of squares

because an even number times and even number is even.

bởi vì tích của hai số chẵn cũng là số chẵn.

So a Hamiltonian path on an even-sided grid that starts on black

Do đó, đường đi Hamiltonian nếu bắt đầu ở ô đen,

will have to end on white.

thì phải kết thúc ở ô trắng.

And one that starts on white will have to end on black.

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,

However, in any grid with even numbered sides,

opposite corners are the same color,

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.

so it's impossible to start and end a Hamiltonian path on opposite corners.

It seems like you're out of luck,

Có vẻ như bạn đã hết cách,

unless you look at the rules carefully and notice an important exception.

nếu bạn không quan sát kĩ yêu cầu và chú ý một ngoại lệ.

It's true that once you activate the switch in a contaminated room,

Đúng là một khi bạn đã kích hoạt công tắc trong phòng nhiễm vi rút,

it's destroyed and you can never go back.

nó sẽ bị phá hủy và bạn không thể quay lại.

But there's one room that wasn't contaminated - the entrance.

Nhưng có một phòng không bị nhiễm là lối vào,

This means that you can leave it once without pulling the switch

Có nghĩa là bạn không cần phải phá hủy nó trong lần đầu đi qua,

and return there when you've destroyed either of these two rooms.

và trở lại sau khi đã phá hủy một trong hai căn phòng sát bên.

The corner room may have been contaminated

Căn phòng này có thể bị nhiễm vi rút khi ô thông gió mở,

from the airlock opening, but that's okay

nhưng không sao cả.

because you can destroy the entrance after your second visit.

vì bạn có thể phá hủy căn phòng sau khi quay trở lại.

That return trip gives you four options for a successful route,

Việc quay trở lại này cho bạn bốn lời giải khác nhau,

and a similar set of options if you destroyed this room first.

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.

Congratulations. You've prevented an epidemic of apocalyptic proportions,

but after such a stressful episode, you need a break.

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.

Maybe you should take up that recent job offer to become a traveling salesman.