Часть II. РАСПРЕДЕЛЕНИЕ НАГРУЗКИ МЕЖДУ РЕЛЕ

4. Основные положения

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

Эта задача представляет скорее математический интерес, так как связана с аддитивной теорией чисел — предметом, который ранее почти не имел применений. Рассмотрим сначала несколько простых случаев. Предположим, что функция реализована деревом рис. 9. Три переменные

входят соответственно

раз или в терминах переключающих элементов

Переменные могут быть переставлены любым способом без изменения функционирования схемы.

Рис. 19. Разделительное дерево с распределением 1, 3, 3.

Так можно переставить X и в нижней ветви дерева, не изменяя еефункций. Получим распределение (рис. 19)

Дерево с 4 ярусами может быть построено с любым из следующих распределений:

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

к суммам последовательностей 1, 2, 4 или 1,3, 3 в некотором порядке, а последние, как уже было отмечено, суть распределения трехъярусных деревьев. Вообще очевидно, что если можно получить распределения

для -ярусного дерева, то можно получить распределение

для -ярусного дерева.

Заметим теперь, что все приведенные распределения обладают следующим свойством: любое из них может быть получено из первого 1, 2, 4, 8 путем перенесения одной или более единиц от больших чисел к меньшим или после последовательности таких операций, но без перенесения единицы к числу 1. Так, 1, 3, 3, 8 получается путем перенесения единицы от 4 к 2; 1, 4, 5, 5 получается путем перенесения двух единиц от 8 к 2 и одной к 4. Кроме того, каждая последовательность, которая может быть получена из последовательности 1, 2, 4, 8 посредством такого процесса, представляет собой возможное распределение. Эта операция аналогична передаче тепла — тепло может переходить только от теплого тела к холодному — так и единицы, как это показано выше, можно передавать лишь от больших чисел к меньшим.

Эти рассуждения наводят на мысль, что разделительное дерево с ярусами может быть построено с любым распределением нагрузок, полученным при помощи такого плавного переноса единиц из начального распределения

Покажем, что это действительно так.

Введем сначала определение. Запись обозначает любую последовательность чисел которая может быть получена из последовательности посредством следующих операций:

1) перестановка чисел

2) перенос единицы от большего числа к меньшему, не допустимый, однако, для числа .

Так,

но Условия того, что

можно представить более формально. Пусть числа расположены в виде неубывающих последовательностей. Тогда необходимым и достаточным условием справедливости соотношения (6) является выполнение следующих условий:

3. существует одинаковое число единиц среди и среди

Необходимость условий 2 и 3 очевидна. Условие 1 следует из того факта, что если последовательность чисел неубывающая, то перенос возможен только справа налево в последовательности

и при этом сумма может только возрастать. Также легко установить достаточность этих условий. Если для выполняются условия 1, 2 и 3, то числа получатся таким образом: сначала увеличивается до путем последовательного перенесения единиц от чисел ближайших к (соблюдая закон «энтропии» при передаче единиц между ближайшими по величине членами), затем увеличивается до (если необходимо) и т. д. Детали достаточно очевидны.

Аддитивная теория чисел или задача разложения числа в сумму чисел, удовлетворяющих некоторым условиям (в нашем случае это определение обобщено на «последовательности чисел»), выражается в виде следующей леммы.

Лемма. Если то можно разложить последовательность чисел в сумму двух последовательностей

так что

и

Можно предположить, что числа образуют неубывающую последовательность . В случае доказательство

просто. Имеем

и производим перенос в последовательности чтобы получить Любой допустимый перенос в А соответствует допустимому переносу в В или С, так как если

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

Теперь предположим, что Так как последовательность чисел неубывающая, то

Следовательно,

Последнее неравенство очевидно для и легко проверяется для Отсюда следует, что лежат между некоторыми степенями двойки в последовательности Предположим, что

Будем производить перенос между до тех пор, пока одно из них не достигнет значения другое, скажем, аналогичным образом поступим для получения ; другое число при этом пусть равно Тогда в начале нашего разложения имеем последовательности (после выполнения перестановок)

Теперь требуется преобразовать величины справа от в величины Обозначим последовательность

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

так как уже было показано, что это достаточное условие того, что

Этим обстоятельством в первую очередь и воспользуемся. Для т. е. перед членом

и

так как

Следовательно, 23

Далее, для т. е. перед членом

Так как то снова имеем

так что в этом интервале также имеем желаемое неравенство. Наконец, для последнего интервала

и

так как

Тем самым лемма доказана.