Sum of product and sum

[BMAD]

Write a list from 1 to 100.

Pick two numbers at random

Sum the two numbers, find the product of the two numbers

Sum the above two numbers

Erase the two chosen numbers from the list

Add the sum of the two numbers to the list

Repeat until there is only one number.

 

Repeat the above process multiple times.  Is it the same number? Do the numbers center around a point? Bimodal?  analyze.

 

[gavinksong]

a ~ b = a + b + ab

 

associativity: (a ~ b) ~ c = a ~ (b ~ c)

  => (a + b + ab) + c + c(a + b + ab) = a + (b + c + bc) + a(b + c + bc)

  => a + b + c + ab + ac + bc + abc = a + b + c + ab + ac + bc + abc

 

The ~ is also obviously commutative. Thus, our number can be written unambiguously as 1~2~...~99~100.

It is always the same number.

[BMAD]

Hint... Try it for numbers 1-10 see what happens. Then try it for 1-20 and see what happens. Then generalize based on your conclusion.

[BMAD]

anything else we can say about that number?

[gavinksong]

Well, to be more explicit...

 

the value is equal to the sum of the product of every subset of the operands.

This can be seen somewhat intuitively if you interpret "a + b + ab" as

"(all current terms) + (new operand by itself) + (all current terms appended with new operand)"

[k-man]

anything else we can say about that number?

 

For any 1...n sequence the result is (n+1)!-1