4
$\begingroup$

This problem was actually from a programming problem, but it has more of a math flavor, so I am asking on Math stack exchange!

Initial configuration

A configuration where it is possible to reach the bottom

A configuration where it is impossible to reach the bottom

Problem: Initially, you are given a graph as in the first image, where red lines are edges and grey circles are vertices. You want to reach from the top platform to the bottom platform. Now, 0 or more edges are deleted from the graph. How many such configurations of graph are there so that there is a path from the top to the bottom?

The second image is an example of a configuration where it is possible to reach from the top to the bottom, and the third image is an example of a configuration where it is impossible.

The hint I got was that this problem is only solvable (or relatively easily solvable) only when the graph is N by N + 1 (the picture shows a graph of 3 by 4).

I don't really want an exact solution, but rather some hints on how to proceed (completely stuck at the moment). I tried setting up some recurrence relation, but had trouble doing so.

$\endgroup$
1
  • $\begingroup$ This reminds me of some renormalization problems I have seen. You might try googling "renormalization". Apologies if you already knew that. $\endgroup$ Jun 17 '15 at 22:58
2
$\begingroup$

Hint: There will either be a connection from top to bottom, or an open path from left to right.

How many configurations with open paths are there?

Further hint: In an $n\times m$ configuration there are $(n+1)m$ possible vertical edges and $m(n-1)$ possible horizontal edges. In the magic case where $m=n+1$, this works out as $(n+1)^2+n^2$ possible edges. That looks nicely symmetric, doesn't it?

$\endgroup$
3
  • $\begingroup$ I'm not seeing the leap to the first hint here. How do you distinguish the two examples? $\endgroup$ Jun 17 '15 at 23:16
  • 1
    $\begingroup$ @Mario: In the middle (and top) example you can walk from shore to shore along the red bridges. In the bottom example you can sail from left to right (on the light blue water) without passing under a bridge. $\endgroup$ Jun 17 '15 at 23:17
  • $\begingroup$ Thank you very much! Solved the problem successfully :) $\endgroup$ Jun 18 '15 at 17:03
1
$\begingroup$

This is a pictorial hint supplementing Henning Makholm’s answer.

Arrows are bridges, $O$s are their supports:

$$\begin{array}{|ccccccc|} \hline \\ &\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\ &O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\ &\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\ &O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\ &\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\ &O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\ &\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\ \\ \hline \end{array}$$

Now arrows are possible seaways when the original bridges are broken:

$$\begin{array}{|ccccccc|} \hline \\ &\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\ &O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\ &\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\ &O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\ &\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\ &O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\ &\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\ \\ \hline \end{array}$$

Observe the symmetry between the two diagrams.

$\endgroup$
2
  • $\begingroup$ This pictorial hint helped me immensely. Thanks! $\endgroup$ Jun 18 '15 at 17:04
  • $\begingroup$ @user1441057: You're welcome! $\endgroup$ Jun 18 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.