Сколько жителей в Шоколадном?

[Xenia1996]

В день, когда родилась его внучка, мэр города Шоколадного заметил, что число жителей города (включая мэра и внучку) сравнялось с наименьшим натуральным числом, представимым как в виде суммы 2011 натуральных слагаемых с одинаковой суммой цифр, так и в виде суммы 2012 натуральных слагаемых с одинаковой суммой цифр.
Сколько жителей стало в Шоколадном?

[Руст]

$2011=4\mod 9, \ 2012=5\mod 5$. Поэтому минимальное решение $2011*5=10055$. Часть из разбиения на 2012 по 4, часть можно по 13.

[Xenia1996]

Руст в сообщении #452883 писал(а):

$2011=4\mod 9, \ 2012=5\mod 5$. Поэтому минимальное решение $2011*5=10055$. Часть из разбиения на 2012 по 4, часть можно по 13.

Во-вторых, не $\mod 5$, а $\mod 9$, а во-первых, разбить красивее можно. Например, 2011 четвёрок и одно число 2011.
Но в целом верно.

-- Чт июн 02, 2011 10:32:45 --

А давайте задачу обобщим?

Для каждого натурального $ n $ найти наименьшее натуральное число, представимое как в виде суммы $ n $ натуральных слагаемых с одинаковой суммой цифр, так и в виде суммы $n+1$ натуральных слагаемых с одинаковой суммой цифр.

[maxal]

Xenia1996 в сообщении #452886 писал(а):

Для каждого натурального $ n $ найти наименьшее натуральное число, представимое как в виде суммы $ n $ натуральных слагаемых с одинаковой суммой цифр, так и в виде суммы $n+1$ натуральных слагаемых с одинаковой суммой цифр.

Что-то типа:

$$\begin{cases} 9(n+1), & \text{if}\ n\equiv 0\pmod{9}\\ 2n, & \text{if}\ n\equiv 1\pmod{9}\\ 3n, & \text{if}\ n\equiv 2, 5\pmod{9}\\ 3(n+1), & \text{if}\ n\equiv 3, 6\pmod{9}\\ 5n, & \text{if}\ n\equiv 4\pmod{9}\\ 2(n+1), & \text{if}\ n\equiv 7\pmod{9}\\ 9n, & \text{if}\ n\equiv 8\pmod{9} \end{cases}$$

[Xenia1996]

maxal в сообщении #453226 писал(а):

Что-то типа:

$$\begin{cases} 9(n+1), & \text{if}\ n\equiv 0\pmod{9}\\ 2n, & \text{if}\ n\equiv 1\pmod{9}\\ 3n, & \text{if}\ n\equiv 2, 5\pmod{9}\\ 3(n+1), & \text{if}\ n\equiv 3, 6\pmod{9}\\ 5n, & \text{if}\ n\equiv 4\pmod{9}\\ 2(n+1), & \text{if}\ n\equiv 7\pmod{9}\\ 9n, & \text{if}\ n\equiv 8\pmod{9} \end{cases}$$

Да не "типа", а так оно и есть.

(Оффтоп)

Или Вы думаете по-английски, а пишете по-русски?
Вы ведь имели в виду "something like this"?

Осталось только доказать, что такое представление всегда существует.
В случае $n=2011$ это было легко, так как сумма цифр не просто 4 по модулю 9, но ещё и равна 4. А если взять, скажем, $n=7777777$ ? Тоже ведь 4 по модулю 9.

[Руст]

При минимальности использовалось то, что $2012=-2011=-4\mod 9$. Именно поэтому 5*2011 давал минимум. А разбиение на 2012 не однозначно. Поэтому я писал "можно" заполнить остальные с 13.

[Xenia1996]

Руст в сообщении #453249 писал(а):

При минимальности использовалось то, что $2012=-2011=-4\mod 9$. Именно поэтому 5*2011 давал минимум. А разбиение на 2012 не однозначно. Поэтому я писал "можно" заполнить остальные с 13.

Хорошо.
Но вот как Вы разобьёте, скажем 7777777*5?

[age]

Xenia1996 в сообщении #453251 писал(а):

Хорошо.
Но вот как Вы разобьёте, скажем 7777777*5?

Никак. Можно только $7777777\cdot83$

[maxal]

Xenia1996 в сообщении #453251 писал(а):

Но вот как Вы разобьёте, скажем 7777777*5?

$$7777777\cdot 5 = 6913581\cdot 4 + 864197\cdot 13$$

всего $6913581 + 864197 = 7777778$ штук.

[Xenia1996]

maxal в сообщении #453342 писал(а):

Xenia1996 в сообщении #453251 писал(а):

Но вот как Вы разобьёте, скажем 7777777*5?

$$7777777\cdot 5 = 6913581\cdot 4 + 864197\cdot 13$$

всего $6913581 + 864197 = 7777778$ штук.

Хорошо.
Но это только пример.
Как доказать, что разбиение существует всегда?

[age]

Для $n\equiv4\mod9$:

$\begin{cases} 4k+13m=5n\\ k+m=n+1 \end{cases}$

Откуда $9m=n-4$. Но $n\equiv4\mod9$, поэтому разбиение существует всегда.