Introduction

This blog is inspired by this blog, which is an interesting constructive problem:

• How to construct a DAG with no multiple edges, such that there exists exactly $$$k$$$ distinct paths from vertex $$$1$$$ to $$$n$$$?

Obviously, there is a trivial solution which requires $$$2k$$$ edges and $$$k+2$$$ vertices. Simply connect vertex $$$1$$$ to each vertex numbered from $$$2$$$ to $$$k+1$$$, then connect each of these vertices to vertex $$$k+2$$$. In this blog, we shall discuss how to minimise the number of edges used.

Using no more than $$$4 \log k+1$$$ edges

This is likely to be the first way that many people will approach this problem. Consider the following structure:

There are exactly $$$2$$$ distinct paths from $$$1$$$ to $$$3$$$. If we chain them together as such:

There will be $$$2^3=8$$$ distinct paths from $$$1$$$ to $$$7$$$. We can see that it is possible to create $$$2^m$$$ paths using $$$3m$$$ edges.

For simplicity, we will call the chain $$$1 \to 3 \to 5 \to 7 \to \dots$$$ as the backbone, and $$$v_i$$$ to be the $$$i$$$-th vertex from $$$1$$$ on the backbone. For example, $$$v_0=1$$$, $$$v_1=3$$$, $$$v_k=2k+1$$$.

Using the method above, we can only construct a graph when $$$k$$$ is a power of $$$2$$$. Consider the binary representation of $$$k$$$. We first construct the backbone such that the number of paths has the same most significant bit as $$$k$$$. Then, for every non most significant set bit in $$$k$$$, say its the $$$j$$$-th bit, we add an edge from $$$v_j$$$ to the terminal vertex. For example, for $$$k=11$$$, its binary representation is $$$1011$$$, and we can construct the following graph:

Since for each $$$v_i$$$, there are exactly $$$2^i$$$ path ending at that vertex, we simple connect the positions corresponding to the set bits to the terminal vertex. There is a slight detail: we can't connect $$$v_{b-1}$$$ to $$$v_b$$$, as multiple edges are not allowed. In this case, we need to add another vertex and another edge.

In the worst case, where $$$k=2^p-1$$$ for some integer $$$p$$$, we need $$$4p+1$$$ edges: $$$3p$$$ for the backbone, $$$p$$$ for $$$p$$$ set bits, and $$$1$$$ extra for the detail above.

Can we do better?

The answer is Yes. To utilise edges even more, we need to change the structure of the backbone. After some thoughts, I came up with the following structure:

where $$$i$$$ connects to $$$i+1$$$ and $$$i+2$$$ for all $$$i \le n-2$$$, and $$$n-1$$$ connects to $$$n$$$. It is not hard to see that the number of distinct paths ending at vertex $$$i$$$ would be $$$F_i$$$, the $$$i$$$-th fibonacci number. The proof is left as a small exercise (hint: consider dp).

Using this structure, we can create $$$F_m$$$ paths using $$$2m-1$$$ edges.

Surprisingly, we can still use the binary representation idea above. Just like every integer can be represented by the sum of distinct powers of $2$s, every integer can also be represented by the sum of distinct fibonacci numbers. The theorem is called Zeckendorf's Theorem.

What makes this construction better is that: in the binary method, we need to consider the worst case where all bits are set. However, in the fibonacci method, the number of distinct fibonacci numbers each integer is partitioned into is not that large. In fact, I bruteforced all $$$k$$$ no larger than $$$10^7$$$, and I found that the maximum number of edges used is only $$$83$$$; for randomly generated integers in the range $$$[10^{17},10^{18}]$$$, the maximum number of edges used is $$$199$$$, whereas you need around $$$240$$$ for the binary method (worst case).

I don't have proofs of whether this method will be better for very large $$$k$$$s, like up to $$$10^{100}$$$ in the original blog. If you have explored this problem even deeper or is willing to, please share any interesting discoveries.

Anyways, this is my first blog on Codeforces. It is very coincidental, as I have made this problem on polygon for my friends a few months ago and they rated it around 2400. The constraints in that problem was $$$k \le 10^{17}$$$, and maximum $$$200$$$ edges.

Don't really know how to end off, so just hope everyone's rating grows like fibonacci numbers. Good luck!