I find this exercise really tricky and a bit confusing. I'm not very happy with my attempt, but I'll post it, hoping somebody points us in the right direction.
Suppose we perform $O(\log_2(r))$ phase estimations and obtain a set of estimates $\left \{\tilde{w}_i\right\}_{i=1}^{O(\log_2(r))}$.
The probability of obtaining anything other than one of
the two closest estimates can be expressed as $\Pr\left(\forall i, |\tilde{w_i}-w|>\frac{1}{2^n} \right)$. We can bound this as follows:
$$\tag{1} \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n}, \right) \leq \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$
This can be viewed as bounding a binomial probability distribution of the number of successes (zero successes in our case) in a sequence of $O(\log_2(r))$ independent experiments.
Now, the probability that there exists at least one $i_0$ such that $\left|\tilde{w}_{i_0}-w \right| \leq 1/2^n$ is
$$\tag{2} \Pr \left(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq \frac{1}{2^n}\ \right) = 1 - \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n} \right).$$
Given (1), we can bound (2) as follows:
$$ 1 - \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n} \right)\geq 1 - \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$
Therefore, we have:
$$\tag{3} \Pr(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq 1/2^n\ ) \geq 1 - \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$
Finally, we note that the following is true in the asymptotic sense:
$$\tag{4} \left(\frac{1}{2}\right)^r =\left(1-8/\pi^2 \right)^{O(\log_2(r))} \textrm{ as} \ r \rightarrow \infty.$$
Given (4), all is left is to rewrite (3) as follows:
$$\tag{5} \Pr(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq 1/2^n\ ) \geq 1 - \frac{1}{2^r}.$$
Here, we argued that there exists at least one or more estimates that satisfy the condition $|\tilde{w}_{i_0} - w| \leq 1/2^n$ with the probability $1-1/2^r$. The trick is that we already know how many more estimates satisfy the condition. From Theorem 7.1.5 on page 119, we know that with the probability of at least $8/\pi^2 \approx 0.8$, QPE produces an estimate $\tilde{w}$ such that $|\tilde{w}-w| < 1/2^n$. This means that roughly 80% of the estimates in $\{w_i\}_{i=1}^{O(\log_2(r))}$ satisfy the condition.
Therefore, it follows that we can rewrite (5) with a slightly more precise bound on the number of phase estimates that satisfy the condition. Specifically, we can say that instead of at least one estimate, there are, on average, $0.8 \cdot O(\log_2(r))$ estimates that satisfy the condition, and this happens with the probability $1-1/2^r$. Of course $0.8 \cdot O(\log_2(r))$ is the majority.