After thinking through this, I think it is better to estimate an average of many random variables than the max. We will do say M iterations of choosing k out of n numbers. That is a total of M*k numbers chosen and we will define (Mk) random variables like this:
Define X_i = 1 if the ith chosen number is on LHS of the interval (1..n)
Prob(X_i=1) = p = 0.5
For not too small values of n (say >=100), X_i and X_j are independent. So we can apply Hoeffding's inequality which says that T coin tosses must yield (0.5+eps)*T heads with very high probability. Precisely, in our case we will count the number of times we get heads (X_i=1) for i=1..Mk. We will test for the fact that this number is above the expected number (Mk/2) by say eps=0.1. As per Hoeffding's inequality, this probability is bounded by exp(-2*0.01*M*k). For M=100, k=10, the test succeeds with probability exp(-20) which is small enough for our purpose. 

To summarize: Run 100 iterations of choosing k=10 numbers from n>=100 (both k and n could be different for different iterations), count the number of times the chosen number in the subset is in the left half of the interval 1..n. Check that this occurs no more than 60% of (M*k) i.e., 0.6*10*100=600

http://en.wikipedia.org/wiki/Hoeffding's_inequality
How does this sound?