Назад
Задача

Имеются два набора из чисел 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.

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

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет