Еще кое-что о принципе голубей и ящиков

Чарлз Сейфе

Профессор журналистики Нью-Йоркского университета, бывший автор журнала Science; автор книги Proofiness: The Dark Arts of Mathematical Deception («Непроницаемость: темное искусство математического обмана»)

Порой даже простой подсчет может поведать нечто значительное. Однажды, еще в конце 1990?х, будучи корреспондентом журнала New Scientist, я получил рекламное электронное письмо, воспевавшее какую-то необычайную компьютерную программу. В письме провозглашалось, что эта программа архивирования данных произведет настоящую революцию в цифровом мире, ибо она столь эффективна, что может сжать любой файл на 95 % или больше, не потеряв при этом ни единого бита данных. Может быть, мой журнал не упустит шанс поведать миру об этом софте, который позволит хранить на жестком диске в 20 раз больше информации, чем раньше?

Нет, мой журнал не станет об этом рассказывать, решил я.

Подобный алгоритм сжатия информации не может существовать. Это алгоритмический аналог вечного двигателя. Этот софт – жульничество. Причина – принцип голубей и ящиков.

Принцип голубей и ящиков – по сути, простое правило счета. Если у вас имеется n голубей и вам удалось запихнуть их менее чем в n ящиков, это означает, что по меньшей мере один ящик будет содержать в себе более одной птицы. Очевидно до банальности, не правда ли? Однако этот принцип – весьма полезный и мощный инструмент. К примеру, представим себе, что компрессионный софт, о котором шла речь, соответствует рекламному описанию и сжимает каждый файл в 20 раз без потери информации. Таким образом, каждый файл размером 2000 бит будет стиснут в какие-нибудь 100 бит, а при обращении алгоритма этот стобитный файл примет первоначальную форму, ничуть при этом не пострадав.

Сжимая файлы, вы волей-неволей натыкаетесь на принцип голубей и ящиков. Ведь общее количество 2000-битных голубей намного, намного больше (их 2²⁰⁰⁰, если быть точным), чем 100-битных ящиков (их 2¹⁰⁰). Если алгоритм позволяет полностью втиснуть первое во второе, это означает, что по меньшей мере один ящик должен содержать более одного голубя. Возьмем этот ящик (этот 100-битный файл) и попробуем обратить алгоритм сжатия, расширив этот файл до его исходной 2000-битной формы. Это не удастся сделать! Поскольку существует множество 2000-битных файлов, каждый из которых окажется сжатым в один и тот же 100-битный файл, алгоритм не сумеет определить, какой из этих 2000-битный файлов – истинный оригинал, так что компрессию будет невозможно обратить.

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

Подобного рода «пересчет» открывает перед исследователями обширные горизонты. Немецкий математик Георг Кантор использовал разновидность обратного принципа голубей и ящиков, дабы показать, что действительные числа невозможно упаковать в ящики, предназначенные для целых чисел (по одному ящику на каждое число), хотя целых чисел бесконечно много. Отсюда следовал трудновообразимый вывод: существуют различные уровни бесконечности. Бесконечность целых чисел ничтожна по сравнению с бесконечностью действительных чисел, которая, в свою очередь, смехотворно мала по сравнению с еще одной бесконечностью, а та – по сравнению с еще одной бесконечностью… бесконечное число бесконечностей, которые останутся неисследованными, пока мы не научимся как-то их считать.

Применение принципа голубей и ящиков к исследованию глубин космоса приводит к еще более странным умозаключениям. Один из физических принципов, так называемый принцип голографической ограниченности, гласит: для каждого конечного объема пространства существует лишь конечное число возможных конфигураций массы и энергии. Если, как склонны полагать космологи, Вселенная бесконечна, то в ней существует бесконечное количество объемов пространства размером с видимую вселенную – гигантских космических пузырей, содержащих материю и энергию. Если пространство более или менее гомогенно (однородно), то в пузыре, где мы с вами обитаем, нет ничего такого уж особенного и уникального. Из всех этих допущений, взятых в совокупности, следует ошеломляющий вывод. Бесконечность количества таких пузырей размером со вселенную при конечном числе конфигураций вещества и энергии в каждом означает, что существует даже не одна точная копия нашей Вселенной (и нашей Земли). Согласно космической версии принципа голубей и ящиков, существует бесконечное количество копий каждой (строго выражаясь, «почти каждой»: для этого выражения имеется точное математическое определение) из возможных вселенных. Мало того, что существует бесконечное количество ваших собственных копий на этом бесконечном количестве планет Земля, есть и бесконечное количество вариаций на ту же тему: вы с хватательным хвостом, вы с несколькими головами, вы как профессиональный жонглер хищными кроликоподобными зверьками, получающий драгоценности для украшения одежды в уплату за демонстрацию своего искусства. Как видите, даже простой счет «раз, два, три…» способен привести к причудливым и неожиданным результатам.