ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ Р. В. Фрейвалд

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

Страница переведена на новый сайт https://myeducation.su/ :

страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)

На V Всесоюзной математической олимпиаде*) была предложена
следующая задача:
Переключатель (рис. 1) с двумя входами и двумя выходами может
находиться в двух различных состояниях.
На рисунке 2 изображена схема телефонной связи с тремя входами
и тремя выходами, кото-
рая обладает таким свой-
ством «универсальности»:

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

(Проверьте это. Заметьте, что общее число различных состояний этой
схемы равно 23—8, поскольку каждый из переключателей может нахо-
диться в двух состояниях.)
а) Постройте схему с четырьмя уходами и четырьмя выходами, ко-
торая была бы «универсальной», то есть осуществляла бы любое из 24
возможных соединений входов и выходов.
б) Какое минимальное число переключателей нужно для такой схемы?
в) Назовем схему с п входами и п выходами «-универсальной, если
*) Подробнее о пятой олимпиаде см. «Квант» Л» 11 за 1971 г., стр. 35—42.

16 ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ.

она осуществляет любое из п! = 1-2-…я возможных соединении я входов с
п различными выходами. На рисунке 3 изображена схема с восьмью вхо-
дами и восьмью выходами, где А и В —-универсальные схемы. Дока-
жите, что она является 8-универсальной.
Оцените сверху и снизу число переключателей в минимальной л-уни-
нереальной схеме.
Рассмотрим следующую схему (рис. 4), 4-универсальность этой схемы
можно легко проверить, подбирая для всех 4! =24 требуемых соединений
нужные состояния переключателей. Заметим, что практически удобнее
поступать наоборот: рассмотреть все 25 =32 различные состояния схемы
и выписать, какое соединение осуществляется каждым состоянием схемы
(попробуйте проделать это!).
Если некоторая схема состоит из 4 или меньшего числа переключа-
телей, то эта схема может иметь только 24—16 различных состояний.
Поэтому такая схема не может осуществлять 24 различных соединения и,
следовательно, не может быть 4-универсалыюй. Итак, мы решили задачи
а) и б).
Последнее рассуждение можно обобщить. Пусть п-универсальная
схема состоит из т переключателей. Эта схема имеет 2т различных сос-
тояний и должна осуществлять At! различных соединений. Поэтому 2т^п\
п
(R V 2
-Z-) , ТО /Л>
> Iog2 t (-5-) » ) = -^—(loggAi— 1). Пользуясь более точным неравенством
л!> (‘ • ¦)» (см. задачу 3 в статье М. И. Башмакова «О постулате
Бертрана» — «Квант» № 5, 1971, стр.6), полученную оценку можно улуч-
шить примерно в два раза: т~>п(\о%г (я+1)—logfC).
Докажем теперь 8-универсальностьсхемы, изображенной на рисунке 3.
Вообще говоря, и это доказательство можно вести перебором состояний
схемы, но здесь такой перебор уже практически неосуществим (по крайней
мере, за время, отведенное на Олимпиаду). Поэтому нужно рассуждать
более рационально.
Пусть требуется осуществить соединение
\ 2 3 4 5 6 7 8
4 4 4 4 4 4 4 4
‘i h h U h h h h
Будем говорить, что это соединение состоит из 8 связей: 1-я связь соеди-
няет 1-й входе /х-м выходом,
2-я связь соединяет 2-й. вход с j |
/2-м выходом, и так далее. лХ,
Заметим, что любую связь LJI
(например, 3-го входа с 5-ым
выходом) в нашей схеме можно
осуществить в точности двумя
способами — через блок /1 и
через блок В (рис. 5 и 6). Каж-
дый из этих блоков имеет 4 вхо-
да и выхода. Для осуществле-
ния нашего соединения мы
должны все 8 связей распре-
рис. 4. Рис. 5.

17 ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ.

делить по блокам А и В так,
чтобы 4 связи проходили через
Л и 4 — через В. При этом мы
должны следить, чтобы две раз-
ные связи не проходили через
один и тот же вход или один
и тот же выход блоков An В.
Рассмотрим первый и пя-
тый вход нашей схемы. Каж-
дый из них может быть под-
ключен либо к первому входу
блока А либо к первому входу
блока В. Следовательно, один
из этих входов должен быть подключен к блоку Л, другой — к блоку В,
иначе две связи будут подключены к одному и тому же входу некоторого
блока. К разным блокам должны быть подключены также следующие
пары входов: 2-й и 6-й, 3-й и 7-й. 4-й и 8-й. Легко видеть, что такое
условие распределения связей по блокам не только необходимо, но и доста-
точно для того, чтобы в схеме разные связи не проходили через один и
тот же вход блоков А и В. Чтобы сформулировать такое же условие
для выходов блоков А и В, полезно обратить внимание на симметрич-
ное расположение входов и выходов схемы. Заключаем, что следующие
пары выходов схемы должны быть подключены к разным блокам: 1-й и
5-й, 2-й и 6-й, 3-й и 7-й, 4-й и 8-й.
Изобразим на рисунке эти отношения между различными связями
одного и того же соединения. Каждую отдельную связь изобразим прямоу-
гольником, внутри которого записано, какой вход с каким выходом данная
связь соединяет. Если две связи обязательно должны проходить через
разные блоки, то соответствующие им прямоугольники соединим линией.
При этом проведем линию красного цвета, если на 4 отличаются входы, и
синего — если на 4 отличаются выходы.
Например, соединение

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

18 ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ.

щую следующему прямо-
угольнику, через А и так да-
-лес, пока «кольцо» замкнет-
ся. Связи, соответствующие
первому и последнему пря-
моугольникам, при этом бу-
дут осуществляться через
разные блоки, так как число
прямоугольников в «кольце»
четно. 8-универсальность схе-
мы (см. рис 3) доказана.
Заметим только, что распре-
деление связей по блокам
всегда можно провести так,
чтобы один из переключа-
телей (например, левый ниж-
ний) находился в каком-то
заранее заданном состоянии.
(Другими словами, этот пе-
реключатель можно из схемы
удалить, а схема не переста-
нет быть универсальной.)
Тогда в «кольце», содержа-
щем связь, проходящую че-
рез выделенный переключа-
тель, распределение связей
по блокам нужно начать
именно с этой связи.
Для оценки сверху числа
переключателей в минималь-
ной «-универсальной схеме
будем строить «-универсаль-
ные схемы с возможно мень-
шим числом переключателей.
Приведенное выше доказа-
тельство 8-универсальности
схемы (см. рис. 3) легко обоб-
щить на случай любого чет-
ного числа входов. Этот спо-
соб дает возможность, имея
8-универсальную схему, стро-
ить довольно экономную 16-
универсальную схему, потом 32-универсальную схему и так далее. Мож-
но подсчитать, что если^л=2А и в качестве блоков 4-универсальной схе-
мы использовать схему (рис. 4), то такая схема имеет 26-2*—LL.2* =
— 2n-log2n ?~-л переключателей. Если « не равно целой степени
двойки, то можно использовать схему, являющуюся универсальной для
большего числа входов, равного полной степени двойки. Так как бли-
жайшая сверху полная степень двойки превосходит данное число « не
более чем в два раза, получается, что для любого « существует «-универ-
сальная схема, содержащая не более 4 «-log2 л переключателей.
(Окончание см. на стр. 27.)

19 ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ.

 

ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ