mshubham's blog

Sum(A) = Sum(B) | Math Problem
By mshubham, 13 years ago, In English

Source: Mathalon

Given ai,bi belongs to set {1,2,3,4,5,6,7,8,9,0}

Find the Number of different solution for N=10 such that a1+a2+..aN=b1+b2+..bN=k and k takes all value 0<=k<=9N

Example N=1 for each 0<=k<=9 we have one solution so the answer is 10

Can anyone solve this problem ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

If we know that d[n] is number of different solutions of Sum(a[i],i=1..10)=n then ans is Sum(d[i]*d[i],i=0..90). Now we have to find d[n].

→ Reply
  • »
    »
    13 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +2 Vote: I do not like it

    d[n] = C(n + 9,9) C(n,k) — binomial coefficient

    P.S. It is wrong because I missed condition that a[i]<=9.
    But it can be made with same idea using inclusion-exclusion principle.

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I think it wont work, because this formula works for the problem where a[i] can be any positive number, but here a[i] less then 10.

      → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      according to problem 0<=n<=90 and all a[i]'s <=9 this C(n+9,9) works iff a[i]>=0 upto infinite..

      → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      .

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        Don't panic. Everyone likes your solution:)

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Actually, I have a question about inclusion-exclusion principle. If you have time,of course, can you show how to use this on this problem? I can't get how use it on this, for me it looks big and tremendous, maybe there any good way of using it, but I can't see it.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it +8 Vote: I do not like it

            Lets generalise this problem.
            We have to find number of solutions a[1] + a[2] + ... + a[N] = S and have N constraints.
            i-th constraint : a[i] < b[i].
            Let MASK be the sequence of N bits, in which if i-th bit equals 1 than we know that i-th constraint doesn't hold for this mask, otherwise we don't know anything about it. F(MASK) — number of solutions for this mask. It means that if MASK[i] == 1 than we have a[i] >= b[i] else a[i] >= 0
            To solve such problem we make such substitutions a[i] = a[i]' + b[i] or a[i] = a[i]'.
            Now we have problem
            a[1]' + a[2]' + ... a[N]' = S - sum(1 to n) MASK[i] * b[i]
            We know how to solve it.

            By inclusion-exclusion principle we have that
            answer = sum(MASK from 0 to 2 ^ N - 1) (-1) ^ OnesInMask(MASK) * F(MASK)

            In problem from this post we have that
            if OnesInMask(MASK1) = OnesInMask(MASK2) than F(MASK1) = F(MASK2)
            so we don't need to calculate all F(MASK).

            → Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it +4 Vote: I do not like it

    Ok, so we decreased problem to a typical dynamic programming problem.

    Suppose, we have fixed K. Let's find number of different solutions of Sum(a[i], i = 1..10) = K, where 0<=a[i]<=9 Let's build this kind of dynamic: d[used][total_sum] , where "used" — number of "a" we used, "total_sum" -the sum of this a-s.

    so the code for will look something like this:

    int n = 10;
int max_number = 9;
int max_sum = max_number*n;
int d[n + 5][max_sum + 2*max_number];
d[0][0] = 1;
for(int i = 0; i<n;i++)
{
    for(int cur_sum = 0; cur_sum < max_sum; cur_sum++)
    {
        for(int j = 0; j<max_number; j++)
        {
           d[i+1][cur_sum + j] += d[i][cur_sum];
        }
    }
}

    The sizes of array d is a bit bigger to avoid runtime errors. Suppose this part isn't difficult, I tried to put logical names to variables.

    So, the penultimate step — to find number of different solutions for some k — as said demolishka this is d[k]*d[k] And the last one is just sum up all the sums for all k from 0 to 9*N I haven't tested this code in order to just show the idea. There can be some kind of typical problems such as big numbers — maybe for this n and k they will less then 10^9 but, as I said, I haven't tested. If this will appear try to use long long int against int, if this won't help, try write your own long arithmetic or use some standard classes in C# or Java or other languages)

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
      ← Rev. 6  
      Vote: I like it 0 Vote: I do not like it

      first of all thanks for your solution.. I have tested your code.. we have to use equality on each three for loop

      for(ll i = 0; i<=n;i++){
    	for(ll cur_sum = 0; cur_sum <= max_sum; cur_sum++){
        	for(ll j = 0; j<=max_number; j++){
         		d[i+1][cur_sum + j] += d[i][cur_sum];
        	}
    	}
}

      here ll is for long long, but it is not sufficient for n=10, I am not well in java.. can anyone convert this code into java (BigInteger) to calculate exact answer.. thanks

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        You actually should change to long long just array. Anyway, I wrote it on Java so here the code http://pastebin.com/wFNFnCt1

        And the answer is 3081918923741896840 < 2^63, so it can be done in c++ with long long int.

        I've got accepted on Mathalon this problem, hope you'll try to solve it on c++)

        → Reply