Тайны чисел: Математическая одиссея

Таблица 4.08

В первом столбце сетки 5 × 5 четное число решек, но добавленная вами монета лежит решкой вверх, указывая, что изначально там было нечетное число решек. Итак, монета, перевернутая вашим другом, находится в первом столбце. Перейдем теперь к рядам. Во втором ряду наблюдается рассогласование: там нечетное число решек, но ваша «контрольная цифра» говорит, что должно быть четное число. Теперь вы можете прочесть мысли вашего друга и возвестить: «Ты перевернул монету в первом столбце, во втором ряду». Вас ждет взрыв аплодисментов впечатленной публики.

Но что будет, если ваш друг перевернул одну из добавленных вами монет? Никаких проблем. Теперь нижний правый угол будет неправильно указывать на четность последнего ряда или последнего столбца. Если он не соответствует последнему ряду, то вы будете знать, что изменение произошло в последнем ряду. Поэтому вы можете проверить поочередно столбец за столбцом, чтобы понять, где произошло рассогласование. Если вы обнаружите, что несоответствие имеется в шестом столбце, значит, ваш друг перевернул монету в нижнем правом углу.

Вот опять та же сетка, где была перевернута одна из добавленных вами монет. Вы можете идентифицировать ее?

Таблица 4.09

Она находится в верхнем правом углу. Орел в нижнем правом углу говорит вам, что выше его в нижнем столбце должно быть четное число решек, но оно оказалось нечетным. Теперь выполните проверку по рядам. В первом ряду имеется рассогласование, поскольку орел в конце ряда говорит, что должно быть четное число решек слева от него. Но их нечетное число, из чего следует, что была перевернута монета в верхнем правом углу.

Подобные приемы лежат в основе так называемого кода с коррекцией ошибок, применяемого компьютерами для исправления ошибок, которые могли вкрасться в сообщения при их передаче. Замените орлы и решки на нули и единицы, и внезапно сетка становится цифровым сообщением. Например, каждый столбец в сетке 5 × 5, первоначально выложенной для показа фокуса, мог бы представлять букву в коде Бодо. Тогда сетка 5 × 5 стала бы сообщением длиной в пять букв. Дополнительные строки и столбцы добавляются компьютером для отслеживания ошибок.

Следовательно, пожелай мы отправить кодированное сообщение о третьем альбоме Coldplay, можно воспользоваться тем же приемом, что и ранее, примененным к сетке 5 × 4. Это даст возможность понять, где и когда вкрадываются ошибки. Вот как должно выглядеть название альбома, если цветные блоки заменить на 1, а пропуски на 0:

Таблица 4.10

Теперь добавим дополнительную строку и столбец с нулями и единицами, чтобы обозначить, четное или нечетное количество единиц имеется в каждой из строк и столбцов:

Таблица 4.11

Теперь представим, что при передаче сообщения произошла ошибка, и одно из чисел изменилось. В результате графический дизайнер получил вот что:

Таблица 4.12

Проверяя контрольные цифры в последнем столбце и строке, дизайнер может заметить ошибку. В данном случае имеется несоответствие во второй строке и в третьем столбце.

Подобные коды с коррекцией ошибок используются повсюду, от CD-дисков до связи с космическими аппаратами. Вы знаете, как бывает при разговоре по телефону, когда вы не можете разобрать все, что говорит ваш собеседник. При связи компьютеров друг с другом могут возникнуть схожие проблемы. Но использование умной математики позволило нам предложить такие варианты кодирования данных, которые помогают избавиться от этих сбоев. Именно так поступило агентство НАСА, когда космический аппарат «Вояджер-2» выслал первые фотографии Сатурна. Использование кодов с коррекцией ошибок позволило специалистам НАСА превратить неразборчивые изображения в кристально четкие.

Как честно кидать монету через интернет

Коды с коррекцией ошибок позволяют четко передавать информацию. Но зачастую мы хотим воспользоваться нашими компьютерами, чтобы поделиться секретными сведениями. Мария, королева Шотландии, лорд Нельсон или кто-либо другой, вознамерившийся обмениваться секретными сообщениями, должен был сначала встретиться со своим агентом, чтобы договориться о коде, который будут использовать обе стороны. Но в наш компьютерный век у нас то и дело появляется необходимость послать секретные сведения. При совершении покупок онлайн мы щелкаем по веб-сайтам и посылаем данные своих кредитных карт людям, с которыми никогда не встречались. Совершение сделок через интернет было бы невозможно со старой криптографией, когда требовалась первоначальная встреча с глазу на глаз. К счастью, у математики есть решение.

Чтобы объяснить его идею, давайте начнем с простого сценария. Я собираюсь играть в шахматы через интернет. Я живу в Лондоне, а мой соперник – в Токио. Мы хотим бросить монету, чтобы решить, кто будет ходить первым. «Орел или решка?» – спрашиваю я у своего соперника по электронной почте. «Орел», – отвечает он. Я подбрасываю монету и пишу: «Решка. Я начинаю». Существует ли возможность удостовериться, что я не сжульничал?