Three is high enough, in my eyes. Two might be. Remember that we don't care about any but the best solution. With one sample you've only got one 50/50 shot to get above the median. With three, the odds of the best of the three being above the median is 87.5%.

Of course picking the median as the random crap boundary is entirely arbitrary, but it'll do until there's a justification for a better number.