My Photo
Name: Tyler
Location: Mountain View, California, United States

thinking := [life, games, movies, philosophy, math, coding, pizza, &c.]

Sunday, February 03, 2008

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 S of real numbers, define the set

sums(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}. Then

sums(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