Задача
Имеются два набора из чисел 1 и –1, в каждом по 1958 чисел. Доказать, что за некоторое число шагов можно превратить первый набор во второй, если на каждом шагу разрешается одновременно изменить знак у любых 11 чисел первого набора. (Два набора считаются одинаковыми, если у них на одинаковых местах стоят одинаковые числа.)
Решение
Сначала заметим, что у любой пары чисел (ai, aj) (i ≠ j) в наборе можно сменить знак. Для этого возьмём произвольные десять чисел, отличных от ai и aj. Тогда, изменив знаки сначала у десятки, дополненной ai, а потом у той же десятки, дополненной aj, получим, что знаки изменились только у ai и aj.
Теперь покажем, как сменить знак у любого числа ak из набора. Рассмотрим произвольные десять чисел b1, b2, ..., b10, отличных от ai, сначала изменим знаки у b1, b2, ..., b10, ai, а затем у пар (b1, b2), (b3, b4), ..., (b9, b10). Тем самым в итоге знак изменится только у ai.
Сменив таким образом знаки у всех несовпадающих чисел, из любого набора можно получить любой другой набор за конечное число шагов.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь