Given $N$ points $X:=(x\_i)\_{i \in \{1,..,N\}}$, we now define a score function $S:X \rightarrow \mathbb{N}$ that is $S(X)= \sum\_{i=1}^N S(x\_i)$ where the score of $S(x\_i)$ is


$$S(x\_i) = 2\* \vert \{x\_j; \vert x\_i-x\_j \vert \in [1,2]\} \vert+ \vert \{x\_j; \vert x\_i-x\_j \vert \in [2,3]\} \vert$$
where $\vert \bullet \vert$ denotes the cardinality of the set. Moreover, we require that for all $i\neq j$ we have $\vert x\_i-x\_j \vert \ge \frac{1}{2}.$


Question: Is it true that any configuration of $N$ points with maximal possible score is in a domain of diameter $c\sqrt{N}$ for some fixed c?



Packing in uniform domains
What follows below is the new answer to the modified question, where we assume in addition $|x\_i-x\_j|\ge 1$ (probably one can ask $|x\_i-x\_j|\ge 1-\varepsilon$ for sufficiently small $\varepsilon$). I want to propose a positive solution of this problem modulo the following guess, which, I hope, is correct.


**Guess.** Consider the equilateral triangular lattice $E$ with distance $1$ between neighbouring points. Then there are exactly $18$ points on distance at most $2$ from a given one, and $36$ on distance at most $3$. So the score of each point is $54=2\*18+(36-18)$. I guess, that for any set $X$ such that any two points are on distance at least $1$, in the punctured $2$-neighbourhood of any point $x\in X$ there are at most $18$ points of $X$. I guess that the same holds for points on distance at most $3$. If this is true then we have the following corollary: for any set $X$ satisfying $|x\_i-x\_j|\ge 1$ we have $S(x\_i)\le 54 $.


So from now on we assume that either the **guess** is correct, or we are working with a set $X$ such that each point of this set has score at most $54$.


I'll prove that under such condition the constant $c$ exists.


*Proof.* Note first of all that we can always construct a set $X$ with $N$ points, such that the score of $X$ is $54N-10^{10}\sqrt{N}$. Such a set can be given by intersecting $E$ with a disk of appropriate radius. (one can take a smaller constant than $10^{10}$, but it doesn't matter).


Assume by contradiction, that we constructed a set $X$ maximising the score and such that its diameter is more than $10^{10^{10}}\sqrt{N}$. Take the union of disks of radius $3$ around all points of $X$, and denote this set by $U\_3$. It is easy to see that $U\_3$ is connected. Indeed, if it is not, we can parallel translate its connected component by pushing one to another and increase this way the score of $X$. So, since the diameter of $X$ is at least $10^{10^{10}}\sqrt{N}$, the perimeter of the exterior boundary of $U\_3$ is at least $10^{10^{10}}\sqrt{N}$. We will say that a point of $X$ contributes to the exterior boundary of $U\_3$ if it is on distance $3$ from it. It is easy to see that the number of points of $X$ contributing to the exterior boundary is at least $10^{(10^{10}-2)}\sqrt{N}$ (because the length of a radius $3$ circle is $<100$). The final observation is that any point $x$ of $X$ that contributes to the boundary has score less than $54$. This is because the disk of radius $3$ around $x$ has a large sub-region, where points of $X$ can not lie (indeed, take a point $y\in \partial U\_3$ on distance $3$ from $x$, then no point on distance less than $3$ from $y$ lies in $X$). Finally, taking into account the **guess** and the fact that the score of $X$ has to be at least $54N-10^{10}\sqrt{N}$, we get a contradiction.


**Old answer**


Let's consider two variations of this question. In both cases the answer is yes. In the first case $X$ is any subset of $\mathbb R^2$ in the second it is a subset of $\mathbb Z^2$.


**1** We assume first that $X$ is any subset of $\mathbb R^2$. In such case the set with maximal possible score has diameter at most $6$. Let me prove this. Let's first construct a set with score approximatively $\frac{5}{3}N^2$. To do this we put $N/6$ points in each vertice of the regular hexagon with side of length $1$.


Now, suppose we have a set with maximal score and suppose its diameter is more than $6$. We will construct a set with larger score which will give us a contradiction.


So, suppose $X$ has two points $x\_i, x\_j$ such that $|x\_i-x\_j|>6$. Let's take two disks of radius $3$ around both points. One of them contains at most $N/2$ points, which means $S(x\_i)$ or $S(x\_j)$ is at most $N$. Without loss of generality assume $S(x\_i)\le N$. On the other hand, we know that $S(X)\ge \frac{5 N^2}{3}$. So, there is a point $x\_k$ such that $S(x\_k)\ge\frac{5}{3}N$. Move $x\_i$ at the place of $x\_k$, this will increase the score $S(X)$. Contradiction.


**2** What follows is just a sketch of proof. We assume $X\subset \mathbb Z^2$. In such case each point $x\_i$ contributes at most $2\*8+20=36$ to the sum $S(X)$. Indeed, there are $8$ integer points on distance at most $2$ from a given one, and $20$ on distance in $[2,3]$. From this one can deduce the answer applying the isomperietric inequality to the set that is the union of $2\times 2$ squares with centres at points of $X$. I can give more details, if you want.


