2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Найти количество решений системы уравнений
Сообщение28.04.2014, 13:42 
Найти количество решений системы уравнений
$$
\left \{ \begin{array}{l}
x+y=A,\\
S(x)+S(y)=S(A),
\end{array}
\right.
$$
где $A$ --- очень большое натуральное число(простой перебор не пройдет), $S$ - сумма цифр.

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

 
 
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 11:10 
Причем тут программирование.

$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$

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

 
 
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 11:14 
Shadow в сообщении #857529 писал(а):
$S(x)+S(y) \ge S(x+y)$
Неужели так просто? Честно говоря, лень думать, но хотелось бы, чтобы так было.

 
 
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 11:33 
Ну, опять обдумаю, но кажется просто - сложение столбиком. Для любого разряда возможны три случая: ($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 --

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

 
 
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 16:14 
Для формального доказательства можно например воспользоваться тем, что

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

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

 
 
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 16:17 
Аватара пользователя
Leox в сообщении #856274 писал(а):
Видел где-то ету задачу, но не могу вспомнить

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group