На дощечке выписаны числа 1,2,...,10000. На каждом шаге сразу стираются все

а) На дощечке выписаны числа 1, 2, 4, 8, 16, 32, 64, 128. Разрешается стереть любые два числа и заместо их выписать их разность неотрицательное число. После семи таких операций на доске будет только одно число. Может ли оно приравниваться 97?

б) На дощечке выписаны числа 1, 21, 2, 2, ..., 210. Разрешается стереть любые два числа и заместо их выписать их разность неотрицательное число. После нескольких таких операций на дощечке будет только одно число. Чему оно может быть одинаково?

Решение

 a) Получить 97 можно, к примеру, так. Поочередно вычитая из 16 числа 8, 4, 2, 1, получим 1. На дощечке остались числа 1, 32, 64, 128. Далее: БикЮ 64 32 = 32,  32 1 = 31,  128 31 = 97.

 б) Докажем, что если на дощечке выписаны числа 1, 2, ..., 2n, то после n операций, описанных в условии, может получиться хоть какое нечётное число от 1 до  2n 1.  Явно, числа, великие 2n, на дощечке не возникают. Просто созидать также, что на дощечке всегда присутствует ровно одно нечётное число. Означает, и заключительнее оставшееся на доске число нечётно. Утверждение о том, что все обозначенные числа выстроить можно, докажем индукцией по n.

 База. Имея числа 1 и 2, можно получить только число 1.

 Шаг индукции. Пусть на дощечке выписаны числа 1, 2, ..., 2n+1. Любое нечётное число, наименьшее 2n, можно получить за  n + 1  операцию (на первом шаге сотрём 2n+1 и 2n и напишем 2n, дальше по предположению индукции). Нечётные числа от  2n + 1  до  2n+ 1 1  можно записать в виде  2n+1 a,  где число a можно получить из набора 1, 2, ..., 2n. На заключительном шаге из  2n+1 вычитаем a.

Ответ

а) Может;  б) хоть какому нечётному числу от 1 до  210 1.

Замечания

Баллы: 2 + 3