Задание 19. Натуральные числа с нечетной и четной суммами цифр

[Яков Самуилович]

Натуральные числа 1, 2, …, n разбиты на две группы. К первой группе отнесены числа с нечетной суммой цифр, ко второй группе – с четной. Для каждой группы найдена сумма чисел этой группы. Затем вычислен модуль разности этих сумм.
а) Приведите пример n, для которого в результате этих вычислений было получено число 16.
б) Чему равен результат при n = 60?
в) Каков наибольший возможный результат для трехзначных n?

[Александр Хоцков]

а) n=12.
Группа 1: 1, 3, 5, 7, 9, 10, 12. Сумма: 47
Группа 2: 2, 4, 6, 8, 11. Сумма: 31
б) 60.
Заметим, что числа внутри одного десятка (от 0 до 9, от 10 до 19 и т.д.) можно разбить на 5 пар, в каждой паре два последовательных числа, принадлежащие разным группам. Разность чисел в каждой паре внутри одного десятка равна 1 или -1. Поэтому искомая разность среди десятка 5 или -5, знак зависит от чётности суммы цифр десятков.
Например, от 0 до 9 (0 можем добавить в набор, т.к. он не влияет на сумму), разность первой группы и второй равна 5, от 10 до 19: -5, а от 0 до 19: 0. И так далее. То есть в двадцатках (от 0 до 19, от 20 до 39, от 40 до 59 и т.д.) разность равна 0. Соотвество от 0 до 59: 0, и остаётся 60 из следующего десятка.

[Александр Хоцков]

Попробую объяснить пункт б более точно и решить пункт в.
б) Введём функцию f(k), k ∈ Z, k>=0, где f(k)=k, если сумма цифр k нечётная, то есть k принадлежит к первой группе чисел, и f(k)=-k, если сумма цифр k чётная, то есть k принадлежит ко второй группе чисел.
Также введём функцию g(a,b), a,b ∈ Z, 0<= a <=b, где g(a,b) равна сумме f(i) всех i, входящих в отрезок [a, b]. Тогда искомый модуль разности групп от 1 до n равен |g(1, n)|.
Так как g(a, b) - это сумма чисел, то функция обладает следующим свойством: g(a,b)=g(a,i)+g(i+1, b), где 0<= a <= i < b. Также для упрощения будем начинать отсчёт от 0, так как f(0)=0, то g(0,n)=0+g(1,n)=g(1,n)
Таким образом на основе свойства, g(0,n) можно посчитать по частям.
Десятком назовём числа, входящие в отрезок [10k, 10k+9], k ∈ Z, k>=0. Посчитаем сумму g(10k+10k+9): десяток разобьём на 5 пар чисел: 10k и 10k+1, 10k+2 и 10k+3, ... 10k+8 и 10k+9. Заметим, что два числа, стоящие в таких парах, принадлежат разным группам чисел, так как это два подряд стоящих числа, количество десятков у которых одинаково, а следовательно значения функции f для этих чисел противоположны по знаку. Поэтому f(10k)+f(10k+1)=f(10k+2)+f(10k+3)=...=f(10k+8)+f(10k+9)=sign(f(10k+1))*1 => g(10k,10k+9)=5*sign(f(10k+1)).
Значения сумм g для двух рядом стоящих десятков противоположны (5 и -5), поэтому g(10k,10k+9)+g(10k+10,10k+19)=0=g(10k,10k+19)
Теперь можем посчитать |g(1,60)|=|g(0,19)+g(20,39)+g(40,59)+f(60)|=|0+0+0+f(60)|=60
Ответ: 60.
в) Можем сосчитать g(100k,100k+99)=g(100k,100k+19)+g(100k+20,100k+39)+...+g(100k+80,100k+99)=0
Введём функцию m(a, b), a,b ∈ Z, 0<= a <=b, где m(a,b) равняется максимуму из |g(1,i)| для всех i, входящих в отрезок [a, b]. Тогда искомая величина равняется m(100, 999).
Рассмотрим m(20k, 20k+19), k ∈ Z, 5 <= k <= 49 (так как мы рассматриваем трёхзначные числа): g(1, 20k-1)=0 (пункт б), поэтому ищем наибольшее число среди |g(20k,20k)|, |g(20k,20k+1)|,|g(20k,20k+2)|, ... , |g(20k,20k+19)|. Поэтапно вычисляем каждое g.
|f(20k)|, |f(20k)+f(20k+1)|, ... , |g(20k, 20k+9)|, |g(20k, 20k+9)+f(20k+10)|, ... , |g(20k,20k+19)|.
20k, 1, 20k+1, 2, 20k+2, 3, 20k+3, 4, 20k+4, 5 (один десяток), 20k+15, 4, 20k+16, 3, 20k+17, 2, 20k+18, 1, 20k+19, 0.
Наибольшее число из этого набора является 20k+19=|g(20k,20k+18)| => m(20k,20k+19)=20k+19
Также заметим, что m(20k,20k+19)=20k+19 < 20k+39=m(20k+20,20k+39) при всех k, которые мы рассматриваем => m(20k, 20k+39)=m(20k+20,20k+39), а поэтому максимум достигается при больших k.
k=49. m(980, 999)=999=m(100,999)
Ответ: 999 при n=998.

[Яков Самуилович]

Попробую объяснить пункт б более точно и решить пункт в.
б) Введём функцию f(k), k ∈ Z, k>=0, где f(k)=k, если сумма цифр k нечётная, то есть k принадлежит к первой группе чисел, и f(k)=-k, если сумма цифр k чётная, то есть k принадлежит ко второй группе чисел.
Также введём функцию g(a,b), a,b ∈ Z, 0<= a <=b, где g(a,b) равна сумме f(i) всех i, входящих в отрезок [a, b]. Тогда искомый модуль разности групп от 1 до n равен |g(1, n)|.
Так как g(a, b) - это сумма чисел, то функция обладает следующим свойством: g(a,b)=g(a,i)+g(i+1, b), где 0<= a <= i < b. Также для упрощения будем начинать отсчёт от 0, так как f(0)=0, то g(0,n)=0+g(1,n)=g(1,n)
Таким образом на основе свойства, g(0,n) можно посчитать по частям.
Десятком назовём числа, входящие в отрезок [10k, 10k+9], k ∈ Z, k>=0. Посчитаем сумму g(10k+10k+9): десяток разобьём на 5 пар чисел: 10k и 10k+1, 10k+2 и 10k+3, ... 10k+8 и 10k+9. Заметим, что два числа, стоящие в таких парах, принадлежат разным группам чисел, так как это два подряд стоящих числа, количество десятков у которых одинаково, а следовательно значения функции f для этих чисел противоположны по знаку. Поэтому f(10k)+f(10k+1)=f(10k+2)+f(10k+3)=...=f(10k+8)+f(10k+9)=sign(f(10k+1))*1 => g(10k,10k+9)=5*sign(f(10k+1)).
Значения сумм g для двух рядом стоящих десятков противоположны (5 и -5), поэтому g(10k,10k+9)+g(10k+10,10k+19)=0=g(10k,10k+19)
Теперь можем посчитать |g(1,60)|=|g(0,19)+g(20,39)+g(40,59)+f(60)|=|0+0+0+f(60)|=60
Ответ: 60.
в) Можем сосчитать g(100k,100k+99)=g(100k,100k+19)+g(100k+20,100k+39)+...+g(100k+80,100k+99)=0
Введём функцию m(a, b), a,b ∈ Z, 0<= a <=b, где m(a,b) равняется максимуму из |g(1,i)| для всех i, входящих в отрезок [a, b]. Тогда искомая величина равняется m(100, 999).
Рассмотрим m(20k, 20k+19), k ∈ Z, k>=10 (так как мы рассматриваем трёхзначные числа): g(1, 20k-1)=0 (пункт б), поэтому ищем наибольшее число среди |g(20k,20k)|, |g(20k,20k+1)|,|g(20k,20k+2)|, ... , |g(20k,20k+19)|. Поэтапно вычисляем каждое g.
|f(20k)|, |f(20k)+f(20k+1)|, ... , |g(20k, 20k+9)|, |g(20k, 20k+9)+f(20k+10)|, ... , |g(20k,20k+19)|.
20k, 1, 20k+1, 2, 20k+2, 3, 20k+3, 4, 20k+4, 5 (один десяток), 20k+15, 4, 20k+16, 3, 20k+17, 2, 20k+18, 1, 20k+19, 0.
Наибольшее число из этого набора является 20k+19=|g(20k,20k+18)| => m(20k,20k+19)=20k+19
Также заметим, что m(20k,20k+19)=20k+19 < 20k+39=m(20k+20,20k+39) при всех k, которые мы рассматриваем => m(20k, 20k+39)=m(20k+20,20k+39), а поэтому максимум достигается при больших k.
k=49. m(980, 999)=999=m(100,999)
Ответ: 999 при n=998.

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

Только в пункте в) после определения функции m(a,b) вы рассматриваете m(20k,20k+10) при k>=10, а надо при k>=5. Да и насколько я понимаю, оценка снизу здесь не особо важна, ее необязательно указывать, важнее оценка сверху k<=49.