Дано целое положительное число N. Имеются N³ точек, расположенных в виде кубической решётки N×N×N. Какое наибольшее количество точек из них можно выбрать, чтобы все попарные расстояния между выбранными точками были различны?
Здравствуйте, nikov, Вы писали:
N>Дано целое положительное число N. Имеются N³ точек, расположенных в виде кубической решётки N×N×N. Какое наибольшее количество точек из них можно выбрать, чтобы все попарные расстояния между выбранными точками были различны?
Здравствуйте, nikov, Вы писали:
N>Дано целое положительное число N. Имеются N³ точек, расположенных в виде кубической решётки N×N×N. Какое наибольшее количество точек из них можно выбрать, чтобы все попарные расстояния между выбранными точками были различны?
Честно лень разбираться, поскольку все числа представимы в виде суммы 4х квадратов, то пкм (int)sqrt(pow(N,3) * 3) ты в виде суммы трех представишь. Ну а больше врядли получится.
Здравствуйте, Chorkov, Вы писали:
C>Расстояния евклидовы?
Для чебышёвской метрики — log2(N)+1: точки с x-координатой 2^k-1: 0, 1, 3, 7, 15...
Для манхеттенской — log2(3N)+1: прочертить любую локсодрому от угла до угла (хоть по главной диагонали лесенкой, хоть по рёбрам куба), далее как с Чебышёвым.
Здравствуйте, С3141566=Z, Вы писали:
СZ>Здравствуйте, nikov, Вы писали:
N>>Дано целое положительное число N. Имеются N³ точек, расположенных в виде кубической решётки N×N×N. Какое наибольшее количество точек из них можно выбрать, чтобы все попарные расстояния между выбранными точками были различны? СZ>Честно лень разбираться, поскольку все числа представимы в виде суммы 4х квадратов, то пкм (int)sqrt(pow(N,3) * 3) ты в виде суммы трех представишь. Ну а больше врядли получится.
Продолжаю тему. Вроде бы, число представляется суммой трёх квадратов, если имеет вид 4^s*(4*k+1) или 4^s*(4*k+2).
Если мы можем выбрать M точек. То имеется M * (M — 1) / 2 расстояний между ними. То есть нам надо понять сколько чисел вида 4^s*(4*k+1) и 4^s*(4*k+2) в отрезке [1, 3*N^2]. Допустим K. Потом решить M *(M — 1) /2 <= K.
Но некоторые из найденных решений могут иметь координаты вне куба NxNxN. Наверное, нужно зайти с другой стороны.
FH>Здравствуйте, С3141566=Z, Вы писали:
СZ>>Здравствуйте, nikov, Вы писали:
N>>>Дано целое положительное число N. Имеются N³ точек, расположенных в виде кубической решётки N×N×N. Какое наибольшее количество точек из них можно выбрать, чтобы все попарные расстояния между выбранными точками были различны? СZ>>Честно лень разбираться, поскольку все числа представимы в виде суммы 4х квадратов, то пкм (int)sqrt(pow(N,3) * 3) ты в виде суммы трех представишь. Ну а больше врядли получится.
FH>Продолжаю тему. Вроде бы, число представляется суммой трёх квадратов, если имеет вид 4^s*(4*k+1) или 4^s*(4*k+2). FH>Если мы можем выбрать M точек. То имеется M * (M — 1) / 2 расстояний между ними. То есть нам надо понять сколько чисел вида 4^s*(4*k+1) и 4^s*(4*k+2) в отрезке [1, 3*N^2]. Допустим K. Потом решить M *(M — 1) /2 <= K.
FH>Но некоторые из найденных решений могут иметь координаты вне куба NxNxN. Наверное, нужно зайти с другой стороны.
Ошибся. Число представляется суммой трёх квадратов всегда, за исключением случаев 4^s*(8*k-1). Но это не так уж важно.
Всё равно больше, чем sqrt(6)*N точек мы выбрать не можем. Если использовать аргументы отсюда (https://www.renyi.hu/~p_erdos/1970-03.pdf), то на вскидку можем выбрать N^(1-epsilon).
Я написал программу. Для малых N видимо имеем N+2. Но точно я не могу это доказать.
Интересно было выяснить, нет ли возможности получать точки рекурсией F(x,y,z)=(R1(x,y,z) mod N,R2(x,y,z) mod N,R3(x,y,z) mod N), где R — рациональная функция. Или получать их как рациональные точки эллиптической кривой.
Перекуём баги на фичи!
