Question

Let S be an array with n distinct integers. Similar to the selection algorithm, we partition S into n / 11 sub-arrays, each of which contains 11 numbers. Let x be the median of the medians of the LaTeX: n/11n / 11 sub-arrays. How many numbers in LaTeX: SS are guaranteed to be less than LaTeX: xx?

Answer 1

Answer:

The answer is "$\bold{\frac{3n}{11}}$"

Explanation:

The value x was its $\frac{n}{11}$ average array median. Almost every other median is less than 6 elements, because the total of 11 components is  all mediums of its arrays i.e. $\frac{n}{22}$ it's less than half x.  Its at least x is also less than:

$\to 6 \times \frac{n}{22} \\\\ \to \frac{3n}{11}$