So I have $A=a_1,a_2,a_3,\dots,a_n$, which are real numbers in the interval $[0,1]$. It is given that $n$ is odd. I am asked to prove that it is not possible to obtain an estimate of the median by taking $o(n)$ (less than $n$) random samples from $A$ and computing the sample median with $\epsilon=\frac{1}{8}$, where $\epsilon$ is the error ($\pm \epsilon$) of the estimate.
The problem also states that it does not matter if the random samples are taken with or without replacement.
In a previous part of this section, I proved that it was possible to get an estimate of the mean of $a_i$'s on the interval $[-1,1]$ using the Hoeffding inequality to get a bound on the error within a given confidence level. This problem doesn't seem that similar though, and I'm really not at all sure where to start. Any ideas?
Also, I don't understand why it matters whether or not $n$ is odd.