Задача 78150

Темы:    [ Теория алгоритмов (прочее) ] [ Четность и нечетность ]

Сложность: 3+ Классы: 8,9

Условие

Имеются два набора из чисел 1 и –1, в каждом по 1958 чисел. Доказать, что за некоторое число шагов можно превратить первый набор во второй, если на каждом шагу разрешается одновременно изменить знак у любых 11 чисел первого набора. (Два набора считаются одинаковыми, если у них на одинаковых местах стоят одинаковые числа.)

Решение

  Сначала заметим, что у любой пары чисел  (a_i, a_j)  (i ≠ j)  в наборе можно сменить знак. Для этого возьмём произвольные десять чисел, отличных от a_i и a_j. Тогда, изменив знаки сначала у десятки, дополненной a_i, а потом у той же десятки, дополненной a_j, получим, что знаки изменились только у a_i и a_j.
 Теперь покажем, как сменить знак у любого числа a_k из набора. Рассмотрим произвольные десять чисел b₁, b₂, ..., b₁₀, отличных от a_i, сначала изменим знаки у b₁, b₂, ..., b₁₀, a_i, а затем у пар  (b₁, b₂),  (b₃, b₄),  ...,  (b₉, b₁₀).  Тем самым в итоге знак изменится только у a_i.
  Сменив таким образом знаки у всех несовпадающих чисел, из любого набора можно получить любой другой набор за конечное число шагов.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	21
Год	1958
вариант
Класс	7
Тур	2
задача
Номер	2