= Solution
For $d\geq1$, take the $d+1$ vertices $v_0,\ldots,v_d$ of a <regular simplex> in $\mathbb R^d$, centered at zero and scaled so that $\|v_j\|=1$. For example, realize them as
$$
v_j=\sqrt{\frac{d+1}{d}}\left(e_j-\frac1{d+1}\mathbf1\right),\qquad 0\leq j\leq d,
$$
in the $d$-dimensional <vector subspace> $\{z\in\mathbb R^{d+1}:\sum_jz_j=0\}$, identified isometrically with $\mathbb R^d$. These vertices are <affinely independent>.
Assign arbitrary desired signs $s_j\in\{-1,1\}$, positive for inclusion. <Affine independence> implies that there is an <affine function> $\ell(x)=a\cdot x+b$ with $\ell(v_j)=s_j$ for every $j$: the $d+1$ interpolation conditions form an invertible <linear system>. For a sufficiently small $\eta>0$, choose
$$
c=\frac\eta2a,\qquad r^2=1+\eta b+\frac{\eta^2}{4}\|a\|^2>0.
$$
At every vertex,
$$
r^2-\|v_j-c\|^2
=\eta(a\cdot v_j+b)=\eta s_j.
$$
Thus the <Euclidean ball> contains exactly the positively labelled vertices, with none on its boundary. This construction also covers the all-positive and all-negative labellings. Therefore
$$
\boxed{\{v_0,\ldots,v_d\}\text{ is shattered by }\mathcal B_d.}
$$
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/learning-theory-2015-balls-shatter-triangle.png]
{title=Closed <Euclidean balls> realize all eight labellings of three <regular simplex> vertices in the plane}
{description=Filled blue points are inside each shaded disk; red crosses are outside. The same three points are used in every panel.}
Back to article page
