 Solution

Use the quoted event with, for example, $\alpha =1/4$, so at least $3k/4$ clean block means obey the uniform bound. Replacing at most $ϵn$ observations can corrupt at most $ϵn$ blocks. If $k\ge 4\max \{nϵ,1\}$, at least $3k/4-ϵn\ge k/2$ block means remain both uncorrupted and good; adjusting constants handles equality and integer rounding. Their strict majority forces every projected median to obey the same uniform bound. Applying part b and absorbing fixed constants giveswith probability at least $1-e^{-c^{\prime }k}$.