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

Предыдущий
вопрос Следующий
вопрос

Давайте докажем данное утверждение по индукции.

База индукции: при n = 1 у нас есть числа 1, 2, 3. За один ход мы можем заменить числа 1 и 2 разностью -1, и останется число 3, которое является четным.

Предположение индукции: предположим, что после (4k-2)-го хода останется одно четное число из чисел 1, 2, 3,...,4k-1.

Индукционный переход: докажем, что после (4(k+1)-2)-го хода останется одно четное число из чисел 1, 2, 3,...,4(k+1)-1.

Рассмотрим числа 1, 2, 3,...,4(k+1)-1. Заметим, что cуществует число i такое, что 1 ≤ i ≤ 4k-1, и число 4(k+1)-i. Тогда мы можем заменить числа i и 4(k+1)-i разностью 4, которая является четным числом. После такого хода останется числа 4k, 4k+1, 4k+2, 4k+3, 4(k+1)-1. При этом остальные числа не изменились, и среди них содержится только одно четное число - 4k.

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