$d-1$ (by assumption, this event occurs with probability at least $(1/2d)^2$) and consider the following two possibilities:

-   $\Pr[f_1=f_2]\geq\frac{1}{4}$,

-   $\Pr[f_1=f_2] < \frac{1}{4}$.

If (i) holds then using a simple calculation one can show that there is $h$ such that $\Pr[A(S) = h] \geq \frac{1}{(2d)^2}\cdot \frac{1}{4}$ and we are done. If (ii) holds then we apply the following [*“random contest”*]{} between $S_1,S_2$:

1.  Pick $x$ such that $f_1(x)\neq f_2(x)$ and draw $y\sim\{\pm 1\}$ uniformly at random.

2.  If $f_1(x)\neq y$ then the output is ${\mathcal{A}}(S_1 \circ (x,y))$, where $S_1\circ (x,y)$ denotes the sample obtained by appending $(x,y)$ to the end of $S$. In this case we say that $S_1$ “won the contest”.

3.  Else, $f_2(x)\neq y$ then the output is ${\mathcal{A}}(S_2 \circ (x,y))$. In this case we that $S_2$ “won the contest”.

Note that adding the auxiliary example $(x,y)$ forces ${\mathcal{A}}$ to make exactly $d$ mistakes on $S_i\circ (x,y)$. Now, if $y\sim\{\pm 1\}$ satisfies $y = c(x) $ then by the mistake-bound argument it holds that ${\mathcal{A}}(S_i\circ (x,y))=c$. Therefore, since $\Pr_{y\sim\{\pm 1\}}[c(x)=y] = 1/2$, it follows that $$\Pr_{S_1,S_2, y}[{\mathcal{A}}(S_i\circ (x,y))=c] \geq \frac{1}{(2d)^2}\cdot \frac{3}{4}\cdot\frac{1}{2} =\Omega(1/d^2),$$ and we are done.

Similar reasoning can be used by induction to handle the remaining cases 