Занимательная индустрия

Автор: Леонид Левкович-Маслюк
Опубликовано в журнале "Компьютерра" №43 от 16 ноября 2004 года.

Авторы статей, составляющих тему этого номера, знают о предмете — интеллектуальных развлечениях и занимательной математике — всё. Евгений Скляревский (автор идеи сегодняшней темы и большинства иллюстраций) и Константин Кноп не только представили и прокомментировали широчайший спектр рекреационно-математических и интеллектуально-игровых ресурсов в Сети, но и — самое интересное! — подошли к делу с совершенно разных позиций — и по отбору материала, и по стилистике комментариев. Обе статьи, однако, роднит искренняя радость авторов от того, что все это — такое увлекательное, такое яркое, иногда блистательно остроумное — не просто существует, а живет полнокровной жизнью и энергично развивается. Вне всякого сомнения, отрасль переживает бурный расцвет.

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

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

На мой взгляд, самое ценное свойство «занимательной математики» — ее способность постоянно напоминать о том, что грань между «занимательной» и «настоящей» наукой эфемерна. Проиллюстрируем это малоизвестным (во всяком случае, по сравнению с игрой «Жизнь») примером из творчества Джона Хортона Конвея (John Horton Conway). Кажется, «КТ» еще не писала об этой мини-теории, которую автор назвал теорией «Аудиоактивного распада» (audioactive decay; я узнал о ней лет двадцать назад из лекции одного из крупнейших современных математиков Юрия Манина).

Любопытно, что «аудиоактивный распад» связан с широко известным каждому программисту кодированием длин серий (run-length encoding, RLE). RLE — народный, я бы сказал, метод сжатия данных, входящий в состав многих известных алгоритмов (например, JPEG). Если в файле встретилась строка из ста семерок, ее можно сильно сжать, заменив строкой вроде «N100S7». Реализаций этой нехитрой идеи существует великое множество (обычно она применяется к двоичным данным). Но что будет, если применить RLE к результатам RLE? Конвей исследовал динамику итераций очень похожего процесса (впрочем, ни о каком RLE он не упоминает). Знаменитую последовательность Look-and-Say (вот о ней «КТ» точно писала!): 1, 11, 21, 1211, 111221, 312211… можно интерпретировать как результат последовательного применения «наивного» (то есть без префиксов N, S или аналогичных конструкций) RLE к строке (1). Действительно, первая итерация от строки (1) дает (11), то есть «одна единица», следующая итерация дает (21) — «две единицы», из этого получается (1211), «одна двойка, одна единица», и т. д. Конвей взял произвольную исходную строку положительных целых чисел и получил фантастические результаты. Как выяснилось, любая исходная последовательность распадается на участки, эволюционирующие независимо друг от друга. Если участок только один, последовательность называется атомом. Оказывается, атомы можно перечислить. «Обычных» атомов 92. Их обозначают элементами из таблицы Менделеева: водород (H) — (2,2), гелий (He) — (1,3,1,1,2,2,2,1,1,3,3,2,1,1,3,2,2,1,1,2,2,1,1,2,1,3,3,2,2,1,1,2), и так далее, до протактиния (Pa) — (1,3) и урана (U) — (3). Кроме того, есть две бесконечные серии трансурановых изотопов плюс ряд «экзотических» атомов. Конвей сформулировал «Космологическую теорему»: после не более чем 25 итераций любой атом («кроме старого зануды водорода») распадается на последовательность обычных и трансурановых атомов; отношение длин (измеренных в количестве атомов) результатов последовательных итераций стремится к «мировой константе» l = 1,303577… (ее точное значение есть максимальный корень уравнения 71-й степени: x⁷¹ – x⁶⁹ – 2x⁶⁸ – … + 3x – 6 = 0). В статье «The weird and wonderful chemistry of audioactive decay» (в сборнике «Open problems of communication and computation», T.M. Cover, B. Gopinath, eds, Springer, 1987, pp. 173-188) Конвей (выдерживая стиль классической мистификации) пишет, что оба известных ему доказательства этой теоремы были утрачены в ходе подготовки текста к печати. О восстановленном в 1997 году доказательстве можно спросить, например, Google, дитя вундеркиндов; при этом обнаружится (www.arxiv.org/abs/math.CO/9808077) множество интересных обсуждений изложенных результатов (в одном ряду с популярными классическими проблемами)…

За многими ссылками, приводимыми нашими сегодняшними авторами, кроются не менее удивительные открытия. Совместима ли индустриализация занимательного с таким вот свободным творчеством высочайшей пробы? Предоставляю желающим поразмышлять еще и над этой задачей. А в заключение хочу вместе с вами порадоваться появлению Константина Кнопа вновь, после длительного перерыва, на наших страницах. Давние читатели «КТ» меня поймут и, не сомневаюсь, разделят мои чувства.