Разделы 
Дополнительно
Задача по математике - 2854
2019-05-06 
Имеютcя два набора знаков «+» и «-» по 1958 знаков в каждом наборе. Доказать, что за некоторое число «шагов», на каждом из которых позволяется менять произвольно выбранные 11 знаков 1-го набора, можно 1-й набор превратить во 2-й. (Наборы считаются одинаковыми, если у них на одинаковых местах стоят одинаковые знаки.)
Решение:
Ясно, что достаточно убедиться в возможности с помощью наших «шагов» изменить любой знак 1-го набора, не меняя ни одного из других знаков, ведь тогда, меняя последовательно все те знаки 1-го набора, которые отличны от стоящих на тех же местах знаков 2-го набора, мы переведем 1-й набор во 2-й. Но изменить одновременно два произвольных знака - скажем, $i$-й знак $\sigma_i$, и $j$-й знак $\sigma_j$-го набора мы, очевидно, можем: для этого достаточно дополнить наши два знака еще какими-то 10 (разумеется, одними и теми же!) знаками $\sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$ 1-го набора до двух групп $\sigma_i, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$ и $\sigma_j, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$, а затем знаки $\sigma_j, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$. Теперь пусть $\sigma_p$ - произвольно выбранный знак 1-го набора; дополним его еще 10 знаками $\sigma_{q_1}, \sigma_{q_2}, \cdots, \sigma_{q_{10}}$ до группы $\sigma_{q_p}, \sigma_{q_1}, \cdots, \sigma_{q_{10}}$ из 11 знаков, а затем сначала поменяем все эти знаки, а потом - с помощью описанного выше приема - знаки $\sigma_{q_3}, \sigma_{q_1}, \cdots$, затем - знаки $\sigma_{q_3}, \sigma_{q_1}, \cdots$, наконец,- знаки $\sigma_{q_3}$ и $\sigma_{q_{10}}$. При этом мы сохраним прежними все знаки 1-го набора, кроме одного лишь знака $\sigma_p$,- «откуда и следует утверждение задачи.
Имеютcя два набора знаков «+» и «-» по 1958 знаков в каждом наборе. Доказать, что за некоторое число «шагов», на каждом из которых позволяется менять произвольно выбранные 11 знаков 1-го набора, можно 1-й набор превратить во 2-й. (Наборы считаются одинаковыми, если у них на одинаковых местах стоят одинаковые знаки.)
Решение:
Ясно, что достаточно убедиться в возможности с помощью наших «шагов» изменить любой знак 1-го набора, не меняя ни одного из других знаков, ведь тогда, меняя последовательно все те знаки 1-го набора, которые отличны от стоящих на тех же местах знаков 2-го набора, мы переведем 1-й набор во 2-й. Но изменить одновременно два произвольных знака - скажем, $i$-й знак $\sigma_i$, и $j$-й знак $\sigma_j$-го набора мы, очевидно, можем: для этого достаточно дополнить наши два знака еще какими-то 10 (разумеется, одними и теми же!) знаками $\sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$ 1-го набора до двух групп $\sigma_i, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$ и $\sigma_j, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$, а затем знаки $\sigma_j, \sigma_{k_1}, \sigma_{k_2}, \cdots \sigma_{k_{10}}$. Теперь пусть $\sigma_p$ - произвольно выбранный знак 1-го набора; дополним его еще 10 знаками $\sigma_{q_1}, \sigma_{q_2}, \cdots, \sigma_{q_{10}}$ до группы $\sigma_{q_p}, \sigma_{q_1}, \cdots, \sigma_{q_{10}}$ из 11 знаков, а затем сначала поменяем все эти знаки, а потом - с помощью описанного выше приема - знаки $\sigma_{q_3}, \sigma_{q_1}, \cdots$, затем - знаки $\sigma_{q_3}, \sigma_{q_1}, \cdots$, наконец,- знаки $\sigma_{q_3}$ и $\sigma_{q_{10}}$. При этом мы сохраним прежними все знаки 1-го набора, кроме одного лишь знака $\sigma_p$,- «откуда и следует утверждение задачи.
