Разделы 
Дополнительно
Задача по математике - 3680
2019-06-15 
Переключатель (рис. а) с двумя входами и двумя выходами может находиться в двух различных состояниях.
На рис. б изображена схема телефонной связи с тремя входами и тремя выходами, которая обладает таким свойством «универсальности»: меняя состояния переключателей, можно осуществить любое
из шести соединений трех входов с тремя различными выходами, т. е.
(Проверьте это. Заметьте, что общее число различных состояний этой схемы равно $2^3 = 8$, поскольку каждый из переключателей может находиться в двух состояниях.)
а) Постройте схему с четырьмя входами и четырьмя выходами, которая была бы «универсальной», т. е. осуществляла бы любое из 24 возможных соединений выходов и входов.
б) Какое минимальное число переключателей нужно для такой схемы?
в) Назовем схему с $n$ входами и $n$ выходами $n$-универсальной, если она осуществляет любое из $n! = 1 \cdot 2 \cdot \cdots \cdot n$ возможных соединений $n$ входов с $n$ различными выходами.
На рис., в изображена схема с восемью входами и восемью выходами, где $A$ и $B$ - 4 - универсальные схемы. Докажите, что она является 8 - универсальной.
Оцените сверху и снизу число переключателей в минимальной $n$-универсальной схеме.
Решение:
Оценим сначала необходимое число переключателей снизу. Поскольку каждый переключатель может находиться в двух состояниях, то схема из $m$ переключателей может находиться в $2^m$ различных состояниях. Если необходимо реализовать все $n!$ различных соединений $n$ входов с $n$ выходами:
где ($i_1, i_2, \cdots, i_n$) - любая перестановка из чисел $1, 2, \cdots, n$ для числа переключателей $m$ должно выполняться неравенство $2^m \geq n!$, т. е. число переключателей в универсальной схеме заведомо не меньше $log_2 (n!)$.
В частности, для $n = 3$ получаем: $2^m \geq 6$, откуда $m = 3$; нетрудно проверить, что схема, указанная на рис. б (в условии), как раз дает пример 3-универсальной схемы. Для $n = 4$ получаем: $2^m \geq 4! = 24$, откуда $m \geq 5$. Действительно, 4-универсальную схему из 5 переключателей можно построить: проверьте, что схема на рис. а при $2^5 = 32$ различных положениях переключателей реализует все 24 возможные перестановки множества $\{1,2,3,4 \}$.
Доказать 8-универсальность схемы, изображенной на рис. в (в условии), перебором практически невозможно; число $8!$ слишком велико. Но нетрудно указать правило, позволяющее любую данную перестановку $\phi$ из 8 элементов $k \rightarrow i_k, k \in {1, 2, \cdots, 8}$, реализовать на схеме. Это правило должно указать, через какой блок - $А$ или $В$ - осуществлять каждую из 8 связей $k \rightarrow \phi (k) = i_k$. При этом должны выполняться такие условия:
если $k - l = 4$ или $i_k - i_l = 4$, то связи $k \rightarrow i_k$ и $l \rightarrow i_l$ должны проходить через разные блоки $A$ и $B$.
Ясно, что эти условия необходимы и достаточны для отсутствия «склеек» (ситуаций, встречающихся и в реальной телефонной сети, когда два входа оказываются соединенными с одним выходом, или наоборот).
Вот нужное нам правило.
Объявляем «соседними» с парой $k \rightarrow \phi (k)$ две пары $j \rightarrow \phi (j)$ и $l \rightarrow \phi (l)$ такие, что $|k - j| = 4$ и $|\phi(k) - \phi(l)| = 4$, тогда все пары разобьются на «хороводы» (циклы) - у каждой будет два соседа, причем эти циклы будут содержать по четному числу пар, В каждом цикле будем попеременно осуществлять связи через блок $А$ и через блок $В$, таким образом «соседи» окажутся соединенными через разные блоки.
Теперь из 4-универсальности блоков $А$ и $В$ следует 8-универсальность всей схемы.
Аналогичным образом можно построить $2^{k+1}$-универсальную схему, исходя из двух $2^k$-универсальных схем и еще $2 \cdot 2^k$ переключателей. Если начать в 5-элементной 4-универсальной схемы (это, конечно, лучше, чем начать с 2-универсального переключателя и получить вместо рис. а 4-универсальную схему рис.б - из 10 элементов!), то при $n = 2^k$ схема будет содержать $2n log_2 n - \frac{11n}{4}$ - переключателей (в частности, при $n = 8$ их 26), что для любого $n \neq 2^k$ дает оценку сверху для числа переключателей в минимальной $k$-универсальной схеме порядка $4n log_2 n$. Лишь слегка изменив конструкцию схемы (рис. в), можно переходить от $k$-универсальной к $2k$ и $(2k + 1)$-универсальной и улучшить оценку сверху до $n log_2 n$. Заметим, что (при больших $n$) $log_2 n! \sim n(log_2 n - log_2 e)$.
Переключатель (рис. а) с двумя входами и двумя выходами может находиться в двух различных состояниях.
На рис. б изображена схема телефонной связи с тремя входами и тремя выходами, которая обладает таким свойством «универсальности»: меняя состояния переключателей, можно осуществить любое
из шести соединений трех входов с тремя различными выходами, т. е.
(Проверьте это. Заметьте, что общее число различных состояний этой схемы равно $2^3 = 8$, поскольку каждый из переключателей может находиться в двух состояниях.)
а) Постройте схему с четырьмя входами и четырьмя выходами, которая была бы «универсальной», т. е. осуществляла бы любое из 24 возможных соединений выходов и входов.
б) Какое минимальное число переключателей нужно для такой схемы?
в) Назовем схему с $n$ входами и $n$ выходами $n$-универсальной, если она осуществляет любое из $n! = 1 \cdot 2 \cdot \cdots \cdot n$ возможных соединений $n$ входов с $n$ различными выходами.
На рис., в изображена схема с восемью входами и восемью выходами, где $A$ и $B$ - 4 - универсальные схемы. Докажите, что она является 8 - универсальной.
Оцените сверху и снизу число переключателей в минимальной $n$-универсальной схеме.
Решение:
Оценим сначала необходимое число переключателей снизу. Поскольку каждый переключатель может находиться в двух состояниях, то схема из $m$ переключателей может находиться в $2^m$ различных состояниях. Если необходимо реализовать все $n!$ различных соединений $n$ входов с $n$ выходами:
где ($i_1, i_2, \cdots, i_n$) - любая перестановка из чисел $1, 2, \cdots, n$ для числа переключателей $m$ должно выполняться неравенство $2^m \geq n!$, т. е. число переключателей в универсальной схеме заведомо не меньше $log_2 (n!)$.
В частности, для $n = 3$ получаем: $2^m \geq 6$, откуда $m = 3$; нетрудно проверить, что схема, указанная на рис. б (в условии), как раз дает пример 3-универсальной схемы. Для $n = 4$ получаем: $2^m \geq 4! = 24$, откуда $m \geq 5$. Действительно, 4-универсальную схему из 5 переключателей можно построить: проверьте, что схема на рис. а при $2^5 = 32$ различных положениях переключателей реализует все 24 возможные перестановки множества $\{1,2,3,4 \}$.
Доказать 8-универсальность схемы, изображенной на рис. в (в условии), перебором практически невозможно; число $8!$ слишком велико. Но нетрудно указать правило, позволяющее любую данную перестановку $\phi$ из 8 элементов $k \rightarrow i_k, k \in {1, 2, \cdots, 8}$, реализовать на схеме. Это правило должно указать, через какой блок - $А$ или $В$ - осуществлять каждую из 8 связей $k \rightarrow \phi (k) = i_k$. При этом должны выполняться такие условия:
если $k - l = 4$ или $i_k - i_l = 4$, то связи $k \rightarrow i_k$ и $l \rightarrow i_l$ должны проходить через разные блоки $A$ и $B$.
Ясно, что эти условия необходимы и достаточны для отсутствия «склеек» (ситуаций, встречающихся и в реальной телефонной сети, когда два входа оказываются соединенными с одним выходом, или наоборот).
Вот нужное нам правило.
Объявляем «соседними» с парой $k \rightarrow \phi (k)$ две пары $j \rightarrow \phi (j)$ и $l \rightarrow \phi (l)$ такие, что $|k - j| = 4$ и $|\phi(k) - \phi(l)| = 4$, тогда все пары разобьются на «хороводы» (циклы) - у каждой будет два соседа, причем эти циклы будут содержать по четному числу пар, В каждом цикле будем попеременно осуществлять связи через блок $А$ и через блок $В$, таким образом «соседи» окажутся соединенными через разные блоки.
Теперь из 4-универсальности блоков $А$ и $В$ следует 8-универсальность всей схемы.
Аналогичным образом можно построить $2^{k+1}$-универсальную схему, исходя из двух $2^k$-универсальных схем и еще $2 \cdot 2^k$ переключателей. Если начать в 5-элементной 4-универсальной схемы (это, конечно, лучше, чем начать с 2-универсального переключателя и получить вместо рис. а 4-универсальную схему рис.б - из 10 элементов!), то при $n = 2^k$ схема будет содержать $2n log_2 n - \frac{11n}{4}$ - переключателей (в частности, при $n = 8$ их 26), что для любого $n \neq 2^k$ дает оценку сверху для числа переключателей в минимальной $k$-универсальной схеме порядка $4n log_2 n$. Лишь слегка изменив конструкцию схемы (рис. в), можно переходить от $k$-универсальной к $2k$ и $(2k + 1)$-универсальной и улучшить оценку сверху до $n log_2 n$. Заметим, что (при больших $n$) $log_2 n! \sim n(log_2 n - log_2 e)$.
