uniolympiads Ελληνικά

IMC 2001, Day 2, Problem 3

Find the maximum number of points on a sphere of radius 11 in Rn\mathbb{R}^n such that the distance between any two of these points is strictly greater than 2\sqrt{2}.

Original from the official PDFFind the maximum number of points on a sphere of radius 1 in R n √ such that the distance between any two of these points is strictly greater than 2.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. The unit sphere in Rn\mathbb{R}^n is defined by

Sn−1={(x1,…,xn)∈Rn∣∑k=1nxk2=1}.S_{n-1}=\left\{(x_1,\dots,x_n)\in\mathbb{R}^n|\sum_{k=1}^nx_k^2=1\right\}.
The distance between the points X=(x1,…,xn)X=(x_1,\dots,x_n) and Y=(y1,…,yn)Y=(y_1,\dots,y_n) is:
d2(X,Y)=∑k=1n(xk−yk)2.d^2(X,Y)=\sum_{k=1}^n(x_k-y_k)^2.
We have
d(X,Y)>2⇔d2(X,Y)>2⇔∑k=1nxk2+∑k=1nyk2+2∑k=1nxkyk>2⇔∑k=1nxkyk<0\begin{aligned}d(X,Y)>\sqrt2\quad&\Leftrightarrow\quad d^2(X,Y)>2\\&\Leftrightarrow\quad\sum_{k=1}^nx_k^2+\sum_{k=1}^ny_k^2+2\sum_{k=1}^nx_ky_k>2\\&\Leftrightarrow\quad\sum_{k=1}^nx_ky_k<0\end{aligned}
Taking account of the symmetry of the sphere, we can suppose that
A1=(−1,0,…,0).A_1=(-1,0,\dots,0).
For X=A1X=A_1, ∑k=1nxkyk<0\sum\limits_{k=1}^nx_ky_k<0 implies y1>0y_1>0, ∀ Y∈Mn\forall\,Y\in M_n.

Let X=(x1,X‾)X=(x_1,\overline{X}), Y=(y1,Y‾)∈Mn\{A1}Y=(y_1,\overline{Y})\in M_n\backslash\{A_1\}, X‾,Y‾∈Rn−1\overline{X},\overline{Y}\in\mathbb{R}^{n-1}.

We have

∑k=1nxkyk<0⇒x1y1+∑k=1n−1x‾ky‾k<0⇔∑k=1n−1xk′yk′<0,\sum_{k=1}^nx_ky_k<0\Rightarrow x_1y_1+\sum_{k=1}^{n-1}\overline{x}_k\overline{y}_k<0\Leftrightarrow\sum_{k=1}^{n-1}x_k'y_k'<0,
where
xk′=x‾k∑x‾k2,yk′=y‾k∑y‾k2.x_k'=\frac{\overline{x}_k}{\sqrt{\sum\overline{x}_k^2}},\quad y_k'=\frac{\overline{y}_k}{\sqrt{\sum\overline{y}_k^2}}.
therefore
(x1′,…,xn−1′),(y1′,…,yn−1′)∈Sn−2(x_1',\dots,x_{n-1}'),(y_1',\dots,y_{n-1}')\in S_{n-2}
and verifies ∑k=1nxkyk<0\sum\limits_{k=1}^nx_ky_k<0.

If ana_n is the search number of points in Rn\mathbb{R}^n we obtain an≤1+an−1a_n\le1+a_{n-1} and a1=2a_1=2 implies that an≤n+1a_n\le n+1.

We show that an=n+1a_n=n+1, giving an example of a set MnM_n with (n+1)(n+1) elements satisfying the conditions of the problem.

A1=(−1,0,0,0,…,0,0)A2=(1n,−c1,0,0,…,0,0)A3=(1n,1n−1⋅c1,−c2,0,…,0,0)A4=(1n,1n−1⋅c1,1n−1⋅c2,−c3,…,0,0)\begin{aligned}A_1&=(-1,0,0,0,\dots,0,0)\\A_2&=\bigl(\tfrac1n,-c_1,0,0,\dots,0,0\bigr)\\A_3&=\Bigl(\tfrac1n,\tfrac{1}{n-1}\cdot c_1,-c_2,0,\dots,0,0\Bigr)\\A_4&=\Bigl(\tfrac1n,\tfrac{1}{n-1}\cdot c_1,\tfrac{1}{n-1}\cdot c_2,-c_3,\dots,0,0\Bigr)\end{aligned}
An−1=(1n,1n−1⋅c1,1n−2⋅c2,1n−3⋅c3,…,−cn−2,0)An=(1n,1n−1⋅c1,1n−2⋅c1,1n−3⋅c3,…,12⋅cn−2,−cn−1)An+1=(1n,1n−1⋅c1,1n−2⋅c2,1n−3⋅c3,…,12⋅cn−2,cn−1)\begin{aligned}A_{n-1}&=\Bigl(\tfrac1n,\tfrac{1}{n-1}\cdot c_1,\tfrac{1}{n-2}\cdot c_2,\tfrac{1}{n-3}\cdot c_3,\dots,-c_{n-2},0\Bigr)\\A_n&=\Bigl(\tfrac1n,\tfrac{1}{n-1}\cdot c_1,\tfrac{1}{n-2}\cdot c_1,\tfrac{1}{n-3}\cdot c_3,\dots,\tfrac12\cdot c_{n-2},-c_{n-1}\Bigr)\\A_{n+1}&=\Bigl(\tfrac1n,\tfrac{1}{n-1}\cdot c_1,\tfrac{1}{n-2}\cdot c_2,\tfrac{1}{n-3}\cdot c_3,\dots,\tfrac12\cdot c_{n-2},c_{n-1}\Bigr)\end{aligned}
where
ck=(1+1n)(1−1n−k+1),k=1,n−1‾.c_k=\sqrt{\left(1+\frac1n\right)\left(1-\frac{1}{n-k+1}\right)},\quad k=\overline{1,n-1}.
We have ∑k=1nxkyk=−1n<0\sum\limits_{k=1}^nx_ky_k=-\frac1n<0 and ∑k−=1nxk2=1\sum\limits_{k-=1}^nx_k^2=1, ∀X,Y∈{A1,…,An+1}\quad\forall X,Y\in\{A_1,\dots,A_{n+1}\}.

These points are on the unit sphere in Rn\mathbb{R}^n and the distance between any two points is equal to

d=21+1n>2.d=\sqrt2\sqrt{1+\frac1n}>\sqrt2.

Remark. For n=2n=2 the points form an equilateral triangle in the unit circle; for n=3n=3 the four points from a regular tetrahedron and in Rn\mathbb{R}^n the points from an nn dimensional regular simplex.

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?