Коллектив авторов - Теории всего на свете

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

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

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

Чарлз Сейфе

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

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

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

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

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

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

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

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