Walking At Random (Combinatorics)
Imagine that you are walking along the lines of the grid below.
If you start from the bottom left-hand corner, how many ways are there for you to leave your starting location and return to your starting point if you can't travel on the same line segment or pass through the same point twice?
The answer is 8222.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The closed paths enclose a connected surface of the $4\times 4$ grid that contains the bottom left corner. However not every connected surface works. The ones that work are the ones in which when we consider the complement of the figure, all of the connected components contain at least one square in the border. It is not hard to find how many of these there are through brought force and some dfs. This is because there is only $2^{15}$ subsets of the $16$ squares. We find there are 4111 such subsets and since each polygon can be transversed in two directions the answer is 8222