|
|
вернуться в форумI've solved it using bruteforce for small K and then guessing the formula. But I still don't know the proof. Can anybody write it? S(A + B) = S(A) + S(B) is equal to that that for every pair of corresponding digits of A and B their sum is lower then 10 (1).
For example:
12 and 13 :1+1<10;2+3<10 it means S(A + B) = S(A) + S(B)
18 and 19: 8+9>10 it means S(A + B) = S(A) + S(B) is wrong here.
Then for every pair of digits from A and B you just count how many varints of pair suits (1) and multiply these quantities for all pairs. thanks Another way to go at it is to think of the number (A+B) as a bunch of stacked blocks, each stack representing a digit. Here is 43 for example:
_
|_| _
|_||_|
|_||_|
|_||_|
Now, to find all the A's and B's that can form S(A+B) = S(43), for example 12+31 or 22+21, etc, we can represent this as chopping each stack into two parts, for example in the case of 12+31:
_
|_| _
_ |_|
|_||_|
|_| _
|_||_|
Now, if we take the general case of having two digits, if the first digit is 1, we can't split the first digit in two since the first digit of A or B can't be 0. However, if the first digit is 2, we can split it in one way (in the middle), and then we can split the second digit depending on what digit it is. If it is 2, we can split it in 3 different ways ( (0,2),(1,1),(2,0) ). If it is 3, we can split it in 4 different ways, etc. So, if the first digit of the two-digit number is 2, we can split the whole number in 1*(1+2+3+4+5+6+7+8+9+10)=1+(10*11/2) different ways. If the first digit is 3, we can split the whole number in 2*(1+2+3+4+5+6+7+8+9+10)=2*(10*11/2) different ways, etc. If we sum everything we get (8*9)/2*(10*11)/2 ways to split a two digit number. For an n digit number continuing the same way we get (8*9)/2*((10*11)/2)^(n-1). |
|
|
