2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Найти количество решений системы уравнений
Сообщение28.04.2014, 13:42 


25/08/05
645
Україна
Найти количество решений системы уравнений
$$
\left \{ \begin{array}{l}
x+y=A,\\
S(x)+S(y)=S(A),
\end{array}
\right.
$$
где $A$ --- очень большое натуральное число(простой перебор не пройдет), $S$ - сумма цифр.

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

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


26/08/11
2057
Причем тут программирование.

$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 
Заслуженный участник


20/12/10
8858
Shadow в сообщении #857529 писал(а):
$S(x)+S(y) \ge S(x+y)$
Неужели так просто? Честно говоря, лень думать, но хотелось бы, чтобы так было.

 Профиль  
                  
 
 Re: Найти количество решений системы уравнений
Сообщение01.05.2014, 11:33 


26/08/11
2057
Ну, опять обдумаю, но кажется просто - сложение столбиком. Для любого разряда возможны три случая: ($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 


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

$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 
Заслуженный участник
Аватара пользователя


09/02/14

1377
Leox в сообщении #856274 писал(а):
Видел где-то ету задачу, но не могу вспомнить

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group