Explanation of formula for distance between triangles in a triangular grid

Question

Lets say you have a triangle similar to the one below, with each triangle numbered $(N, i) $ where $N$ is the row number and $i$ is the position within the row.

From any triangle, you are allowed to move to any triangle which shares an edge with her current triangle. This can be seen in the diagram:

As an example, it takes 3 moves to get from (3, 3) to (2, 2).

---

How would you find a formula to find the number of moves it takes to get from a triangle specified by the coordinates $(a_i, a_j)$ to another triangle specified by coordinates $(b_i, b_j)$?

When looking for a solution to this problem online I found this monstrous formula:

$$\left| a_{i}-b_{i} \right|\; +\; \left| \left( a_{i}-\left\lfloor \frac{a_{j}}{2} \right\rfloor \right)-\left( b_{i}-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right) \right|\; +\; \left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}+1}{2} \right\rfloor \right|$$

but I have no idea how they came up with this. I believe this is some variant of taxicab/manhatan geometry except with triangle instead of rectangles.

Could someone please try to explain/prove why this formula is valid?

---

I believe that the first addend, $|a_i - b_i|$ comes from the observation that to get from any triangle $(a_i, a_j)$ to $(b_i, b_j)$ you must make $|a_i - b_i|$ moves downward (or upward depending on the order). The other two addends combined seem to give the number of moves left/right (depending on the position), but I cannot figure out the intuition/logic behind why it works.

Answer 1

Consider a triangle labeled $(i,j)$ somewhere deep in the larger triangle. The triangle $(i,j)$ is connected to $(i,j-1),$ $(i,j+1),$ and exactly one other triangle: $(i+1,j+1)$ if $j$ is odd, $(i-1,j-1)$ if $j$ is even.

Already this is getting trickier than ordinary Manhattan/taxicab distance, because different locations have links in different directions. We can simplify things a bit by considering only even values of $j$ at first; this means we must make an even number of moves, since any single move changes $j$ from even to odd or odd to even. The nice thing about this is that if you do two moves starting at $(i,j)$ where $j$ is even, you end up at one of the following six places: $(i-1,j-2),$ $(i-1,j),$ $(i,j-2),$ $(i,j+2),$ $(i+1,j),$ or $(i+1,j+2).$ And since you wind up at a triangle whose second coordinate is even, you can repeat any sequence of the same set of moves. (We can consider how to deal with odd values of $j$ later.)

Now let's consider a minimal sequence of moves from $(a_i,a_j)$ to $(b_i,b_j),$ where $a_i \le b_i.$ If $a_j \le b_j \le a_j + 2(b_i - a_i),$ then we can build such a sequence from $b_i - a_i$ pairs of moves such that each pair of moves takes some $(i,j)$ to either $(i+1,j)$ or $(i+1,j+2).$ But if $b_j < a_j$ then we must use $b_i - a_i$ pairs of moves that take some $(i,j)$ to $(i+1,j)$ and some additional pairs of moves that take $(i,j)$ to $(i,j-2),$ while if $b_j > a_j + 2(b_i - a_i)$ we must use $b_i - a_i$ pairs of moves from $(i,j)$ to $(i+1,j+2)$ and additional moves from $(i,j)$ to $(i,j+2).$ Note that only the number of moves in each direction matters, not the exact sequence of the moves.

Now we have the beginning of a formula for the "distance" between two triangles, although we are restricted at this time to even values of $a_j$ and $b_j$ and to the case $a_i < b_i.$ We could write the number of moves this way: $$ d((a_i,a_j),(b_i,b_j)) = \begin{cases} 2|b_i - a_i| + |b_j - a_j| & \mbox{if } b_j < a_j, \\ 2|b_i - a_i| & \mbox{if } a_j \le b_j \le a_j + 2(b_i - a_i), \\ 2|b_i - a_i| + |b_j - (a_j + 2(b_i - a_i))| & \mbox{if } b_j > a_j + 2(b_i - a_i). \end{cases} $$ So this is a function that looks like an absolute value function except for the constant part between $a_j$ and $a_j + 2(b_i - a_i).$ A function like that can be defined by adding a constant to the arithmetic mean of two absolute value functions. (Try graphing $f(x) = n + \frac 12(|x-p|+|x-q|)$ to see how this works.) It turns out that we can rewrite our "distance" function (with the same restrictions as before) like this: $$\begin{eqnarray} d((a_i,a_j),(b_i,b_j)) & = & |b_i - a_i| + \frac 12 \left(|b_j - a_j| + |b_j - (a_j + 2(b_i - a_i))|\right) \\ & = & |b_i - a_i| + \left|\frac{b_j}{2} - \frac{a_j}{2}\right| + \left|\left(\frac{b_j}{2} - b_i\right) - \left(\frac{a_j}{2} - a_i\right)\right| \\ & = & |a_i - b_i| + \left|\left(a_i - \frac{a_j}{2}\right) - \left(b_i - \frac{b_j}{2}\right)\right| + \left|\frac{b_j}{2} - \frac{a_j}{2}\right|. \end{eqnarray}$$ The first line of this sequence of equations comes from the observation that the function looks like the arithmetic mean of two absolute values plus a constant (the constant turns out to be $|b_i - a_i|$), and the next two lines come from distributing the factor of $\frac 12$ and rearranging terms. The result looks a lot like the "monstrous" formula except that it does not use the "floor" function and never adds $1$ to either $a_j$ or $b_j.$

Now we may notice something interesting: if we simply rename our two triangles so that the triangle formerly labeled $(a_i,a_j)$ is now labeled $(b_i,b_j)$ and the former $(b_i,b_j)$ is now $(a_i,a_j),$ we can evaluate the "distance" between the triangles using the same formula except that $a_i$ and $b_i$ are swapped and $a_j$ and $b_j$ are swapped; but when we do that, each of the three absolute values remains the same. So our formula, which we developed for the case $a_i \le b_i,$ works just as well for $b_i \le a_i,$ and we can therefore dispense with the restriction $a_i \le b_i,$ and have only the restriction that $a_j$ and $b_j$ are even.

It is easy to confirm that when $a_j$ and $b_j$ are both even, the "monstrous" formula is exactly equal to the formula for $d((a_i,a_j),(b_i,b_j))$ written above. It remains only to see what happens when either $a_j$ or $b_j$ (or both) can be odd. We can do this by seeing what happens to the number of moves if we add $1$ to $a_j,$ to $b_j,$ or to both. Generally, adding $1$ to just one of the $j$ coordinates either increases or decreases the number of moves by $1$, while a symmetry argument shows that adding $1$ to both $a_j$ and $b_j$ leaves the number of moves unchanged. Further investigation shows that when we add $1$ to just one $j$ coordinate, the number of moves decreases if this change brings $a_j$ and $b_j$ closer together, but increases if $a_j$ and $b_j$ become further apart.

Now we observe that if when $a_j$ is even, we can replace $\frac{a_j}{2}$ with either $\left\lfloor\frac{a_j}{2}\right\rfloor$ or $\left\lfloor\frac{a_j+1}{2}\right\rfloor$ without changing the value of the formula, but if $a_j$ is odd, then $\left\lfloor\frac{a_j+1}{2}\right\rfloor = \left\lfloor\frac{a_j}{2}\right\rfloor + 1.$ Something similar happens with $b_j.$ So we can replace $\frac{a_j}{2}$ with $\left\lfloor\frac{a_j}{2}\right\rfloor$ in places where we want to have no effect from adding $1$ to $a_j,$ but $\left\lfloor\frac{a_j+1}{2}\right\rfloor$ in places where we want to insert an extra term of $1$ when adding $1$ to $a_j,$ and a similar tactic applies to $\frac{b_j}{2}.$ By examination (and trial and error if necessary) we can confirm that we want to make exactly the changes that are shown in the "monstrous" formula.

Having derived the formula in such a manner, one would be well advised to attempt a more formal proof such as the one devised by Bilou06, to ensure there are no false assumptions or other errors in the derivation.

It seems to me the "monstrous" formula is about as neat as a formula for this "distance" can get. The apparent complexity of the formula arises from the complexity of the way our scheme for numbering the triangles interacts with the way the triangles are connected--which is to say, not very neatly. (Note that the two "axes" are treated very differently, and there is all that odd-even nonsense governing who is connected to whom.) Contrast this with Manhattan (taxicab) distance, where the way we number the grid points goes practically hand-in-hand with the way we measure the distance; that's why the Manhattan distance formula is so much simpler.

Answer 2

The formula is True if the distance $d(a,b)= 0$.

Let's say it is True for any distance $<n$.

If you have to 2 points a,b and $d(a,b)=n+1$ with $a_i\geq b_i$

If $b_j$ is odd, t least one of the 3 is True:

• $d(a, (b_i, b_j-1)) = n$
• $d(a, (b_i, b_j+1)) = n$
• $d(a, (b_i+1, b_j)) = n$

can see graphically that

• $d(a, (b_i+1, b_j)) > d(a,b)$ using $a_i\geq b_i$
• $d(a, (b_i, b_j+1)) \geq d(a, (b_i, b_j-1))$ if $a_j+1\geq b_j$

So, with the 2 assumptions, $d(a,b) = d(a, (b_i, b_j-1))+1$:

$$d(a,b) = \left| a_{i}-b_{i} \right|\; +\; \left| \left( a_{i}-\left\lfloor \frac{a_{j}}{2} \right\rfloor \right)-\left( b_{i}-\left\lfloor \frac{b_{j}-1}{2} \right\rfloor \right) \right|\; +\; \left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right|+1$$

• $b_j$ is odd so $\left\lfloor \frac{b_{j}-1}{2} \right\rfloor = \left\lfloor \frac{b_{j}}{2} \right\rfloor$
• $a_j+1\geq b_j$ so $\left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right|+1 = \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor +1 = \left|\left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}+1}{2} \right\rfloor \right|$

and so the formula is True for $a_i\geq b_i$ and $b_j$ odd. I claim you can do the same with $b_j$ even and use symmetry to close the case

Answer 3

Here's an alternative approach to find a distance formula between two points in this triangle. It's based upon two ideas:

• Symmetries: There are many symmetry patterns and we could try to use some of them. In order to do so we transform the coordinates.

• Walk along pathes: We find a distance formula by developing pathes of minimum length between points.

We start with:

Coordinate Transformation: Let \begin{align*} P^{\star}=\binom{a_1}{a_2}\qquad\qquad a_1\geq 1, 1 \leq a_2 \leq 2a_1-1\\ Q^{\star}=\binom{b_1}{b_2}\qquad\qquad b_1\geq 1, 1 \leq b_2 \leq 2b_1-1\\ \end{align*} We want to find a distance formula $d(P^\star,Q^\star)$ according to the specific geometry in the triangle as described in the question above. In order to do so, we change the coordinates to get a triangle with the following shape: $$ \begin{array}{ccccccc} &&&(0,0)&&&\\ &&(1,-1)&(1,0)&(1,1)&&\\ &(2,-2)&(2,-1)&(2,0)&(2,1)&(2,2)&\\ (3,-3)&(3,-2)&(3,-1)&(3,0)&(3,1)&(3,2)&(3,3)\qquad\qquad(1)\\ \end{array} $$

Therefore we transform $P^\star,Q^\star$ into points $P,Q$ using the transformation \begin{align*} P^\star=\binom{a_1}{a_2}\quad\rightarrow\quad&P=\binom{x_1}{y_1}=\binom{a_1-1}{a_2-a_1}\qquad x_1\geq 0, -x_1\leq y_1 \leq x_1\\ Q^\star=\binom{b_1}{b_2}\quad\rightarrow\quad&Q=\binom{x_2}{y_2}=\binom{b_1-1}{b_2-b_1}\qquad y_1\geq 0, -x_2\leq y_2 \leq x_2\\ \end{align*}

We observe: The transformation does a shift by one in $x$-direction and the $y$-coordinates are centered by subtracting the $x$-value from the $y$-value.

Now we can use some symmetry properties to declare without loss of generality:

• We may assume: $x_1 \leq x_2$, since $d(P,Q)=d(Q,P)$

• We may assume: $y_1 \leq y_2$, since $d\left(\binom{x_1}{y_1},\binom{x_2}{y_2}\right)=d\left(\binom{x_1}{-y_1},\binom{x_2}{-y_2}\right)$

The first assumption is valid, since the metric $d$ is symmetric. In other words, the length of a minimal path walk from $P$ to $Q$ is the same as walking the path back from $Q$ to $P$. Furthermore pathes may be reflected at the $x$-axis without changing the length, so the second assumption is valid.

Note: This second symmetry property would look more complicated if we would have used $P^\star,Q^\star$ instead.

Walk along pathes: One step approach

Let $P=\binom{x_1}{y_1},Q=\binom{x_2}{y_2}$. Under the assumption $x_1 \leq x_2$ and $y_1 \leq y_2$ we consider how a path from $P$ to $Q$ with minimum length can be constructed. Let's assume we are at position $M=(x_M,y_M)$ on the path and we want to specify the next step. \begin{align*} P=\binom{x_1}{y_1}\quad\longrightarrow\quad M=\binom{x_M}{y_M}\quad\longrightarrow\quad Q=\binom{x_2}{y_2} \end{align*} The basic idea of the one step strategy is:

• As long as $x_M < x_2$ and $y_M < y_2$ we go a step in $x$-direction if possible, otherwise we go a step in $y$-direction. The direction we have to choose depends on the geometry of the small triangles around each point.

• We can proceed this way until either $x_M = x_2$ or $y_M = y_2$. Then we proceed as follows:

• In the case $x_M=x_2$ we can simply walk step by step horizontally in $y$-direction until we have reached the point $Q$. In the case $y_M=y_2$ we have to go in $x$-direction to $Q$ by carefully considering the geometry of the triangles around each point.

Now the details: We have to consider four cases:

\begin{align*} &x_M < x_2, y_M<y_2\qquad\qquad \begin{cases} x_M \rightarrow x_M+1\qquad\qquad x_M+y_M\equiv0(2)\\ y_M \rightarrow y_M+1\qquad\qquad x_M+y_M\equiv1(2)\\ \end{cases}\tag{2}\\ &x_M = x_2, y_M<y_2\qquad\qquad y_M\rightarrow y_M+1\tag{3}\\ &x_M < x_2, y_M=y_2\qquad\qquad \begin{cases} x_M \rightarrow x_M+1\qquad\qquad x_M+y_M\equiv0(2)\\ y_M \rightarrow y_M-1\qquad\qquad x_M+y_M\equiv1(2)\\ \end{cases}\tag{4}\\ &x_M = x_2, y_M=y_2\qquad\qquad M=Q;\text{ finished}\tag{5}\\ \end{align*}

So, when starting from $P$ we proceed with step (2) as long as possible until we have either the situation (3) or the situation (4). These two cases will now be analysed in the next section special cases.

Note: Observe, that we walk in (4) one step to the left in case of odd $x_M+y_M$. So we stay at the minimum path and we have the situation, that $y_M-1 < y_2$. Therefore we can use one of the specified cases again.

Special cases $x_M=x_2$ resp. $y_M=y_2$

Here we assume, that we have either reached the same row as $Q$ ($x_M=x_2$) or the same column as $Q$ ($y_M=y_2$). In the first case it's easy, since we can go horizontally $y_2-y_M$ steps. In the other case we have to consider the geometry of the triangle, i.e. the parity of the $x$ and $y$-coordinates:

In case $x_M+y_M$ is even, we observe we need $$1,4,5,8,9,12,\ldots$$ steps when increasing the $x$-difference between $M$ and $Q$ and similarly we need $$3,4,7,8,11,\ldots$$ steps in case $x_M+y_M$ is odd.

Detailed description: We again assume the situation $M=\binom{x_M}{y_M}$ and $Q=\binom{x_2}{y_2}$.

The case: $x_M=x_2$ \begin{align*} d(M,Q)=y_2-y_M\tag{6} \end{align*}

The case: $y_M=y_2$ \begin{align*} \begin{array}{rll} x_M+y_M\equiv0(2),x_M+x_2\equiv1(2)&\rightarrow 1,5,9,\ldots &d(M,Q)=2(x_2-x_M)-1\\ x_M+x_2\equiv0(2)&\rightarrow 4,8,12,\ldots &d(M,Q)=2(x_2-x_M)\\ x_M+y_M\equiv1(2),x_M+x_2\equiv1(2)&\rightarrow 3,7,11,\ldots &d(M,Q)=2(x_2-x_M)+1\\ x_M+x_2\equiv0(2)&\rightarrow 4,8,12,\ldots &d(M,Q)=2(x_2-x_M)\\ \end{array}\tag{7} \end{align*}

Let's go on with the general case. Here we have to distinguish which situation occurs after we have processed the steps in (2) as often as possible.

General Case:

The situation $x_2-x_1\leq y_2-y_1$:

Here we can walk $x_2-x_1$ steps in $x$-direction and $x_2-x_1$ steps in $y$-direction. Then we reach the same row as $Q$ and we can simply walk horizontally step by step till we have reached $Q$ according to (6).

The situation $x_2-x_1 > y_2-y_1$:

Here we can walk $y_2-y_1$ steps in $x$-direction and $y_2-y_1$ steps in $x$-direction. Then we reach the same column as $Q$ and we can walk vertically step by step till we have reached $Q$. We have thereby to respect the geometry according to (7).

Note: In case of equal $x_2-x_1=y_2-y_1$ both situations coincide and have therefore to show the same results.

And now the gory details: We again assume $P=\binom{x_1}{y_1},M=\binom{x_M}{y_M}$ and $Q=\binom{x_2}{y_2}$.

The case $x_2-x_1 \leq y_2-y_1$: \begin{align*} d(P,Q)&=d(P,M)+d(M,Q)\\ &=2(x_2-x_1)+d\left(\binom{x_1+(x_2-x_1)}{y_1+(x_2-x_1)},\binom{x_2}{y_2}\right)\tag{8}\\ &=2(x_2-x_1)+d\left(\binom{x_2}{y_1+x_2-x_1},\binom{x_2}{y_2}\right)\\ &=2(x_2-x_1)+y_2-(y_1+x_2-x_1)\tag{9}\\ &=x_2-x_1+y_2-y_1 \end{align*}

Observe that (8) reflects the fact that in this case we can walk $x_2-x_1$ steps in $x$-direction and $x_2-x_1$ steps in $y$-direction by consecutively applying $2(x_2-x_1)$ times rule (2). In (9) we have the situation according to (6).

The other case:

The case $x_2-x_1 > y_2-y_1$:

\begin{align*} d(P,Q)&=d(P,M)+d(M,Q)\\ &=2(y_2-y_1)+d\left(\binom{x_1+(y_2-y_1)}{y_1+(y_2-y_1)},\binom{x_2}{y_2}\right)\tag{10}\\ &=2(y_2-y_1)+d\left(\binom{x_1+y_2-y_1}{y_2},\binom{x_2}{y_2}\right) \end{align*} Observe that (10) reflects the fact that in this case we can walk $y_2-y_1$ steps in $x$-direction and $y_2-y_1$ steps in $y$-direction by consecutively applying $2(y_2-y_1)$ times rule (2).

In order to respect the geometry when walking vertically from $M$ to $Q$ we have to consider the parity of $x_M+y_M$ and $x_M+x_2$ according to (7):

\begin{align*} \begin{array}{rrl} x_M+y_M\equiv0(2),x_M+x_2\equiv1(2)&d(P,Q)&=2(y_2-y_1)+2(x_2-x_M)-1\\ &&=2(y_2-y_1)+2(x_2-x_1-y_2+y_1)-1\\ &&=2(x_2-x_1)-1\\ x_M+x_2\equiv0(2)&d(P,Q)&=2(y_2-y_1)+2(x_2-x_M)\\ &&=2(y_2-y_1)+2(x_2-x_1-y_2+y_1)\\ &&=2(x_2-x_1)\\ x_M+y_M\equiv1(2),x_M+x_2\equiv1(2)&d(P,Q)&=2(y_2-y_1)+2(x_2-x_M)+1\\ &&=2(y_2-y_1)+2(x_2-x_1-y_2+y_1)+1\\ &&=2(x_2-x_1)+1\\ x_M+x_2\equiv0(2)&d(P,Q)&=2(y_2-y_1)+2(x_2-x_M)\\ &&=2(y_2-y_1)+2(x_2-x_1-y_2+y_1)\\ &&=2(x_2-x_1)\\ \end{array} \end{align*}

Finally a

Summary:

Let's assume a transformed triangle starting with $(0,0)$ and centered around the vertical $x$-axis with coordinates according to (1). Let $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ be points within this triangle. \begin{align*} P=\binom{x_1}{y_1}\qquad\qquad x_1\geq 0, -x_1\leq y_1 \leq x_1\\ Q=\binom{x_2}{y_2}\qquad\qquad x_2\geq 0, -x_2\leq y_2 \leq x_2 \end{align*} We may assume without loss of generality that \begin{align*} x_1&\leq x_2\\ y_1&\leq y_2 \end{align*}

This is due to the symmetry of the distance function $d$ and the symmetry of the vertical $x$-axis.

The distance $d(P,Q)$ fulfils:

Case $x_2-x_1 \leq y_2-y_1$: \begin{align*} d(P,Q) &= x_2-x_1+y_2-y_1\qquad\qquad x_2-x_1 \leq y_2-y_1\\ \end{align*} Case $x_2-x_1 > y_2-y_1$: \begin{align*} d(P,Q) &=\begin{cases} 2(x_2-x_1)-1&\qquad\qquad x_1+y_1\equiv0(2),x_2+y_2\equiv1(2)\\ 2(x_2-x_1)+1&\qquad\qquad x_1+y_1\equiv1(2),x_2+y_2\equiv0(2)\\ 2(x_2-x_1)&\qquad\qquad\text{otherwise}\\ \end{cases} \end{align*}

Note: Observe that in the result in case $x_2-x_1 > y_2-y_1$ no steps in $y$-direction occur. This is due to the fact that we have to walk first $(x_2-x_1)$ steps in $x$-direction as well as in $y$-direction till we have reached the same column as $Q$. So we can simply count $(x_2-x_1)$ twice. Furthermore when we proceed to go vertically in $x$-direction we see, that for each two steps in $y$-direction we also have to make two steps in $x$-direction. That's why we can again simply count the steps in $x$-direction twice. In case of different parity between $x_1+y_1$ and $x_2+y_2$ we have to adjust by $\pm1$.

Additional Note: Number of minimal pathes

Related with the length of minimal pathes is the number of minimal pathes from $P$ to $Q$. A striking constellation of two interleaved Pascal triangles can be seen when we look at the number of minimal pathes from $(0,0)$ to $(x,y)$.

$$ \begin{array}{ccccccccccccc} &&&&&&{\color{blue}{1}}&&&&&&\\ &&&&&{\color{blue}{1}}&1&{\color{blue}{1}}&&&&&\\ &&&&{\color{blue}{1}}&1&{\color{blue}{2}}&1&{\color{blue}{1}}&&&&\\ &&&{\color{blue}{1}}&1&{\color{blue}{3}}&2&{\color{blue}{3}}&1&{\color{blue}{1}}&&&\\ &&{\color{blue}{1}}&1&{\color{blue}{4}}&3&{\color{blue}{6}}&3&{\color{blue}{4}}&1&{\color{blue}{1}}&&\\ &{\color{blue}{1}}&1&{\color{blue}{5}}&4&{\color{blue}{10}}&6&{\color{blue}{10}}&4&{\color{blue}{5}}&1&{\color{blue}{1}}&\\ \end{array} $$

The one step approach above could be used to derive a recurrence relation for the number of minimal pathes and to derive the binomial coefficients.