Для каждого натурального n обозначим через P(n) число разбиений n в сумму натуральных слагаемых (разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми; например,  P(4) = 5,  потому что  4 = 4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1  – пять способов).
  а) Количество различных чисел в данном разбиении назовем его разбросом (например, разбиение  4 = 1 + 1 + 2  имеет разброс 2, потому что в этом разбиении два различных числа). Докажите, что сумма Q(n) разбросов всех разбиений числа n равна   1 + P(1) + P(2) + ... + P(n–1).
  б) Докажите, что  

   Решение

Темы:    [ Десятичная система счисления ] [ Алгебраические неравенства (прочее) ] [ Арифметика остатков (прочее) ]

Сложность: 3+ Классы: 10,11

Прислать комментарий

Условие

Доказать, что в десятичной записи чисел  2ⁿ + 1974ⁿ и 1974ⁿ  содержится одинаковое количество цифр.

Решение

Предположим, что  1974ⁿ < 10^k ≤ 2ⁿ + 1974ⁿ.  Тогда  k ≥ 3n,  поскольку  1974ⁿ > 10³ⁿ.  После деления на 2ⁿ приходим к неравенству
987ⁿ < 2^k−n·5^k ≤ 987ⁿ + 1.  Число  2^k–n·5^k  целое, поэтому  2^k–n·5^k = 987ⁿ + 1.  Если  n ≥ 2,  то  k − n ≥ 2n > 3,  поэтому  2^k–n·5^k  делится на 8. С другой стороны, 987 при делении на 8 даёт остаток 3, поэтому  987ⁿ + 1  при делении на 8 даёт остаток 4 или 2. Противоречие.

Источники и прецеденты использования