1
00:00:07,503 --> 00:00:10,598
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ử,

2
00:00:10,598 --> 00:00:12,469
được bảo tồn trong lớp bằng vĩnh cửu,

3
00:00:12,469 --> 00:00:14,980
và tách nó ra để nghiên cứu.

4
00:00:14,980 --> 00:00:16,763
Sau một đêm dài làm việc, 


5
00:00:16,763 --> 00:00:20,329
khi bạn đóng cửa phòng thí nghiệm 
thì một trận động đất bất ngờ ập đến,

6
00:00:20,329 --> 00:00:22,209
và làm mất nguồn điện.

7
00:00:22,209 --> 00:00:27,189
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,

8
00:00:27,189 --> 00:00:30,094
những lọ chứa mẫu đã bị vỡ.

9
00:00:30,384 --> 00:00:32,823
Vi rút vẫn chưa thoát ra,

10
00:00:32,843 --> 00:00:34,446
nhưng nếu bạn không tiêu diệt nó

11
00:00:34,446 --> 00:00:38,892
cửa thông gió sẽ mở
và một bệnh dịch chết chóc sẽ lan truyền.

12
00:00:39,832 --> 00:00:42,640
Bạn ngay lập tức mặc bộ đồ bảo vệ,

13
00:00:42,640 --> 00:00:44,910
và sẵn sàng giải cứu thế giới.

14
00:00:45,850 --> 00:00:49,641
Phòng nghiên cứu gồm 16 khu
được xếp theo hình vuông,

15
00:00:49,641 --> 00:00:54,371
với lối vào ở góc hướng tây bắc, 
và lối ra ở góc hướng đông nam.

16
00:00:54,791 --> 00:00:57,972
Mỗi phòng đều nối với phòng sát nó 
bằng một cửa không khí,

17
00:00:58,142 --> 00:01:02,290
và vi rút đã lan khắp các phòng
ngoại trừ lối vào,

18
00:01:02,640 --> 00:01:05,760
Để tiêu diệt nó, bạn phải 
đi vào từng phòng bị nhiễm

19
00:01:05,940 --> 00:01:09,000
và kéo công tắc tự hủy diệt.

20
00:01:09,160 --> 00:01:10,780
Nhưng có một quy tắc:

21
00:01:11,230 --> 00:01:13,722
Bởi vì hệ thống an ninh
đang ở chế độ khẩn cấp,

22
00:01:13,762 --> 00:01:16,111
một khi bạn bước vào phòng nhiễm vi rút,

23
00:01:16,111 --> 00:01:19,280
bạn không thể thoát ra
nếu không kích hoạt công tắc tự huỷ.

24
00:01:19,280 --> 00:01:21,070
Một khi bạn đã kéo công tắc,

25
00:01:21,070 --> 00:01:24,391
bạn không thể bước vào lại căn phòng đó.

26
00:01:25,041 --> 00:01:28,681
Bạn bắt đầu vẽ ra lộ trình thích
hợp trên một mảnh giấy,

27
00:01:28,900 --> 00:01:31,324
nhưng không có cách nào
giúp bạn thoát được,

28
00:01:31,324 --> 00:01:33,920
mà không bỏ lỡ ít nhất một phòng.

29
00:01:34,150 --> 00:01:38,100
Làm sao để bạn tiêu diệt vi rút 
trong tất cả các phòng,

30
00:01:38,101 --> 00:01:40,582
mà vẫn sống sót để kể lại câu chuyện?

31
00:01:40,872 --> 00:01:45,392
Dừng ở đây nếu bạn muốn tự tìm lời giải.

32
00:01:45,392 --> 00:01:47,036
Ba.

33
00:01:47,036 --> 00:01:48,890
Hai.

34
00:01:48,890 --> 00:01:49,923
Một.

35
00:01:50,603 --> 00:01:54,353
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,

36
00:01:54,670 --> 00:01:56,810
thì bạn đã có ý tưởng đúng rồi đấy.

37
00:01:56,810 --> 00:02:00,350
Câu đố này liên quan đến bài toán 
tìm đường đi của Hamiltonian,

38
00:02:00,350 --> 00:02:04,691
được đặt tên theo nhà toán học Ireland
ở thế kỉ 19, William Rowan Halmilton

39
00:02:05,211 --> 00:02:06,980
Thử thách của bài toán

40
00:02:06,980 --> 00:02:11,111
là tìm ra một sơ đồ có đường đi 
dạng Hamiltonian.

41
00:02:11,561 --> 00:02:15,491
Đó là đường đi qua tất cả các điểm
chứa trong nó chính xác 1 lần.

42
00:02:15,981 --> 00:02:19,431
Bài toán này là bài toán NP đầy đủ,

43
00:02:19,431 --> 00:02:23,451
sẽ cực kì khó giải khi sơ đồ đủ lớn.

44
00:02:23,951 --> 00:02:27,672
Mặc dù có thể dễ dàng xác minh lời giải,

45
00:02:27,672 --> 00:02:31,041
nhưng không có công thức
hay lối tắt nào để tìm ra nó,

46
00:02:31,221 --> 00:02:33,202
hay chứng minh nó tồn tại.

47
00:02:33,352 --> 00:02:36,181
Và cũng không chắc rằng liệu máy tính


48
00:02:36,181 --> 00:02:39,411
có thể chắc chắn
tìm ra lời giải hay không.

49
00:02:40,191 --> 00:02:43,331
Câu đó này làm bài toán
đường đi Hamiltonian thêm khó,

50
00:02:43,331 --> 00:02:47,072
rằng bạn phải bắt đầu và kết thúc
tại những điểm cố định.

51
00:02:47,482 --> 00:02:49,942
Nhưng để tránh mất công vẽ một đống sơ đồ,

52
00:02:49,942 --> 00:02:52,642
trước tiên bạn nên biết rằng,
một đường đi Hamiltonian

53
00:02:52,662 --> 00:02:55,032
sẽ không tồn tại với những 
điểm kết thúc như vậy.

54
00:02:55,032 --> 00:03:00,343
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.

55
00:03:00,973 --> 00:03:03,262
Đối với cấu trúc như thế,

56
00:03:03,262 --> 00:03:08,602
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.

57
00:03:10,222 --> 00:03:12,461
Để hiểu tại sao lại như vậy,

58
00:03:12,651 --> 00:03:16,952
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,

59
00:03:17,302 --> 00:03:20,232
mọi con đường sẽ liên tục là trắng và đen.

60
00:03:20,772 --> 00:03:25,162
Tổng số ô của bàn cờ cũng là số chẵn,

61
00:03:25,512 --> 00:03:29,003
bởi vì tích của hai số chẵn 
cũng là số chẵn.

62
00:03:29,413 --> 00:03:34,183
Do đó, đường đi Hamiltonian
nếu bắt đầu ở ô đen,

63
00:03:34,183 --> 00:03:36,243
thì phải kết thúc ở ô trắng.

64
00:03:36,243 --> 00:03:39,783
Và một khi bắt đầu ở ô trắng
thì phải kết thúc ở ô đen.

65
00:03:39,944 --> 00:03:43,002
Tuy nhiên, bàn cờ
với mỗi cạnh đều là số chẵn,

66
00:03:43,152 --> 00:03:45,802
thì hai góc đối diện nhau lại cùng màu,

67
00:03:45,912 --> 00:03:51,673
nên không thể có đường Hamiltonian
bắt đầu và kết thúc ở hai góc đối diện.

68
00:03:52,533 --> 00:03:54,734
Có vẻ như bạn đã hết cách,

69
00:03:54,734 --> 00:03:59,434
nếu bạn không quan sát kĩ yêu cầu
và chú ý một ngoại lệ.

70
00:04:00,524 --> 00:04:04,374
Đúng là một khi bạn đã kích hoạt
công tắc trong phòng nhiễm vi rút,

71
00:04:04,374 --> 00:04:07,043
nó sẽ bị phá hủy
và bạn không thể quay lại.

72
00:04:07,043 --> 00:04:10,923
Nhưng có một phòng
không bị nhiễm là lối vào,

73
00:04:11,253 --> 00:04:14,824
Có nghĩa là bạn không cần
phải phá hủy nó trong lần đầu đi qua,

74
00:04:14,824 --> 00:04:19,148
và trở lại sau khi đã phá hủy
một trong hai căn phòng sát bên.

75
00:04:19,718 --> 00:04:23,214
Căn phòng này có thể bị nhiễm
vi rút khi ô thông gió mở,

76
00:04:23,234 --> 00:04:24,483
nhưng không sao cả.

77
00:04:24,483 --> 00:04:27,713
vì bạn có thể phá hủy căn phòng
sau khi quay trở lại.

78
00:04:28,338 --> 00:04:32,314
Việc quay trở lại này cho bạn
bốn lời giải khác nhau,

79
00:04:32,314 --> 00:04:36,264
và tương tự nếu bạn chọn
phá hủy căn phòng này trước.

80
00:04:36,984 --> 00:04:41,974
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.

81
00:04:42,525 --> 00:04:45,959
Sau thử thách cam go này, 
bạn cần nghỉ ngơi.

82
00:04:45,959 --> 00:04:50,829
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.