Can you solve the computer virus riddle? - James Tanton

Переводчик: Yulia Kallistratova Редактор: Elena McDonnell

Your antivirus squad is up against a particularly sadistic bit

Вашему антивирусному отряду предстоит сразиться

с особенно изощрённым вирусом, завладевшим центральным процессором.

of malicious code that’s hijacked your mainframe.

What you’ve learned from other infected systems— right before they went dark—

Случаи ранее заражённых систем — до того, как все они отказали, —

is that it likes to toy with antivirus agents in a very peculiar way.

выявили, что зловредный код не прочь поиграть с антивирусами в игру.

It corrupts one of the 4 disks that run your mainframe,

Он заражает один из четырёх дисков, на которых расположен ЦПУ

represented by lights showing which are on and which off.

и лампочки которых показывают, включён данный диск или нет.

Then it selects one member of the antivirus squad— this’ll be you—

Потом выбирает одного из членов антивирусного отряда — например, тебя —

and brings them into the mainframe.

и переносит его в центральный процессор.

It tells them which disk it corrupted,

Вирус сообщает агенту, какой именно диск заражён,

allows the agent to switch a single disk on or off,

позволяет ему включить или выключить единственную лампочку,

then immediately de-rezzes the agent.

после чего немедля расправляется с агентом.

Your squad can make an all-out attack to break into the mainframe

Твой отряд может совершить одну лобовую атаку на ЦПУ

and destroy one disk before they’re wiped out.

и уничтожить один из дисков до того, как их всех прикончат.

If they destroy the corrupted one, the malware will be defeated.

Если они ликвидируют заражённый диск, вирус будет побеждён.

Any others, and the virus will erase the entire system.

А в случае атаки на любой другой диск вирус сотрёт целиком всю систему.

The lights are only visible within the mainframe,

Лампочки не видны за пределами ЦПУ,

so you won’t know until you get there which, if any, are on.

поэтому узнать, какие из них горят, можно только попав в систему.

How can you communicate, with your single action,

Как сообщить другим с помощью единственного действия,

which of the 4 disks has been corrupted?

который из четырёх дисков заражён?

Pause here to figure it out for yourself. Answer in 3

Нажми на паузу и реши задачу самостоятельно.

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

Answer in 2

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

Answer in 1

Ответ через: 1

The setting is a big clue for one solution.

Подсказка к решению — в тематике задачи.

Using binary code— the base two numbering system that only uses 1s and 0s—

Применяя бинарную, или двоичную, систему счисления, использующую только 0 и 1,

we can represent each of the 4 disks with a 2-bit binary number

можно представить каждый из четырёх дисков в виде двухразрядного двоичного числа

ranging from 00 for zero to 11 for three.

между 00, что соответствует нулю, и 11, что равно трём.

What we’re looking for now is some sort of mathematical operation

Нам требуется подобрать математическую операцию,

that can take the lit disks as input, and give the corrupted disk as an output.

на входе которой — включённые диски, а на выходе — заражённый диск.

Let’s consider one possibility.

Рассмотрим такую ситуацию.

Say that the corrupted disk was this one,

Допустим, это испорченный диск

and when you come in, no lights are on.

и ни одна лампочка не горит.

You could turn 11 on to indicate that disk.

Можно включить 11, что однозначно укажет товарищам на неисправный диск.

Okay, what if you came in and 11 was already on?

А что, если при твоём появлении 11 уже включён?

You have to switch one light.

У тебя в запасе лишь одно действие.

Which seems like the most innocuous to change?

Какой выключатель мало что изменит?

Probably 00, in that if you were to add 00 and 11,

Скорее всего, 00 — ведь, сложив 00 и 11,

you’d still get 11.

на выходе всё ещё получим 11.

So maybe the key is to think of addition of binary numbers,

То есть, похоже, ключ к решению — в сложении двоичных чисел,

with the sum of the lit disks communicating the corrupted disk number.

при котором сумма включённых дисков однозначно укажет номер неисправного.

This works great, until we start with a different hypothetical.

Всё сходится до тех пор, пока мы не изменим гипотезу.

What if 00 was the corrupted disk, and 01 and 10 were on?

Что, если 00 и есть заражённый диск, а лампочки на 01 и 10 включены?

Here, the sum of the lit disks is 11.

Здесь сумма включённых дисков равна 11.

But we need to change this to a sum of 00 with the flip of one switch.

А нам нужно одним действием превратить её в 00.

We have four options: turning switch 00 on gives us 11.

У нас четыре варианта: включив лампочку на 00, получим 11.

Turning 01 off takes us back to 10,

Выключив 01, получим 10,

and turning 10 off gives 01.

а выключив 10, получим 01.

None of those work.

Ни один из вариантов нам не подходит.

Turning switch 11 on gives us 110 by standard binary addition.

Если включить 11, то нормальное бинарное сложение даст нам 110.

But we don’t really want three digit numbers.

А нам совершенно ни к чему трёхзначные числа.

So what if— to keep the result a two digit number—

Тогда давайте — чтобы в результате осталось двоичное число —

we break the rules a bit and let this sum equal 22.

немного нарушим правила, и пусть сумма будет равна 22.

That’s not a binary number, but if we regard 2s as the same as 0s,

Это не бинарное число, но если отнестись к двойкам как к нулям,

that does indicate the correct disk.

то они также укажут нужный диск.

So this suggests a strategy:

Тогда стратегия следующая:

look at the sum of all the lighted disks we see,

смотрим на сумму всех дисков с включёнными лампочками,

regarding 2s as 0s.

считая двойки нулями.

If it’s already the correct result, flip 00,

Если результат получился верным, переключи диск с номером 00,

and if not, find the switch that will make the sum correct.

а если нет, найди тот выключатель, который сделает сумму верной.

You can see for yourself that any starting configuration

Сразу понятно, что любая изначальная конфигурация

can sum to any number from 00 to 11 with a flip of a switch.

может дать в сумме любое число между 00 и 11 единственным переключением.

The reason this works is related to a concept called parity.

Это работает благодаря характеристике числа,

Parity tells you whether a given value is even or odd.

указывающей, является оно чётным или нечётным.

In this case, the values whose parity we’re considering

В нашем случае чётность или нечётность интересующих нас значений

are the number of 1s in each digit place of our binary sums.

определяется количеством единиц в каждом разряде наших двоичных сумм.

And that’s why we can say that 2 and 0, both even numbers,

Именно поэтому двойку и ноль — оба чётных числа —

can be treated as equivalents.

можно считать эквивалентами.

By adding or subtracting 00, 01, 10, or 11,

Складывая или вычитая 00, 01, 10 или 11,

we can change the parity of either, both, or neither digit,

можно изменить чётность одного из чисел, обоих или ни одного из них

and create the disk number we want.

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

What’s incredible about this solution is that it works for any mainframe

Самое невероятное в этом решении то, что оно будет справедливым для любого ЦПУ

whose disks are a power of two.

с дисками, пронумерованными степенями двойки.

With 64 you could turn each activated disk into a 6-bit binary number

Имея 64 диска, каждый можно обозначить шестизначным двоичным числом

and sum the 1s in each column,

и сложить единицы в каждом столбце,

regarding any even sum as the same as 0 and any odd sum as 1.

считая каждую чётную сумму нулём, а каждую нечётную — единицей.

1,048,576 disks would be daunting, but entirely doable.

1048576 дисков — задача устрашающая, но тоже вполне решаемая.

Luckily, your mainframe is much smaller.

К счастью, ваша система гораздо меньше.

You make the valiant sacrifice and your team rushes in,

Ты геройски жертвуешь собой, и твой отряд врывается,

destroying the corruption and freeing the system.

обезвреживает заражённый диск и восстанавливает систему.