Weighted balls and bins Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$.  We throw the balls into the bins randomly, i.e., each ball lands into a random bin.

Can we argue that with constant probability, if you take the heaviest ball that lands into each non-empty bin, you get a set of balls whose total weight is $c T$ for some constant $c \in [0,1]$? I prefer $c$  as close to $1$ as possible but I want to make sure that the probability that happens is at least a constant.
Suppose you have $n$ balls. Take a random ball from each non-empty bin. Your expected weight is approximately $(1-1/e)T$. This holds because the probability that a bin is empty is $(1-1/n)^n \approx 1/e$. Thus, the expected number of balls you get is $(1-1/e)n$, and these are a random sample of all the balls.

Now, suppose you have balls whose weights are not all equal. Then the expected weight is at least $(1-1/e)T$, because you always take the largest ball from each bin. However, you never get a total weight larger than $T$. This means that at least half the time, you must get a weight of at least $(1-2/e)T$. 

You're never going to get $c &gt; 1-1/e$. That's probably the right answer for $c$, but to get it you probably need to use probability theory that's at least a little more sophisticated than I did.