Рассмотрим всевозможные $%99$%-значные натуральные числа, в десятичной записи которых встречаются только цифры $%4$% и $%5$%. Сколько среди них делятся на $%3$% нацело?

задан 9 Фев 20:34

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

Пусть k раз встречается цифра 4. Тогда сумма цифр 4k+5(99-k) делится на 3, то есть k кратно 3. Обозначим через a(n) число n-значных чисел из цифр 4 и 5 с суммой цифр кратной 3. Легко видеть, что a(1)=0, a(2)=2, a(3)=2. Пусть n > 3. Если у n-значного числа первая цифра 4, то далее идёт (n-1)-значное число с суммой цифр =2(mod 3), а если 5, то =1(mod 3). Получается формула a(n)=2^{n-1}-a(n-1), так как количество n-значных с суммой кратной 3 равно количеству (n-1)-значных с суммой не кратной 3. Последовательность имеет вид 0, 2, 2, 6, 10, 22, 42, ... . Найдём закономерность.

Из общих соображений ясно, что a(n) примерно равно 2^n/3, так как около трети чисел подходят. Утроим члены последовательности: 0, 6, 6, 18, 30, 66, 126, ... . Видно, что это 2^1-2, 2^2+2, 2^3-2, 2^4+2, 2^5-2, 2^6+2, 2^7-2, ... , то есть 3a(n)=2^n+2(-1)^n. Это гипотеза, которая доказывается индукцией по n при помощи рекуррентного равенства.

Итого a(99)=(2^99-2)/3.

ссылка

отвечен 9 Фев 21:43

@falcao: Извините, пожалуйста, я не очень понял почему у Вас написано: "Если у n-значного числа первая цифра 4, то далее идёт (n-1)-значное число с суммой цифр =2(mod 3), а если 5, то =1(mod 3). Разве не наоборот, т.к. при делении 4 на будет остаток 1, а при делении 5 на 3 будет остаток 2. Или имеется в виду, что первую цифру (4) мы не учитываем и тогда дальше идёт 5 и поэтому остаток 2 и тоже если первая цифра 5. Или я неправ и ничего не понял? Заранее благодарен. С уважением.

(10 Фев 0:47) serg55
1

@serg55: я рассматриваю n-значное число кратное 3. Оно начинается с 4 или 5. Если с 4, то у оставшегося числа (после вычёркивания первой цифры) остаток от деления на 3 равен 2 -- чтобы в сумме с 4 получилось кратное . Аналогично для первой цифры 5.

(10 Фев 1:05) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,505

задан
9 Фев 20:34

показан
62 раза

обновлен
10 Фев 1:05

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

по почте:

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

по RSS:

Ответы

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

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