full transcript

From the Ted Talk by Lisa Winer: Can you solve the virus riddle?

Unscramble the Blue Letters

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The vruis is contained for now, but unless you can destroy it, the vents will soon open and unleash a delady airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an enrnacte on the ntsoerhwt corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each cemtnatoniad room and pull its emergency self-destruct switch. But there's a catch. Because the security sstyem is on lockdown, once you enetr the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and sirvvue to tell the story? Pause here if you want to figure it out for yourself. aeswnr in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This pzzlue is related to the Hamiltonian path problem named after the 19th century Irish mhiitaameatcn William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a rutoe that vstiis every point within it exactly once. This type of prlbeom, classified as NP-complete, is notoriously difficult when the garph is sufficiently large. Although any proposed solution can be easily veieirfd, we have no reliable formula or shortcut for finding one, or determining that one exsits. And we're not even sure if it's possible for computers to reliably find such soilunots, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rmoos form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These gdris will all also have an even total number of squares because an even number tiems and even nbmuer is even. So a hilatomainn path on an even-sided grid that starts on black will have to end on whtie. And one that sattrs on white will have to end on blcak. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an iopamrntt ecxeption. It's true that once you activate the switch in a contaminated room, it's dyoteserd and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the sictwh and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've penrvteed an epidemic of apocalyptic pnopooritrs, but after such a stfsresul esdopie, you need a break. Maybe you should take up that recent job offer to become a talirevng saelsman.

Open Cloze

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The _____ is contained for now, but unless you can destroy it, the vents will soon open and unleash a ______ airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an ________ on the _________ corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each ____________ room and pull its emergency self-destruct switch. But there's a catch. Because the security ______ is on lockdown, once you _____ the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and _______ to tell the story? Pause here if you want to figure it out for yourself. ______ in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This ______ is related to the Hamiltonian path problem named after the 19th century Irish _____________ William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a _____ that ______ every point within it exactly once. This type of _______, classified as NP-complete, is notoriously difficult when the _____ is sufficiently large. Although any proposed solution can be easily ________, we have no reliable formula or shortcut for finding one, or determining that one ______. And we're not even sure if it's possible for computers to reliably find such _________, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the _____ form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These _____ will all also have an even total number of squares because an even number _____ and even ______ is even. So a ___________ path on an even-sided grid that starts on black will have to end on _____. And one that ______ on white will have to end on _____. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an _________ _________. It's true that once you activate the switch in a contaminated room, it's _________ and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the ______ and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've _________ an epidemic of apocalyptic ___________, but after such a _________ _______, you need a break. Maybe you should take up that recent job offer to become a _________ ________.

Solution

  1. destroyed
  2. black
  3. solutions
  4. northwest
  5. system
  6. prevented
  7. times
  8. graph
  9. exception
  10. virus
  11. deadly
  12. contaminated
  13. answer
  14. stressful
  15. verified
  16. exists
  17. episode
  18. traveling
  19. enter
  20. mathematician
  21. switch
  22. proportions
  23. salesman
  24. survive
  25. hamiltonian
  26. starts
  27. problem
  28. entrance
  29. white
  30. puzzle
  31. rooms
  32. grids
  33. number
  34. route
  35. visits
  36. important

Original Text

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.

Frequently Occurring Word Combinations

ngrams of length 2

collocation frequency
hamiltonian path 7
path problem 3
contaminated room 2

ngrams of length 3

collocation frequency
hamiltonian path problem 2

Important Words

  1. activate
  2. activating
  3. adds
  4. adjacent
  5. airborne
  6. airlock
  7. alarm
  8. alternate
  9. answer
  10. apocalyptic
  11. black
  12. break
  13. broken
  14. carefully
  15. catch
  16. century
  17. challenge
  18. checkerboard
  19. classified
  20. closing
  21. color
  22. compound
  23. computers
  24. configuration
  25. confirms
  26. congratulations
  27. connected
  28. contained
  29. contaminated
  30. corner
  31. corners
  32. deadly
  33. destroy
  34. destroyed
  35. determining
  36. difficult
  37. draw
  38. earthquake
  39. easily
  40. emergency
  41. ends
  42. enter
  43. entrance
  44. epidemic
  45. episode
  46. exception
  47. exists
  48. exit
  49. figure
  50. find
  51. finding
  52. form
  53. formula
  54. generators
  55. grab
  56. graph
  57. grid
  58. grids
  59. hamilton
  60. hamiltonian
  61. hazmat
  62. hesitation
  63. hits
  64. idea
  65. important
  66. impossible
  67. instinct
  68. irish
  69. isolated
  70. job
  71. kick
  72. knocks
  73. lab
  74. large
  75. late
  76. leave
  77. lockdown
  78. luck
  79. mathematician
  80. means
  81. missing
  82. moves
  83. named
  84. night
  85. northwest
  86. notice
  87. notoriously
  88. number
  89. numbered
  90. offer
  91. open
  92. opening
  93. options
  94. pad
  95. paper
  96. path
  97. pause
  98. permafrost
  99. plague
  100. point
  101. points
  102. power
  103. prehistoric
  104. preserved
  105. prevented
  106. problem
  107. proportions
  108. proposed
  109. pull
  110. pulling
  111. puzzle
  112. ready
  113. related
  114. released
  115. reliable
  116. reliably
  117. research
  118. return
  119. room
  120. rooms
  121. route
  122. routes
  123. rowan
  124. rules
  125. salesman
  126. sample
  127. save
  128. security
  129. set
  130. shortcut
  131. side
  132. sides
  133. similar
  134. solution
  135. solutions
  136. southeast
  137. specific
  138. squares
  139. start
  140. starts
  141. story
  142. stressful
  143. study
  144. successful
  145. sudden
  146. sufficiently
  147. suit
  148. survive
  149. switch
  150. system
  151. team
  152. times
  153. ton
  154. total
  155. traveling
  156. trip
  157. true
  158. twist
  159. type
  160. understanding
  161. unleash
  162. vents
  163. verified
  164. vials
  165. virus
  166. visit
  167. visits
  168. waste
  169. white
  170. william
  171. working
  172. world
  173. worst