You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make it.
One example. 990 edges is precisely what you need to create a complete graph on 45 vertices. Call one of the 45 vertices A and another B. Then the number of paths from A to B is $$ 1 + 43 + 43\cdot42 + 43\cdot42\cdot41 + \cdots + 43! = \lfloor 43!\cdot e\rfloor \approx 1.64\times 10^{53} $$
Another example. We can do much better than that, though. For example consider this graph:
A---O---O---O---O.....O---O---B
\ / \ / \ / \ / \ / \ /
O O O O O O
made of 330 triangles. Here there are $2^{330}\approx 2.19\times 10^{99}$ simple paths from A to B.
How many paths can you make, and how? I know that solutions with plenty more than $10^{100}$ paths exist, but have no particular reason to believe that what I'm thinking of is optimal.
Most paths win. Answers must state the number of paths in ordinary scientific notation, and must explain clearly how the paths were counted (in addition to explaining how to construct the graph they're counted in, of course). It is acceptable to compute a lower bound instead of an exact count.
(Inspired by this math.SE question, but I don't think anyone will be able to prove a maximum, so it's more a puzzle than an exact question.)
Answer
$2.11×10^{135}$
If I'm not mistaken the following grid must give the optimal result:
where are 990/5 = 198 layers with 2 vertices.
Let's calculate number of paths. I number 2-vertice layers from 0 to 197. CD is 0th, GH is 197th. There are 3 different possibilities at each transition between two layers:
1) straight
/
/ __
2) vertical + straight
__
|\ |
| \ |
3) zigzag
__ __
\/ \
/\ _\
A rule here is that you can make vertical line only at the beginning of the transition. I call type 1 and type 2 open and type 3 - closed. After open transition you can have any other transition, but after closed you can have only type 1. Let's call number of paths, which lead to open layer $i$: $a_i$ and n of paths, which lead to closed layer $i$: $b_i$.
$a_0 = 2$, $b_0 = 0$ (see the vertical-line-rule above).
Open pattern can be followed by 4 open (type 1 and 2) or by 2 closed. Closed patern can be followed only by 2 open (type 1). Thereby: $$ \begin{pmatrix} a_{n} \\ b_{n} \end{pmatrix} = \begin{pmatrix} 4 & 2\\ 2 & 0 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ b_{n-1} \end{pmatrix} $$
Finally, to reach B-point after last layer we can use 2 ways if we ended with open pattern and 1 way with closed. So the total number of paths are:
$$ \begin{pmatrix}2&0\end{pmatrix} \begin{pmatrix} 4 & 2\\ 2 & 0 \end{pmatrix}^{197} \begin{pmatrix} 2 \\ 1 \end{pmatrix} $$
The result is $10^{135.325} = 2.11\cdot10^{135}$.
To be sure I haven't made mistakes, I have compared my calculations for 20 vertices and 45 edges graph with recursive program. They do agree.
The "inductive prove" (guess based) that most probably you can't do better you can find below.
The old answer:
@Falk Hüffner, gave the improved number $6.76 \cdot 10^{130}$ and the fact that you need to use 15 edges per "link" in the "chain", but there is still no prove and no example of the "link", which allows you to achieve this number. So let me do it here and give some extrapolations, which allows to imagine a probable optimal solution.
First, my chain of thoughts:
I got noted that @Henning Makholm (3 edges -> 2 paths), @Roland (5 edges -> 4 paths) and @f'' (9 edges -> 15 paths) can be reached easily from the complete graphs (for 3,4 and 5 vertices correspondingly) by rejecting the most useless edges. In case of 3 vertices there are no edges to reject. In case of 4 and 5 vertices you need to reject the one who connects A to B directly (and adds only 1 path).
Now, if we take complete graph on 6 vertices and will reject edges, which connect A to B via only 1 vertices we will get a graph, which have 10 edges and 20 paths. Which leads to $6.34 \cdot 10^{128}$ and is quite close to result with 5 vertices.
Here comes the example for current max-paths:
But you can improve result if you take 7 vertices and reject edges, which connect A to B via only 1 vertices. You will have 96 paths per 15 edges. And $6.76 \cdot 10^{130}$ paths for 990 edges.
To do so you need to take complete graph on 5 vertices (10 edges) and any 3 of them connect to A and other 2 connect to B.
Complete graph on 5 vertices allows you to reach any point from any-other point in $1+3+3\cdot 2+3\cdot 2+1$ = 16 paths. Plus you have 3 different ways to reach A and 2 ways to reach B, this leads to $16 \cdot 3 \cdot 2$ = 96 paths. Then $96^{990/15} \approx 6.76 \cdot 10^{130}$.
And the extrapolation:
When you try the same trick with 8 vertices, you will get $(65\cdot3\cdot3)^{990/(15+3+3)} \approx 2.83\cdot 10^{130}$ which is already smaller and since 990 is not dividable by 21 the actual result will be even worse.
Let's try now to reject also paths with 2 vertices. This is achieved in the following configuration: 
And the result here is exactly the same as with 7 vertices: 15 edges and 96 paths.
So I suppose to improve this you need to consider 9 vertices and reject all paths via 0,1 and 2 vertices (I still need to figure out how to build and count this, may be it is even to reject all paths, which go through 2 vertices only).
Now, it looks like you need to add 2 vertices and reject 1-vertice longer path each time. Finally, we can guess here that the most optimal result will be a complete graph on X vertices with all paths via 0,1,2,...,(X-5)/2 vertices excluded. So if you stretch it between A and B you should see a chain with width of ~2 vertices.
P.S. Another @Falk Hüffner result $8.16 \cdot 10^{130}$ with 18 edges and 240 paths in "link" is achieved in the following configuration of the link: 
This configuration follows the general sense rule, which I mentioned above: you need to take complete graph and rid of most useless links (those, which contribute to the shortest paths).
Unfortunately it was hard for me to consider all possibilities on paper, but my program confirmed that there are exactly 240 paths.
No comments:
Post a Comment