Можете ли да решите загатката с вируса? - Лиса Уайнър

Вижте целия урок: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Изследователският ви екип е открил праисторически вирус съхранен в замръзнала почва и са го изолирали за проучване. След късно доработване, тъкмо затваряте лабораторията, когато удря внезапно земетресение и счупва всички стъкленици с проби. Ще успеете ли да унищожите вируса преди да се отворят вентилационните отвори и да пуснат смъртоносна преносима зараза? Лиса Уайнър показва как.

Урок от Лиса Уайнър, анимация от Artrake Studio.

Изследователският ви екип
е открил праисторически вирус,

съхранен в замръзнала почва

и са го изолирали за проучване.

След късно доработване,

тъкмо затваряте лабораторията,
когато удря внезапно земетресение

и спира тока.

Докато резервният генератор се включва,
аларма потвърждава най-лошите ви страхове:

всички стъкленици с проби са се счупили.

Вирусът е задържан за сега,

но освен ако не го унищожите,

вентилационните шахти ще се отворят и
ще освободят смъртоносна преносима зараза.

Без колебания, грабвате
предпазния си костюм

и се приготвяте да спасите света.

Лабораторията е съставена
от 16 стаи, 4 на 4

с вход от северозападния ъгъл
и изход от югоизточния.

Всяка стая е свързана със съседната
с вакумна врата,

а вирусът се е освободил във всяка стая,
освен входната.

За да го унищожите, трябва да влезете
във всяка заразена стая

и да дръпнете аварийният
самоунищожаващ лост.

Но има уловка.

Понеже системата за безопасност
е заключена,

щом влезете в заразена стая,

не може да излезете,
без да дръпнете лоста,

а веднъж щом го направите,

няма да можете да се върнете в тази стая.

Започвате да рисувате
възможни маршрути на тефтер,

но нищо не изглежда
да ви води до изхода,

без да пропуснете поне една стая.

Как да унищожите вируса
във всяка заразена стая

и да оцелеете,
за да разкажете историята?

Спрете видеото тук,
ако искате сами да помислите.

Отговор след: 3

Отговор след: 2

Отговор след: 1

Ако първата ви мисъл е да пробвате да
нарисувате възможните ходове на таблица,

това е правилната идея.

Тази загадка е свързана
със задачата с Хамилтонови пътища

кръстена на ирландския математик
от 19-ти век Уилям Роуан Хамилтън.

Предизвикателното
на задачата с пътя,

е да се установи дали даден граф
има Хамилтонов път.

Това е път, който минава
през всяка своя точка точно веднъж.

Този тип проблеми,
класифицирани като NP-пълни,

са пословично трудни,
когато графът е доста голям.

Въпреки, че всяко предложено решение
може да се провери лесно,

нямаме надеждна формула или
лесен начин да намерим такова,

и да установим, че такова съществува.

А не сме сигурни дори,
че е възможно за компютрите

надеждно да открият решение, също.

Тази загатка добавя обрат към задачата
с път на Хамилтън

в това, че трябва да започнете
и завършите на конкретни точки.

Но преди да изхабите тон хартия с графове,

трябва да знаете, че
истинският път на Хамилтън,

не е възможен с тези крайни точки.

Това е така, понеже стаите формират таблица
с четен брой помещения на всяка страна.

Във всяка таблица с такова разпределение,

Хамилтонов път, който започва и завършва
на срещуположните ъгли е невъзможен.

Ето един начин да разберем защо.

Представете си шахматна дъска с равен брой
квадратчета на всяка страна.

Всеки път през нея ще редува черно и бяло.

Тези таблици също ще имат
четен брой квадратчета сумарно,

защото четно по четно дава четно число.

Така че Хамилтонов път през таблица,
с равни страни започваща с черно

ще трябва да завърши на бяло.

А такава започваща с бяло,
ще трябва да завърши на черно.

Обаче, във всяка решетка с равни страни,

срещуположните ъгли са с еднакъв цвят,

така че е невъзможно да започнеш и
завършиш Хамилтонов път

на противоположни ъгли.

Изглежда, че нямате късмет, освен

ако не погледнете правилата внимателно
и не забележите важно изключение.

Вярно е, че щом веднъж активирате лоста,
в заразена стая,

той е унищожен и не може да се върнете.

Но има една стая, която не е заразена -
входа.

Това значи, че може да я напуснете
веднъж без да дърпате лоста

и да се върнете там, когато
сте разрушили една от тези две стаи.

Стаята в ъгъла може да се е заразила

щом сте отворили вратите,
но това е приемливо,

понеже може да я разрушите
след второто ви посещение.

Това връщане ви дава четири опции
за успешен маршрут

и подобен набор от опции
ако сте унищожили тази стая първо.

Поздравления. Вие току що предотвратихте
епидемия от апокалиптичен размер,

но след толкова стресов епизод,
имате нужда от почивка.

Може би трябва да приемете
последното предложение за работа

да станете пътуващ търговец.