Given $\alpha>0$, consider the following system of linear equations of variable $x=(x_1,\cdots,x_n)$ where $x\in\mathbb{R}^n\backslash x_0$. The $x_0$ denotes vectors that all elements are equal. There are $n(n-1)/2$ number of equations in the system.
$$|x_i-x_j|=\alpha, \ \forall i,j \in \{1,\cdots,n\}, i<j$$
We can see that there exist no solution satisfying all equations. Take $n=3$ as example. Without loss of generality, set $x_1=0$. Then in order to satisfy $|x_1-x_2|=\alpha$ we have $x_2=-\alpha,\text{ or }\alpha$. Wlog consider $x_2=\alpha$, in order to satisfy $|x_2-x_3|=\alpha$, then $x_3$ can be either $0$ or $\alpha$. But these two cases violate $|x_1-x_3|=\alpha$ or $|x_2-x_3|=\alpha$, respectively.
My question is, for general $n$, what is the maximal and minimum number of equations can be satisfied?
If this problem is np-hard, could we expect that considering some special graph structure such that the problem can be solved? i.e. consider
$$a_{ij}|x_i-x_j|=\alpha, \ \forall i,j \in \{1,\cdots,n\}, i<j$$
For the minimum, since we can't just have all the starting values the same, we can just set them all to different powers of $2$: any pair of powers of $2$ gives a different difference from any other pair, so no possible value of alpha can give a result of more than one satisfied equation.
As for the maximum, the value of $\alpha$ doesn't matter, so I'll make it $1$.
Assuming $x_i \in \mathbb R$, the maximum should be
$$\left\lfloor \frac{n}{2}\right\rfloor\left\lfloor \frac{n + 1}{2} \right\rfloor = \left\lfloor\frac{n^2}{4}\right\rfloor$$
Take half the $x_i$ values and make them $0$, and then take the other half and make them $1$.
Why? Each thing can only connect to things that are $1$ above or below it, which means they're of different parity, so we have a bipartite graph: only equations that pair even and odd values of $x$ can possibly be satisfied.
If we want to maximize this, we need a complete bipartite graph, so the values all have to be close enough to each other: a distance of at most $1$ between members of the two classes. This limits us to having only one value for one class, and just the two surrounding values for the other class, though we can pick just one of the two if we want.
This gives us $a(n-a)$ matches, where $a$ is number of $x$ values in the first class. Now, we must maximize this by varying $a$, which will happen when $a$ and $n-a$ are as close together as they can be, which is when $a = \lfloor n/2\rfloor$.
This gives the sequence A002620: $0, 1, 2, 4, 6, 9, 12, 16,\dots$ for $n = 1,2,\dots$
If $x_i \in \mathbb C$ or $x_i \in \mathbb R^2$, when we can divide them as evenly as possible into three classes by placing them on corners of a triangle, giving $0,1,3,5,8,12,16,21,27,\dots$ A000212, and in higher dimensions we can similarly use matching simplices: it's $0,1,3,6,9,13,18,24,30,37,\dots$ A033436 for three dimensions.
Looking through these, these are the edge counts of the Turán graph of appropriate size, which makes sense because this is kind of what they're for...