What is the number of shortest paths from $A$ to $B$? (IJMO problem)

Question

What is the number of shortest paths from $A$ to $B$? We measure by the number of steps (not by length)

---

Attempt:

Notice that we should just consider 2 types of step: right and down. The longest path clearly required 8 steps. The longest 8-step path uses only short lines. Notice that if we use a long line one time, then it saves one short line (it is either right, right or down, down). Notice also if we use the hypotenuse line, then it is the same as two steps: right,down or down,right.

Now a shortest path consists only of 6 steps. These can be attained when we use 2 shortcuts: either using 2 long lines, or using 1 long line and 1 hypotenuse line.

There is only one shortest path that uses 2 long lines, the path is from $A$ to the top right, then straight to $B$.

There are only 2 shortest paths that use 1 long line and 1 hypotenuse.

So the total number of shortest paths is 3.

Are there better or simpler ways to solve the problem?

Answer 1

Since you knew you must take either the diagonal edge or the right most edge, you can reduce the work significantly by considering paths going only through them.

number of paths from A, distance from A

Answer 2

Let us work backward in this problem : we define an "algorithm" (there's a small issue) that will attach to each vertex, two numbers : the length of the shortest path from that vertex to $B$, along with the number of such shortest paths. For any vertex, we attach a $2$ tuple indicating these parameters.

This is very simple : start with labelling $B$ as $(0,0)$. Next, label all neighbours of $B$ as $(1,1)$. Then , proceeding to their neighbours and so on, do the following at each vertex:

• Check the following condition visually(this is the issue : I'd need to know how to algorithmically do this properly, but for a small graph visuals work) : all vertices which are strictly closer to $B$ than it, are labelled. Else, go to another vertex.

• If so, find the minimum of all the first labels of its neighbors, and add $1$ to the minimum : that is the first part of the label of this graph. Next, find how many neighbours attain the minimum : add the second labels of all these vertices, and you have the second label of your vertex.

Here's how my algorithm worked :

Let me explain the algorithm for a few cases.

$B,E,G$ should be obvious. Let us look at $D$. Every vertex of distance smaller than $D$ to $B$ is already labelled. These are $E,G$ whose first labels are $1$. Hence, the minimum is $1$ so the first label of $D$ is $2$. Also, both $E$ and $G$ attain the minimum first label value of $1$, so adding their second labels gives $2$, so $D$ is assigned $(2,2)$.

Now, look at $F$. Note that $D$ is labelled by now. The minimum of the first label is $2$, so the first label of $F$ is $3$. Next, the only label attaining the minimum is of course $D$, so its second label is $2$, which becomes the second label of $F$. So $F$ is assigned $(3,2)$.

Take $M$. By now, both of $Q,L$ will have been labelled. The minimum of their first labels is $4$, so the first label of $M$ is $5$. Next, the minimum is attained by both $Q$ and $L$, so the sum of their second labels is $3$, which we assign as second label to $M$. Thus $M$ is assigned $(5,3)$.

In this manner, if things are done correctly, then $A = (6,5)$, giving five paths. Furthermore, any path is given by a descent from $A \to B$ where the first labels decrease by $1$. In our case :

• AWQFDEB

• AWQFDGB

• AMQFDEB

• AMQFDGB

• AMLKJGB

Voila!

As to why the algorithm works, I leave you to see.

---

EDIT : one can algorithmically configure the "visually" part as follows : doing this with neighbours of $B$, proceed to doing it with "neighbours of neighbours", so in that case when you encounter a vertex, you can be confident that all "closer" vertices have been already labelled. Essentially, this is an induction by distance from $B$, like going from one layer of the onion to the next.