### math puzzle: average of the set of sums

My friend Chris Altomare once asked me a math question which inspired this one:

Given a set

sums(

and the set function

avg(

where #

As an example, let

sums(

the 0 is always included in sums(

Can you find a general formula for avg(sums(

This is actually not super-hard, but the trick is that the "obvious proof" is wrong -- in other words, if we thought of the sums function as giving a multiset, then it becomes a linear function, which would make everything straightforward (since avg is based on linear functions, so avg(sums) is still linearly analyzable and thus easy to find and prove). But this is not the case!

Good luck! I'll post the answer soon.

Given a set

*S*of real numbers, define the setsums(

*S*) := {t: t = ∑ T for some T ⊂*S*}and the set function

avg(

*S*) := ∑*S*/ #*S*,where #

*S*denotes the size of the set*S*(we can leave avg(empty set) undefined).As an example, let

*S*= {2, 5, 7}. Thensums(

*S*) = {0, 2, 5, 7, 9, 12, 14};the 0 is always included in sums(

*S*) as the sum of the empty set. In this example, we also have avg(sums(*S*)) = 7.Can you find a general formula for avg(sums(

*S*)), for any set*S*?This is actually not super-hard, but the trick is that the "obvious proof" is wrong -- in other words, if we thought of the sums function as giving a multiset, then it becomes a linear function, which would make everything straightforward (since avg is based on linear functions, so avg(sums) is still linearly analyzable and thus easy to find and prove). But this is not the case!

Good luck! I'll post the answer soon.

## 0 Comments:

Post a Comment

<< Home