Факторизация человечности (ЛП)

Теперь надо бы сообразить, как эти маленькие сообщения составить вместе. К сожалению, они все были разных размеров, которые не повторялись от страницы к странице. Первое сообщение первой из 48 групп состояло из 118 301 бита (произведение простых чисел 281 и 421), тогда как в первом сообщении второй страницы было 174 264 бит (произведение простых 229 и 761).

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

Однако Кайл мог бы написать для неё программу, которая бы это сделала.

После того, что случилось вчера вечером, она колебалась. Что она ему скажет?

Она собралась с духом и взяла трубку телефона.

— Алло? — произнёс голос Кайла.

Он, несомненно, знал, что звонит Хизер; он мог прочитать это в строке статуса своего телефона. Но в его голосе не было заметно особенной теплоты.

— Привет, Кайл, — сказала Хизер. — Мне нужна твоя помощь.

— Вчера она тебе была не нужна, — холодно ответил он.

Хизер вздохнула.

— Прости. На самом деле нужна была. Но время сейчас непростое для всех нас.

Кайл молчал. Хизер почувствовала необходимость заполнить паузу.

— Нужно время, чтобы во всём разобраться.

— Прошёл уже год, — сказал Кайл. — Сколько ещё тебе нужно?

— Я не знаю. Слушай, я сама не рада, что позвонила; не нужно было тебя беспокоить.

— Да всё в порядке, — ответил Кайл. — У тебя что-то важное?

Хизер сглотнула, потом заговорила:

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

— Правда?

— Ага.

— И сколько всего таких групп?

— Ровно сорок восемь.

— И ты подумала — что? Ты подумала, что отдельные сообщения складываются в сорок восемь ещё больших по размеру страниц?

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

Кайл издал звук, похожий на презрительное фырканье.

— И нечего надо мной смеяться, — сказала Хизер.

— Нет… нет, я не о том. Прости. Просто это забавно. Видишь ли, это задача покрытия.

— Да?..

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

— И что?

— Просто забавно, что центавряне выбрали для своих сообщений формат, который был предметом больших дебатов в человеческом сознании, вот и всё.

— Гмм. Но ты сказал, что задача решаема?

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

— Я об этом не подумала, но ты прав. Когда ты сможешь это сделать?

— Ну, на самом деле я сейчас очень занят — прости, но это так. Но я могу посадить за это одного из своих аспирантов. И тогда у нас будет ответ через пару дней.

— Спасибо, Кайл, — сказала Хизер так тепло, как только смогла.

Она почти услышала, как он пожимает плечами.

— Всегда к твоим услугам, — ответил он и положил трубку.

13

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

На этих квадратах, представленных в виде чёрных и белых пикселей, было видно множество круговых  структур. Круги были разных диаметров — какие-то большие, какие-то маленькие. Диаметры также распадались на категории — кругов с уникальными значениями диаметров не было.

К сожалению, кроме кругов — которые казались хорошим косвенным свидетельством в пользу того, что плитки действительно предполагалось расположить именно таким способом — никаких других осмысленных фрагментов так и не появилось. Она надеялась на нечто вроде книги с картинками о четырёх дюжинах страниц: «Сорок восемь видов горы Альфа Центавра».

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