Дана последовательность натуральных чисел a1, a2, . . . , an, . . . , в которой a1 не делится на 5 и для всякого n имеет место равенство: an+1 = an + bn, , где bn - последняя цифра числа an. Например, a1 = 11, далее, 11 + 1 = 12, 14, 18, 26 … Докажите, что последовательность содержит бесконечно много степеней двойки.

задан 28 Авг '18 22:53

10|600 символов нужно символов осталось
4

Последняя цифра числа a(n+1) есть остаток от деления на 10, то есть 2a(n) mod 10, где mod рассматривается в "программистском" смысле. Это значит, что если последняя цифра числа a(1) равна 1, то далее последовательно будут прибавляться числа 1, 2, 4, 8, 6, 2, ... с периодом. Для других цифр на конце a(1), эти значения будут равны 2, 4, 8, 6, 2, ... для двойки, 3, 6, 2, 4, 8, 6, ... для тройки, и так далее. Для цифр 7 и 9 получится соответственно 7, 4, 8, 6, 2, 4, ... и 9, 8, 6, 2, 4, 8, ... . Во всех случаях окажется, что, начиная с некоторого числа, последовательность a(n) будет содержать арифметическую прогрессию с разностью 2+4+6+8=20. Для примера из условия это будет 12, 32, 52, 72, ... .

Цифра 2 встречается в периоде, и в какой-то момент к числу будет прибавляться 2. Это значит, что одно из двух чисел вида a(n), a(n+1) окажется кратно 4. Осталось заметить, что если некоторый член последовательности кратен 4, то имеется подпоследовательность вида 4m, 4m+20, 4n+40, ... , в которой степеней двойки будет бесконечно много. Действительно, это то же самое, что случай m, m+5, m+10 , ... , где m, согласно условию, не равно ни 0, ни 5 (среди цифр на конце 0 или 5 никогда не появляются, так как их не было изначально, а все последующие цифры мы знаем). Среди степеней двойки при делении на 5 остатки имеют вид 1, 2, 4, 3, 1, ... , то есть среди них бесконечно много раз встречается тот же остаток, что и у m. Значит, эти степени двойки войдут в прогрессию. В примере с числом 32=2^5 туда войдут 2^9=512, 2^{13}, ... и так далее.

ссылка

отвечен 28 Авг '18 23:32

@falcao, спасибо за решение, задача из Российской олимпиады 25-летней давности, идея решения вроде и напрашивается... Мне всегда хочется излагать решения предельно коротко и на школьном уровне. Для данной задачи я пытался рассуждать примерно так.

Любая последовательность a(n) содержит а.п. 12 + 20k, либо а.п.п. 4 + 20k, 8 + 20k, 16 + 20k, иначе говоря, ВСЕ числа, имеющие остаток 12 при делении на 20, и т.д. Степени двойки имеют при делении на 20 остатки 4,8,16 и 12 в периоде.

Отсюда следует, что в последовательности с a(1) = 11 будут содержаться степени двойки 32, 512, 8192 = 2^13, и т.д.

(29 Авг '18 0:44) kipot_l

Наиболее "густо" степени двойки будут встречаться в последовательности a(n), где a(1) = 2 : 2, 4, 8, 16, ...64, ...128, ...256, ... Вроде так...

(29 Авг '18 0:49) kipot_l
1

@kipot_l: у меня по содержанию сказано в точности то же самое.

Что касается способа изложения, но я писал сразу на "чистовик", не особо заботясь о "шлифовке". Мне было интересно понять суть, а потом её изложить без пробелов типа "очевидно, что". Конечно, при второй "проходке" можно сделать доказательство более компактным. Сама цель -- "благая", но я её перед собой не ставил.

(29 Авг '18 0:53) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×525
×149
×1

задан
28 Авг '18 22:53

показан
541 раз

обновлен
29 Авг '18 0:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

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

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru