Suppose a seller has $n$ fruits and you would like to buy $n/3$ of them. Now you know that $k$ of those fruits are rotten inside (but you do not know which $k$ are rotten while buying, but the seller does!). Assume $k < n/3$. You would like to pick your $n/3$ fruits to avoid rotten fruits as much as possible.
The seller knows your tricks in selecting fruit, and would adversarially place them so that you'd pick the bad ones. If you deterministically choose $n/3$ fruits, the seller (knowing your choice) would make sure you get all the $k$ bad fruits. So we have to be randomized to hope to beat the seller. Suppose we choose $n/3$ fruits totally at random, then we can show that the intersection of our choice with the rotten fruits is small on avg.
But now suppose we do not have perfect randomness. That is, we cannot choose from $\binom{n}{n/3}$ possibilities uniformly. However we can choose randomly from some smaller subset (say polynomial in $n$) of the set of all possibilities. What is a choice of sample space that minimizes the probability of too many rotten fruits in our collection?
Reminds me of some hat problem. But I am unable to figure out how to proceed with this- set intersections? error correcting codes? Hash functions? Limited independence?