wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Sum of possible combination
        
(Message started by: Viperdude619 on Feb 14^th, 2004, 6:52pm)

Title: Sum of possible combination
Post by Viperdude619 on Feb 14^th, 2004, 6:52pm

Suppose x and y are whole numbers, with x < y. Find the sum of all the sums of all the numbers in unique combinations of whole numbers between x and y, inclusive.

I know that's a mouthful, so I'll give an example below.

Say x = 1 and y = 3. We then are looking at the numbers 1 through 3, or {1, 2, 3}, to work with. We want to find all the possible unique combinations of these numbers. They would be:

{1},
{2},
{3},
{1, 2},
{1, 3},
{2, 3},
{1, 2, 3}.

That's all of them. So we want the sum of all of the sums of the numbers in each combination, so we'd have

(1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24.

Get it? I hope so. So what I'm asking you is to give me a general formula to find this number, given any x and y.

If I didn't explain this well enough, please let me know, and I'll try to do a better job. I know it's strangely wordy.

Title: Re: Sum of possible combination
Post by SWF on Feb 14^th, 2004, 7:42pm

This one probably belongs in the Easy or Medium section. Hard problems should take more than a minute to solve (solution hidden, highlight to read):
[hide](y*(y+1)-x*(x-1))*2^y-x-1[/hide].