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

Это компьютерная игра для одного участника, которая имеется в каждом установочном комплекте операционной системы Microsoft. Цель игры состоит в том, чтобы очистить сетку от мин. Если вы щелкаете по квадратику на сетке, и там нет мины, то появляется число, показывающее, во скольких квадратиках вокруг данного есть мины. Если же вы щелкаете по мине… то взлетаете на воздух. Но саперный вызов на миллион долларов предлагает вам сделать несколько иное. Следующий рисунок не может появиться в настоящей игре, потому что никакое расположение мин не может дать такие числа (рис. 3.20). Число 1 означает, что лишь в одном из неоткрытых квадратиков есть мина, а число 2 означает, что заминированы оба.

Рис. 3.20

Но что можно сказать о следующем рисунке – можно ли увидеть такой в настоящей игре?

Рис. 3.21

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

Задача об упаковке

Вы руководите фирмой по переезду. Все ваши упаковочные ящики имеют одинаковую ширину и высоту, совпадающие с внутренними размерами вашего грузовика (ну, или чуть меньше этих размеров, так, чтобы их можно было разместить внутри). Но длина ящиков разная. Длина вашего грузовика 150 футов, а у имеющихся ящиков следующие длины: 16, 27, 37, 42, 52, 59, 65 и 95 футов.

Рис. 3.22. Упаковка коробок является математически сложной задачей

Можете ли вы найти комбинацию ящиков, которая наполнит грузовик самым эффективным способом? Вы должны найти алгоритм, определяющий для любого заданного числа N и набора меньших чисел n(1), n(2), …, n(r), существует ли набор меньших чисел, складывающийся в большее число.

Судоку

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

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

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

Решения

Лотерея «Тайн 4исел»

Выигрышные номера: 2, 3, 5, 7, 17, 42.

Задача коммивояжера

Вот маршрут протяженностью 238 миль:

Рис. 3.23

15 + 55 + 28 + 12 + 24 + 35 + 25 + 17 + 4 + 5 + 18 = 238

Глава 4 Случай кода, не поддающегося взлому

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