Наименьшая сумма

[wpoms.]

Рассмотрим все числа вида `3n^2 + n + 1`, где `n` натуральное число. (a) Найдите наименьшее значение суммы цифр подобного числа в десятичной системе счисления. (b) Существует ли такое число, сумма цифр которого в десятичной системе счисления равна 1999?

---

Начинаем публикацию задач аргентинской математической олимпиады (ОМА), финал которой состоялся в ноябре 2012 года.
Благодарим Диану Шипилову за помощь при переводе условий ОМА.

Приглашаем всех желающих принять участие в решении и обсуждении предлагаемых задач

@темы: Задачи на экстремум, Теория чисел

Comments

[Adjirranirr]

Пусть `S: NN -> NN` — сумма цифр числа, а `f(n) = 3n^2+n+1 : NN -> NN`.

Заметим, что `AA n: S(n * 10^k + p) = S(n) + p`, где `k, 0 <= p <= 10^k - 1` — натуральные числа.

(a): Так как числа `n` и `3n^2` одной четности, то для всех `n`, `f(n)` — нечетное число. Значит, `S(f(n)) = 1 <=> f(n) = 1`. Но тогда `3n^2 + n = 0`, что невозможно, так как `n >= 1`.
Теперь заметим, что числа `n` и `3n + 1` взаимно просты. В самом деле, `AA p >= 2:\ n\ \text{mod}\ p = 0 => 3n\ \text{mod}\ p = 0 => 3n + 1\ \text{mod}\ p = 1`.
Предположим, что `S(f(n)) = 2`. Так как `S(n)` не может быть меньше первой и последней цифры числа, а так же, в силу нечетности `f(n)`, последняя цифра не менее `1`, то первая цифра не превосходит `1` и `f(n)` имеет вид `10^k + 1`, или `3n^2 + n = 10^k => n * (3n + 1) = 2^k * 5^k`. В силу взаимной простоты `n` и `3n + 1`, а так же неравенства `3n + 1 > n`, имеем `3n + 1 = 5^k,\ n = 2^k`, или `5^k - 3*2^k = 1`. Функция `g(x) = 5^x - 3*2^x` возрастает при `x > (ln(3)-ln(ln(5))+ln(ln(2)))/(ln(5)-ln(2)) ~~0.279621`, причем `g(0) = -2,\ g(1) = -1,\ g(2) = 13,\ g(k) > g(2) > 1` для `k > 2`, а, значит, ни при каком натуральном `k` равенство `5^k - 3*2^k = 1` не имеет места, и `AA n: S(f(n)) != 2`.
Таким образом, `S(f(n)) >= 3`. При этом, т. к. `S(f(8)) = S(201) = 3`, `min_{n \in NN} S(f(n)) = 3`.

(b): Очевидно, что `S(10^k - 1) = 9k` при целом неотрицательном `k`. С другой стороны, `S(3*(10^k - 1)^2) = S(3*10^{2k} - 6*10^k + 3) = S(10^k*(3*10^k - 6) + 3) = S(3 * 10^k - 6) + 3 = 2 + 4 + 9*(k - 1) + 3 = 9k = S(10^k - 1)`. Таким образом, `S(f(10^k(10^k - 1))) = S(1 + 10^k * (10^k - 1) + 3*10^{2k} (10^k - 1)^2) = 1 + S(10^k - 1) + S(3*(10^k - 1)^2) =``= 2*S(10^k - 1) + 1 = 2*9k + 1`. Так как `1999 = 1 + 2*9*111`, то `S(f(10^111(10^{111} - 1))) = 1999`.