В канун юбилея Дня Победы вспомним математические задачи, решение которых внесло вклад в победу над фашизмом.

Взлом кода Энигма

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

Для передачи и приёма сообщений немецкими войсками использовалась шифровальная машина «Энигма», внешне напоминающая печатную машинку. В Блэтчи-парке недалеко от Лондона для расшифровки кода была создана секретная лаборатория, в которой была собрана группа специалистов по криптографии. Самым известным из них был английский математик Алан Тьюринг, который выполнил теоретическую часть работы, связанной с криптографическим анализом.

Но как удалось взламывать столь сложный шифр, ведь он менялся немцами каждую ночь? У шифровальной машины был замечен такой изъян, что каждая буква никогда не оставалась в подстановочном шифре на своём месте, т.е. вместо А никогда не подставлялась А и т.д.

Исследовательская группа располагала образцом машины «код энигма» и на её основе была сконструирована дешифровальная машина «бомба», повторявшая соединённых вместе нескольких десятков машин «энигма».

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

После окончания второй мировой войны Черчилль из соображений секретности приказал уничтожить все материальные следы программы исследований, в том числе и «бомбу». Но впоследствии британские любители истории по чертежам воссоздали машину, которая хранится в музее Блетчи-парка.

Тем, кто заинтересовался данной историей, могут посмотреть документальные фильмы «Человек, взломавший код нацистов» и «Алан Тьюринг. Обгоняющий время» (есть на youtube), а также художественные фильмы «Код энигма» (2001) и «Игра в имитацию» (2014).

Задача о немецких танках

Во время второй мировой войны объёмы выпуска немецких танков, например марки «Пантера» были оценены с высокой точностью при помощи статистических методов, и как оказалось впоследствии, данные статистических оценок были гораздо более эффективными, чем данные разведки.

Приведём вкратце суть статистического метода оценки.

Оказалось, что на всех выпущенных танках ставились месяц выпуска и серийные номера, причём каждый месяц нумерация вновь начиналась с единицы. Если танк оказывался подбитым в ходе военных действий, то его номер и серийный номер и месяц выпуска становились известны.

Оказывается, что полезную информацию для статистического анализа несут только два показателя - количество номеров и максимальное значение.

Можно легко решить такую вероятностную задачу. Если из набора чисел от 1 до n сделана случайная выборка без повторения к чисел, то вероятность того, что максимальным в этой выборке будет m, равна .

Например, вероятность того, что в лотерее «5 из 36» максимальным номером будет 25, равна . Это легко пояснить.

Всего k чисел из n можно выбрать  способами. Посчитаем число способов, при которых максимальным числом из k выбранных будет равно m (где k ≤ m ≤ n). При этом одно число из k нужно зафиксировать в позиции m, а остальные k-1 чисел могут принимать любые значения от 1 до m-1, и таким образом искомое число способов равно , а искомая вероятность - .

Но вернемся к оценке количества выпущенных танков. К сожалению, это задача, обратная к рассмотренной нами - мы научились строить вероятностное распределение m при известном n, а нужно наоборот.

Оказывается, что такое вероятностное распределение тоже можно построить, и на помощь приходит формула Байеса .

Более подробно о формуле Байеса.

Задача о бомбардировке Лондона

С июня по октябрь 1944 года фашистская Германия выпустила в сторону Англии 9.5 тысяч самоходных летающих бомб, из которых 2,4 тысяч упали на Лондон.

Британцы сильно переживали и задавались вопросом - падали ли бомбы на город случайным образом или поражали намеченные цели? Помочь ответить на этот вопрос смог метод, разаботанный выдающимся английским математиком и статистиком Карлом (Чарльзом) Пирсоном и который называется критерий Пирсона или хи-квадрат критерий.

Территория города была условно разбита на 24×24=576 квадратных участков и были собраны и обработаны данные о распределении числа бомб, попавших на участки.

Если бомбардировка проводилась бы хаотично, то полученные статистические данные о распределении числа попаданий должны были бы согласовываться с распределением Пуассона (о котором будет статья в одном из следующих выпусков).

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

Задача об анализе крови

Видный американский математик и экономист Роберт Дорфман во время Второй мировой служил в военно-воздушных силах США.

При прохождении новобранцами медицинской комиссии должны были обязательно сдаваться анализы крови на тест Вассермана. Это качественный анализ показывающий, что человек болен, если в его крови имеются определенные антитела. Для сдачи теста всеми призывниками требовалось большое количество тестовых препаратов и время на проведение тестирования.

И тогда Дорфман предложил простую и гениальную идею, позволяющую существенно сократить количество проводимых анализов.

Поскольку положительный тест реакции Вассермана встречается нечасто, то нужно смешать образцы крови нескольких призывников (k) и провести тест смеси. Если результат такого теста отрицательный, то это значит, что результат для каждого из тестируемых также отрицательный, и, таким образом, был проведен всего один тест вместо к, следовательно, сэкономлено k-1 тестов.

Если же тест положительный, болен один или несколько человек из k, и далее они проходят индивидуальные тесты, и это значит, был сделан один лишний тест.

Таким образом, возникает вопрос, как выбрать оптимальный размер группы тестируемых, ведь с одной стороны с ростом k растёт количество сэкономленных тестов в случае отрицательного результата, с другой стороны, растёт вероятность положительного результата (в результате чего будет потрачен дополнительный тест).

Найдём оптимальное значение k. Пусть p - вероятность положительного результата теста у одного призывника (эту величину легко оценить как частоту, вычисленную по совокупности уже исследованных призывников).

Тогда тест смеси из k образцов даст отрицательный результат с вероятностью (1-p)^k и положительный с дополнительной вероятностью, тогда в среднем понадобится (1-p)^k +(k+1)(1-(1-p)^k)=(k+1)-k(1-p)^k, что в пересчёте на одного призывника составит .

Заменим k действительной величиной x и будем искать точку максимума функции .

Минимум H(x) достигается в точке x₀, где x₀ - меньший корень уравнения H'(x) = 0, т.е. .

Если p мало (а в реальной ситуации так и было), то уравнение можно упростить, положив (1-p)^x≈1-px, ln(1-p) ≈-p, тогда получаем уравнение

, корень которого , тогда .

Например, при p=0.01 берём , H(x) ≈ 0.2. Это значит, что количество проведенных тестов уменьшится в 5 раз!

С.И. Доценко, кандидат физико-математических наук, доцент факультета информационных технологий КНУ имени Тараса Шевченко