Welcome to Open Problem #4! This is the first problem that's been drawn from our suggestion thread. This problem comes from Andrew Hayes. I want to draw from that thread more, so please, if you have any ideas for future open problems, send them in!
Consider an by grid. Each square can either be open or closed, except for the top left and bottom right squares, which are always open. How many arrangements exist such that there exists a path from the top left to the bottom right square (moving only up/down/left/right)?
Computer science mavens may recognize this as related to the "Rat in a Maze" problem used in textbooks. In the traditional setup, you are given the maze and then asked how many solutions are there. The textbook question is then to write a backtracking algorithm that finds all solutions to the maze.
This page has source code in both C++ and Java to the traditional problem. (Note: external link.)
The question posed here is very different, and as far as I can find in my comprehensive search, has never been asked. If we are given a particular size of grid, how many unique "mazes" can we make? Note we could adapt existing source code (like the example above) to work on solving this by simply adding a loop that tests every single maze configuration for a particular size. This is actually a fairly good way to start the problem.
However, we'd like to go a little farther, and start finding mathematical patterns. One approach might be to only ask about how many "mazes of a particular type" there might be; so not a comprehensive counting, but using some sort of generating rule to make mazes that are guaranteed to work and where it's easy to count how many mazes come from the rule.
As a goal for this open question, I'd like to get enough information that we can make the start of an entry in the On-Line Encyclopedia of Integer Sequences. (That is, we can solve it for 2 by 2, 3 by 3, 4 by 4 etc. up to a certain point - even if we don't have a general formula, we can calculate as many numbers as possible in the sequence.)
For Open Problem #3, if you haven't read it yet I definitely recommend David Vreken's solution here. He has two more example figures and mentions a possible new direction for research (using shapes other than isosceles right triangles for the "folding" method).
I will be putting the paper from Open Problem #2 up on ArXiv fairly soon, and sending it somewhere for publication (I'm guessing by the end of this week).