We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \mathbb{N}$)

**edit:** You may assume $D$ is symmetric, and there are zeroes on the main diagonal.

A coordinate $t = (t_1,t_2,\dots,t_{n}) \in \mathbb{N}^n$ is said to be "good" if for all $1 \leq a,b \leq n$: $|t_a - t_b| \leq d(a,b)$

We say that two coordinates are equivalent if one could be obtained from the other by adding a constant to all the entries.

How many "good" coordinates are there, given the matrix D? (We don't count equivalent coordinates twice).

Any idea of how to approach this is highly appreciated.

## Where does this come from?

Given a graph $G=(V,E)$ (simple and undirected), and a subset $T \subseteq V$ we could get "coordinates" for every node in the graph in the following manner:

For every vertex $v \in V$ we define $coord(v) := (dist(v,a))_{a \in T}$. Here $dist$ is the length of the shortest path in the graph.

In the question above, the matrix $D$ is the set of distances ${dist(a,b)}_{a,b \in T}$. It is interesting to know at what point the coordinates space saturates. (Which means that the set $T$ is too small for the set $G$). One way to find out would be to count the amount of possible coordinates, given the triangle inequalities restrictions.

The formulation above does not take into account the requirement for $t_a + t_b \geq d(a,b)$, however it could be obtained by adding a constant to all the entries.

## Example

To make the question more concrete, I include here an example. For the matrix:

```
0 2 1
2 0 1
1 1 0
```

We get the list of solutions:

```
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 2, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(2, 0, 1)
```

A total of 9 solutions.

## Further Progress

I noticed that for a matrix $D$ where $d(i,j) = k$ for $i \neq j$ and $d(i,j)=0$ otherwise we get that the amount of valid coordinates is $(k+1)^n - k^n$.

In the case of $n=3$, If the distances inside $D$ are $a,b,c$, then we could represent them as $a=y+z, b=x+z, c=a+y$, where $x,y,z \geq 0$. This helps us to get rid of the triangle inequalities constraints. Is there an equivalent for cases of $n>4$?