The VC dimension when the samples are fixed
Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$.

Let $M(\epsilon,\delta)$ be the minimal number of samples required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any distribution $\mathcal{D}$ over the sample space $\mathcal{X}$, we can treat this case as a uniform distribution with finite support $S=\left\{a_1,...,a_n\right\}$ (picked by the adversary). The learner picks a  set $T\subseteq S$ of $n/2$ samples (chosen uniformly at random), and chooses any consistent hypothesis $h$ (relative to $T$).

There are two issues which prevent us from directly using the known bounds on $err(h)$. 

The first is that we are only interested in the error on the set $S\setminus T$, i.e. the training and test samples are not independent. This will add an extra $2$ factor to the bounds on $err(h)$, since:

$err(h)=\Pr_{x\sim\mathcal{D}}\left(h(x)\neq f^*(x)\right)=
\Pr\left(h(x)\neq f^*(x) | x\in T\right)\Pr(x\in T)+\Pr\left(h(x)\neq f^*(x) | x\notin T\right)\Pr(x\notin T)$.

In this case we have $\Pr(x\in T)=\Pr(x\notin T)=\frac{1}{2}$, and $\Pr\left(h(x)\neq f^*(x) | x\in T\right)=0$ ($h$ is consistent with $T$). So we get $err(h)=\frac{1}{2}\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, or equivalently $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)=2err(h)$, where the left hand side is the probability that we wish to bound.

The second issue is caused by the fact that we don't allow repetitions while picking $T$ (the usual model treats each training sample as chosen independently from the distribution $\mathcal{D}$). To avoid this issue, the learner could choose $T$ by taking $m$ independent samples form $\mathcal{D}$, such that with high probability we see at least $\frac{|S|}{2}$ samples. This can be easily done by picking $m\approx |S|$, and conditioning on the event that we saw at least half of $S$, we can use the regular bounds on $err(h)$ for sample size $\ge|S|/2$.