Задача 32134

Темы:    [ Суммы числовых последовательностей и ряды разностей ] [ Примеры и контрпримеры. Конструкции ] [ Арифметика остатков (прочее) ]

Сложность: 4 Классы: 9,10,11

Условие

Автор: Bong-Gyun Koh

Каждое ли целое число можно записать как сумму кубов нескольких целых чисел, среди которых нет одинаковых?

Решение

Заметим, что  (n + 7)³ – (n + 6)³ – (n + 5)³ + (n + 4)³ – (n + 3)³ + (n + 2)³ + (n + 1)³ – n³ = 48.  С другой стороны, число  (48k + 1)³  при любом k даёт при делении на 48 остаток 1. Складывая такие кубы, можно получить сумму с любым наперёд заданным остатком от деления на 48, а потом, прибавляя или вычитая нужное количество раз комбинации, равные 48 и состоящие из разных чисел, получить любое число с таким остатком.

Ответ

Каждое.

Замечания

1. Идеология. Положим  Δ^kf(x) = f(x + k) – f(x).  Применение такой операции понижает степень многочлена на единицу (ср. с задачей 61433). Использованное в решении выражение равно  Δ₁Δ₂Δ₄f(n),  где  f(n) = n³,  поэтому оно и равно константе.

2. 7 баллов

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

олимпиада
Название	Турнир городов
Турнир
Номер	35
Дата	2013/2014
вариант
Вариант	осенний тур, сложный вариант, 10-11 класс
задача
Номер	4