Найти количество решений системы уравнений

[Leox]

Найти количество решений системы уравнений

$$ \left \{ \begin{array}{l} x+y=A,\\ S(x)+S(y)=S(A), \end{array} \right. $$

где $A$ --- очень большое натуральное число(простой перебор не пройдет), $S$ - сумма цифр.

Видел где-то ету задачу, но не могу вспомнить

[Shadow]

Причем тут программирование.

$S(x)+S(y) \ge S(x+y)$ причем равенсто возможно только при равенстве в каждом разряде. Простое сложение столбиком

$A=\overline{a_n\cdots a_2a_1}$

И если $x_k+y_k=10+a_k$, то в следующем разряде можно компенсировать только единичку, но еще 9 никак.

Или $x_k+y_k=a_k \forall k$

Дальше очевидно.

[nnosipov]

Shadow в сообщении #857529 писал(а):

$S(x)+S(y) \ge S(x+y)$

Неужели так просто? Честно говоря, лень думать, но хотелось бы, чтобы так было.

[Shadow]

Ну, опять обдумаю, но кажется просто - сложение столбиком. Для любого разряда возможны три случая: ($x_k,y_k,a_k$ - цифры на k-той позиции)
$a_k=x_k+y_k$
$a_k=x_k+y_k+1$ (если есть перенос с предыдушего разряда)
$a_k=x_k+y_k-10$ (с переносом 1 на следующий разряд)

Последние два случая очень неравностойны по отношению к требованию $\sum (x_k+y_k)=\sum a_k$

-- 01.05.2014, 12:00 --

Есть и четвертый вариант - при перенос с предыдущей и перенос к следующей позиции, но он ничего особо не меняет.

[Shadow]

Для формального доказательства можно например воспользоваться тем, что

$S(X)+S(Y)-S(X+Y)=9n$ - прямое следствие от $S(N)\equiv N \pmod 9$

А то, что $n \ge 0$ и что равенство возможно только когда $x_k+y_k<10$ для любого разряда $k$ наверное можно доказать по индукции для числа разрядов.
Хотя и так все ясно.

[kp9r4d]

Leox в сообщении #856274 писал(а):

Видел где-то ету задачу, но не могу вспомнить

Недавно прошедший первый этап АСМ ICPC в Украине. Решалось ровно так, как говорит Shadow.