Слыхали детскую байку о том, что у каждого из нас есть таинственный ДВОЙНИК? А ещё, говорят, есть параллельная вселенная, в которой всё точно также, как у нас, но только по другому и совсем наоборот? Давайте сегодня прольём свет на эти удивительные слухи!
Недавно я уже делился тем, как объяснял смысл наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) для двух чисел, через кубики или слова. Для болтовни на прогулке это объяснение вполне подходит, но оно не даёт прямых подсказок ни о том, как эффективно вычислять эти величины алгоритмом Евклида, ни о том, какую пользу могут принести эти две числовые операции.
Алгоритм Евклида достоин отдельного разговора, а вот пользу этих величин легко продемонстрировать на двух задачках об упаковке коробок в ящики. Вот они:
Задача 1. Какого размера должен быть квадратный ящик, чтобы в него можно было плотно уместить одинаковые прямоугольные коробки со сторонами a и b?
Ответ: сторона квадрата x должна быть кратной как числу a, так и числу b. Наименьшее такое значение — это НОК(a, b).
Задача 2. Какого размера должны быть одинаковые квадратные коробки, которые можно было бы плотно разместить в ящике со сторонами a и b?
Ответ: искомая сторона квадрата x должна делить на цело и a и b. Наибольшее такое значение — это НОД(а, b).
От достаточно невнятных "квадратных ящиков" можно потом перейти к более реалистичным кубическим, а коробки сделать параллелепипедами со сторонами a, b, и c. Тогда можно выяснить, что операции НОД и НОК ассоциативны и могут быть применены к трём и более аргументам.
Эти две немудрящие задачки мне очень и очень нравятся, во-первых, лаконичностью, а во-вторых, своей внутренней симметрией. Смотрите: в первой задаче мы для прямоугольных коробок отыскивали наименьший квадратный ящик, а во второй задаче — для прямоугольного ящика отыскивали наибольшие квадратные коробки.
Эти задачи превращаются друг в друга, если поменять в них всё, что можно на противоположное: квадратное ⟷ прямоугольное, наибольшее ⟷ наименьшее, искомое ⟷ известное, НОД ⟷ НОК.
В таких случаях говорят, что операции НОД(а, b) и НОК(a, b) двойственны друг другу. Двойственность, как своеобразная разновидность симметрии, встречается в самых разных разделах математики, чрезвычайно их собой украшая. Приведу несколько примеров.
Булева алгебра и логика. Операции И и ИЛИ двойственны и любое верное утверждение (теорема, формула) останется верным при одновременном преобразовании: И ⟷ ИЛИ, ИСТИНА ⟷ ЛОЖЬ, A ⟷ НЕ A для всех переменных A. Например, эти два поисковых запроса одинаковы:
(НЕ "кот") И (НЕ "собака") = НЕ ("кот" ИЛИ "собака")
Двойственными также являются кванторы общности и существования:
НЕ (ВСЕ числа простые) = СУЩЕСТВУЮТ числа (НЕ простые).
Двойственны друг другу и задачи на распределение ресурсов. Одна задача переходит в другую, эквивалентную, при одновременной замене последовательно ⟷ параллельно, производительность ⟷ темп, мгновенно ⟷ никогда. В школе мы встречаемся с такими задачами, возясь с землекопами, роющими канавы, изучая электрические цепи или соединения пружин.
Например, при последовательном соединении нагрузок складываются сопротивления (R = R₁ + R₂), при параллельном соединении складываются проводимости — величины обратные сопротивлениям (1/R = 1/R₁ + 1/R₂). Соединяя две пружинки параллельно, мы складываем их жёсткости, а если последовательно, то величины, обратные жёсткости, и т. д. Подробнее я рассказывал о таких задачах в этой заметке.
Точки и прямые в проективной геометрии двойственны относительно отношений пересекаться и соединять. Это значит, что при одновременной замене в любой теореме: пересечение ⟷ соединение, точка ⟷ прямая, мы получим новую верную теорему.
Например, утверждения: две точки можно соединить одной прямой двойственно утверждению: две прямые пересекаются в одной точке.
Удивительно, но в проективной геометрии дуальность универсально распространяется на все теоремы! Скажем, теорема Менелая двойственна теореме Чевы, так что доказывать достаточно только одну из них, вторая верна автоматически. Внимательно посмотрите на построения теоремы Менелая и теоремы Чевы, и убедитесь в их двойственности:
В стереометрии и теории графов тоже есть понятие двойственности, состоящее в замене вершины ⟷ грани, соединять ⟷ быть границей. Скажем куб двойственен октаэдру, а икосаэдр — додекаэдру.
В теории графов триангуляция Делоне двойственна диаграмме Вороного.
Наконец, в теории категорий любая теорема, коммутационная диаграмма или утверждение, справедливые в некоторой категории, остаются справедливыми в дуальной категории в которой всё стрелки (морфизмы) заменены на противоположные.
Например, понятия произведения и суммы для объектов в некоторой категории двойственны и определяются такими коммутационными диаграммами:
На практике мы можем встретить эти понятия в программировании, при образовании типов данных. Произведению типов соответствуют структуры или кортежи, а сумме типов размеченное объединение или перечисление. Наличие в теории двойственности позволяет "сократить работу вдвое", порождая каждой теореме верную пару.
* * *
Давайте вернёмся к тому, с чего начали и посмотрим в чём же состоит и как проявляется двойственность НОД и НОК для чисел. Любое тождество остаётся верным при одновременной замене НОД ⟷ НОК, делит ⟷ делится, максимум ⟷ минимум.
Посмотрим на некоторые общие формулы, в которых проявляется эта двойственность:
Наконец, существует алгоритм нахождения НОК(a, b), двойственный алгоритму Евклида для нахождения НОД(a, b):
Схемы работы этих алгоритмов можно показать геометрически, при этом мы получим иллюстрацию упаковки квадратных коробок в прямоугольный ящик с помощью НОД и прямоугольных коробок в квадратный ящик с помощью НОК.
Так же как непохожи друг на друга чертежи к теоремам Менелая и Чевы, так же и алгоритмы вычисления НОД и НОК имеют отличия. Двойственный, не значит эквивалентный, противоположный или обратный. Этот принцип относится не к объектам, а теориям, строящимся на этих объектах, то есть, к связанными с ними утверждениями или отношениями.