Question

Даны натуральные числа 1, 2, 3,...,4n-1. За один ход разрешается заменить два любых числа их разностью. Доказать, что после (4n-2)-го хода останется одно четное число​

Answer 1

1) После каждого хода кол-во чисел уменьшается на одно. Тогда после 4n-2ого хода из 4n-1 числа останется 4n-1-(4n-2)=1 число

2) Заметим, что четность разности двух чисел совпадает с их суммой. И правда: ч+ч=ч, ч-ч=ч; н+ч=н, н-ч=н; ч+н=н, ч-н=н.

Значит после каждого хода четность суммы чисел не изменится.

Сумма всех начальных чисел равна (1+4n-1)/2*(4n-1)=2n*(4n-1) - четное число, а значит и последнее оставшееся число будет четным.

Ч.т.д.

Answer 2

Давайте рассмотрим, что происходит при каждом ходе.

После первого хода у нас останется числа 1, 2, 3, ..., 4n-2, 1. В этой последовательности четных и нечетных чисел по-прежнему одинаковое количество.

После второго хода мы можем заменить любые два числа, одно из которых четное, а другое нечетное. Разность между четным и нечетным числом всегда будет нечетной, поэтому останется нечетное число. Таким образом, после второго хода у нас останется нечетное число четных чисел и (4n-3) нечетных.

На каждом последующем шаге мы также будем оставлять нечетное число четных и нечетных чисел. Поэтому после (4n-2)-го хода у нас останется одно четное число и (4n-2)-1 = 4n-3 нечетных чисел.

Таким образом, мы доказали, что после (4n-2)-го хода останется одно четное число.