Can you solve the virus riddle? - Lisa Winer

Можете ли вы решить загадку о вирусе? — Лиза Винер

Переводчик: Daria Ziablitseva Редактор: Yekaterina Jussupova

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

Лаборатория представляет собой строение четыре на четыре из 16 комнат

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

[Ответ через: 3]

Answer in: 2

[Ответ через: 2]

Answer in: 1

[Ответ через: 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.

названной в честь математика XIX века Уильяма Роуэна Гамильтона.

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,

Этот тип задачи, классифицирующийся как NP-полная,

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.

Может быть, вам следует принять недавнее предложение о работе коммивояжёром.