Какое наибольшее число точек можно расположить на плоскости так, чтобы расстояния между любыми двумя различными точками были одинаковы?
Легко понять, что нам подойдут три точки, образующие правильный треугольник, а четвёртую точку добавить не получается.
А сколько точек можно расположить на плоскости, чтобы расстояния между точками могли принимать не одно, а два различных значение?
На плоскости нам подойдёт в качестве примера правильный пятиугольник.
А в трёхмерном пространстве? А в произвольном d-мерном?
Поясним, что такое d-мерное пространство? Да всё такое же, как и в привычных размерностях! Точка x задаётся набором координат. Только этих координат не две и не три, а сразу d: x=(x[1],x[2],...,x[d]).
А как считать расстояния между двумя точками? Опять же, ничего нового. Всё та же теорема Пифагора!
Если x=(x[1],x[2],...,x[d]), y=(y[1],y[2],...,y[d]), то
|x-y|^2=(x[1]-y[1])^2+(x[2]-y[2])^2+...(x[d]-y[d])^2.
Так вот, нам хочется, чтобы точек было бы как можно больше, а возможных расстояний только два.
Для решения задачи нам придётся знать немного линейной алгебры. Ну, хотя бы первые две главы из книги И.М. Гельфанда "Лекции по линейной алгебре".
Пусть p[1], p[2], .., p[k] - это такие точки, расстояние между которыми может принимать только два значения - a и b.
Рассмотрим многочлены
f[j](x)=(|x-p[j]|^2-a^2)(|x-p[j]|^2-b^2).
Сразу заметим, что f[j](p[j])=a^2b^2, при этом
f[j](p[k])=0, когда p[k] и p[j] различны. Это происходит из-за того, что один из сомножителей равен нулю.
Теперь рассмотрим линейное пространство, натянутое на f[1](x),..., f[k](x).
Наши многочлены линейно независимы. Для этого рассмотрим их линейную комбинацию
alpha[1] f[1](x)+alpha[2] f[2](x)+...+alpha[k] f[k](x).
Пусть alpha[1] f[1](x)+alpha[2] f[2](x)+...+alpha[k] f[k](x)=0. Подставим x=p[j]. Но тогда получается alpha[j] a^2b^2=0, откуда alpha[j]=0.
Таким образом, этих многочленов f[j](x) (и, соответственно, точек p[1], ..., p[k]) не более размерности этого пространства.
Значит, нам надо оценить эту размерность. Для этого введём ещё одну переменную X=x[1]^2+x[2]^2+...+x[d]^2.
Теперь раскроем скобки и поймём, что все слагаемые выражаются через
X^2, X*x[i], X, x[i]*x[j], x[i], 1.
Этих переменных - 1+d+0+d(d+1)/2+d+1=(d^2+5d+4)/2.
Почему в этой сумме появился 0? Да потому что X выражается через переменные x[i]x[j]! Ведь у нас же есть и слагаемые, когда i=j.
Таким образом, базисных элементов не более (d^2+5d+4)/2. Значит, и точек не более (d^2+5d+4)/2.
P.S. Легко понять, что если мы захотим, чтобы наши точки лежали на сфере, то точек будет не более d(d+3)/2.
P.P.S. Мы оценили сверху число точек, между которыми может быть только два разных расстояния. А достигается ли эта оценка? Или хотя бы есть пример, когда точек ненамного меньше?
Ну, эта совсем другая история. И повод написать ещё один пост.