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

Xem bản đầy đủ tại: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Nhóm nghiên cứu của bạn vừa tìm thấy một loài vi khuẩn thời tiền sử được bảo tồn trong lớp băng vĩnh cữu và đã tách nó để nghiên cứu. Sau một đêm dài làm việc, khi bạn đóng cửa phòng nghiên cứu ra vè thì có một trận động đất xảy ra, làm vỡ các bình đựng mẫu. Liệu bạn có thể tiêu diệt con vi rút trước khi cửa thông gió mở và làm bùng phát một bệnh dịch khủng khiêp? Lisa Winer sẽ cho bạn câu trả lời.

Bài giảng của Lisa Winer, hoạt hoạ bởi Artrake Studio

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.