"Радарная" точка минимальной нормы

[slavav]

Дан куб целочисленных точек $[0, 100] \times [0, 100] \times [0, 100]$. Точку $p$ с неотрицательнными целыми координатами назовём радарной если все расстояния от $p$ до точек куба различны.

Отыскать радарную точку минимальной нормы.

Я умею находить радарные точки но не умею найти радарную точку минимальной нормы. Какие есть подходы к задаче?

[ozheredov]

slavav

Перебрать $101 \times 101 \times 101$ точку и выбрать, какая нравится, что мешает? )

Или она еще вне куба может быть?

[slavav]

ozheredov в сообщении #1563936 писал(а):

Или она еще вне куба может быть?

Она точно вне куба. Любая точка внутри куба имеет от трёх до шести соседок на единичном расстоянии. Пример радарной точки $(100, 5100, 510100)$.

[ozheredov]

slavav
А, потому что если внутри, то точки в минимально-связной кубической окрестности равноудалены. Понял.

[waxtep]

slavav в сообщении #1563938 писал(а):

Пример радарной точки $(100, 5100, 510100)$.

Кажется, можно чуть поближе: $(100,5100=100\cdot(100-49),505100=100\cdot(5100-49))$

-- 02.09.2022, 00:26 --

Это исходя из логики, что минимальная разница в квадратах расстояния вдоль одной оси строго больше максимальной вдоль другой:

$$\underset{\substack{s_{1,2}\in\mathbb{N}\\0\leqslant s_1<s_2\leqslant100}}\min{(A-s_1)^2-(A-s_2)^2}>\underset{\substack{t_{1,2}\in\mathbb{N}\\0\leqslant t_1<t_2\leqslant100}}\max{(B-t_1)^2-(B-t_2)^2}$$

Минимум/максимум достигаются при $s_1=99,s_2=100,t_1=0,t_2=100$, что дает $A\geqslant100(B-49)$ для каких-либо двух координат радарной точки $A,B$

[waxtep]

А нет, надо же аккуратнее: $2A-199>100\cdot(2\cdot5100-100)+100\cdot(2\cdot100-100)$, так что получил ту же точку $(100,5100,510100)$

[waxtep]

Трудно назвать это подходом, скорее наблюдение: написал на PARI/GP примитивную проверялку радарности точки и пытался долго и изобретательно скакать, как вблизи приведенной в пример точки, так и вдали от нее. Железной рукой оно ведет к указанной точке, как ни скачи. slavav, а Вам удалось найти радарную точку меньшей нормы?

Проверялка (подсчитывает количество совпадающих расстояний):

radar_check(A,B,C,S)={r2=vector((S+1)^3); for(x=0,S,for(y=0,S,for(z=0,S,r2[(x+1)+y*(S+1)+z*(S+1)^2]=x^2+y^2+z^2-2*(A*x+B*y+C*z)))); r2=vecsort(r2,,8); return((S+1)^3-#r2)};

Точка $(A,B,C)$ радарна для куба $[0,S]^3$ если она возвращает $0$

[slavav]

Точку меньшей нормы я никогда не видел. Делал два вида поиска: случайный в кубе размера 10_000_000. В нём много радарных точек. Второй поиск - лексикографический - решается одномерная задача, с её решением решается двумерная, в её решением решается трёхмерная. Результат - $(100, 5100, 510100)$ - лексикографически наименьшая.

Случайный поиск в кубе размера 1_000_000 очень редко даёт радарные точки. Радарных точек со всеми координатами меньше 500_000 не видел ни одной.

Идеи: 1) диофантова задача, должна быть какая-то теория рядом. 2) полный перебор на двумерной задаче может подсказать что-то о структуре радарных точек. 3) полный перебор на кубе меньшего размера.

[waxtep]

Для куба $[0,S]^3$ при малых нечетных $S$ оценка сверху квадрата минимальной нормы $R^2_{est}$, соответствующая точке $\left(S,\lceil{\frac12((S+1)^2-1)\rceil},S\cdot\lceil{\frac12((S+1)^2+1)}\rceil\right)$, не является точной, можно чуть лучше (формат $(A,B,C)\rightarrow R^2$ для истинного минимума и для оценочного):

$$\begin{tabular}{c|l|l|c} S&\min&est&$(R_{est}-R_{\min})/R_{\min},\%$\\ \hline 3&(4,7,26)\rightarrow741&(3,8,27)\rightarrow802&4,0\%\\ \hline 5&(11, 16, 93)\rightarrow9026&(5, 18, 95)\rightarrow9374&1,9\%\\ \hline 7&(28, 35, 228)\rightarrow53993&(7, 32, 231)\rightarrow54434&0,4\% \end{tabular}$$

Наибольшая координата в истинном минимуме чуть смещена вниз, а наименьшая существенно задрана вверх; относительная разница между минимумом нормы и его оценкой быстро падает. Для малых четных $S$ оценка неулучшаема, приходим в предсказанную точку. Чтобы дальше это таким образом изучать, видимо нужно поинтеллектуальнее напрограммировать, сейчас моя полнопереборная поделка уже для $S=8$ работает безобразно долго:

radar_search(S)={A0=S; B0=ceil(((S+1)^2-1)/2); C0=S*ceil(((S+1)^2+1)/2); R02=A0^2+B0^2+C0^2; t=[A0,B0,C0,R02]; p=vector(4,i,R02+1); for(A=S,floor(sqrt(p[4]/3)),for(B=A,floor(sqrt((p[4]-A^2)/2)),for(C=B,floor(sqrt(p[4]-A^2-B^2)),if(A^2+B^2+C^2<p[4],if(radar_check(A,B,C,S)==0,p=[A,B,C,A^2+B^2+C^2]))))); return([p; t])};

[waxtep]

Для $S=9$:

$$\begin{tabular}{c|l|l|c} S&\min&est&$(R_{est}-R_{\min})/R_{\min},\%$\\ \hline 9&(45,54,455)\rightarrow211966&(9, 50, 459)\rightarrow213262&0,3\%\\ \end{tabular}$$

Можно подметить, что $C_{\min}=C_{est}-\frac12(S-1),A_{\min}=B_{\min}-S$

[waxtep]

slavav в сообщении #1564025 писал(а):

1) диофантова задача, должна быть какая-то теория рядом.

Попробовал этот путь для квадрата $[0,S]^2$, удалось вот к такому прийти: точка $(X,Y): X,Y\in\mathbb{N},Y\geqslant X\geqslant S$ не является радарной, если

$$-\alpha S+\alpha\left\lceil\frac{\alpha}2\right\rceil+\beta\left\lceil\frac{\beta}2\right\rceil\leqslant\beta Y-\alpha X\leqslant\beta S-\alpha\left\lceil\frac{\alpha}2\right\rceil-\beta\left\lceil\frac{\beta}2\right\rceil$$

для каких-либо $\alpha,\beta\in\mathbb{N}:S\geqslant\alpha\geqslant\beta\geqslant1,\gcd(\alpha,\beta)=1$. Такие полосочки вокруг прямых, вначале идут густо и покрывают всё, а на некотором отдалении уже перестают конечно справляться, и появляются радарные точки. Гипотеза, что минимум нормы радарной точки для четного $S$ достигается при $\alpha=S,\beta=1$ в точке $(S,S^2/2+S)$.

[waxtep]

waxtep в сообщении #1564352 писал(а):

Гипотеза, что минимум нормы радарной точки для четного $S$ достигается при $\alpha=S,\beta=1$ в точке $(S,S^2/2+S)$.

Идея доказательства, которую хотелось бы попробовать реализовать:
1. Для полоски "антирадарных" точек вокруг прямой с данным наклоном $\alpha_1/\beta_1$ мы знаем "соседнюю справа" полоску вокруг прямой с (минимальным превышающим $\alpha_1/\beta_1$) наклоном $\alpha_2/\beta_2$;
2. И можем найти радарную точку минимальной нормы в секторе между нижней границей первой полоски и верхней границей второй;
3. Затем среди этих точек для всех возможных $\alpha_1/\beta_1$ находим самую скромную.

В пп.1, 2 возможны затруднения, поскольку а) требуется упорядочить несократимые дроби и б) вблизи начала координат несколько полосок могут накладываться, и найденная в секторе радарная точка может оказаться антирадарной из-за накрытия "несоседней" полоской. Ну, тут пока не проделаешь, - не поймешь

[waxtep]

waxtep в сообщении #1564352 писал(а):

точка $(X,Y): X,Y\in\mathbb{N},Y\geqslant X\geqslant S$ не является радарной, если

$$-\alpha S+\alpha\left\lceil\frac{\alpha}2\right\rceil+\beta\left\lceil\frac{\beta}2\right\rceil\leqslant\beta Y-\alpha X\leqslant\beta S-\alpha\left\lceil\frac{\alpha}2\right\rceil-\beta\left\lceil\frac{\beta}2\right\rceil$$

Это неверно, правильно так: точка $(X,Y): X,Y\in\mathbb{N},Y\geqslant X\geqslant S$ не является радарной, если

$$-\alpha S+\frac{\alpha^2+\beta^2}{1+\kappa}\leqslant\beta Y-\alpha X\leqslant\beta S-\frac{\alpha^2+\beta^2}{1+\kappa}$$

для каких-либо $\alpha,\beta\in\mathbb{N}:\dfrac{S}{2-\kappa}\geqslant\alpha\geqslant\beta\geqslant1,\gcd(\alpha,\beta)=1$, где $\kappa\equiv[2|(\alpha-\beta)]$ - индикатор одинаковой четности $\alpha$ и $\beta$. Все равно полоски, но более хитрой структуры: для $\alpha,\beta$ разной четности (т.е. если в точности одно из $\alpha,\beta$ - четное, поскольку они взаимно просты), полоски более узкие, и их наклон не может быть чересчур большим.