I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each other at the other side. Two people nearby were debating whether both sides had the same physical length, or whether one side was shorter. I spent lots of time in queues that day mulling over the following problem:
Define an $(m,n,k)$-queue to be an $m\times n$ grid, together with $k$ disjoint paths from one of the $m$-long sides to the other, such that
- each grid point is contained in one path;
- each of the paths has the same length;
- the entry points are contiguous, and
- the exit points are contiguous.
Question: What are necessary and sufficient conditions on $m$, $n$ and $k$ such that there exists an $(m,n,k)$-queue?
As examples, below are pictures of $(6,6,k)$-queues for $k=1,2,3,4,6$.
There are some obvious necessary conditions. First, $k$ must divide $mn$ (and the common path length is $l=mn/k$). Second, $k\le m$. However, these conditions are not sufficient; for example, it's not hard to show that there is no $(8,3,4)$-queue.
Some special cases are straightforward. An $(m,n,m)$-queue trivially exists; it consists of $m$ vertical paths of length $n$ (see the $(6,6,6)$-queue in the figure above.) An $(m,n,1)$-queue always exists; the $(6,6,1)$-queue above illustrates a ubiquitous construction. An $(m,n,n)$-queue always exists if $n\le m$; for example, here's the canonical construction of a $(6,4,4)$-queue:
Constructing larger queues from smaller queues
One easy way to extend a queue is to stack one queue on top of its reflection; thus the existence of an $(m,n,k)$-queue implies the existence of a $(m,cn,k)$-queue for any integer $c>0$.
Here's a more interesting construction. In an $(m,n,k)$-queue with $k|m$, there's a possibility that some horizontal line in the grid is crossed exactly $m/k$ times by each of the $k$ paths. (This happens, for example, in the pictured $(6,6,2)$-queue; both paths intersect the line below the top line three times.) In this case you can insert an extra row at this line, extending all $k$ paths vertically to get an $(m,n+1,k)$-queue:
Iterating, this proves the existence of a $(6,n,2)$-queue for all $n\ge 6$. (If you've been to the Haunted Mansion, this construction will look familiar!) You can also extend horizontally (if $k|n$ and every path intersects a vertical line $n/k$ times) to get an $(m+1,n,k)$-queue.
Remarks
The contiguousness requirement was motivated by observation of actual queues. However, the problem seems trivial if that requirement is dropped; in that case, the necessary conditions $k|mn$ and $k\le m$ are also sufficient.
Observe that there are some parity consequences of the bipartiteness of the grid. If $l$ is odd, the paths connect points of the same color in a "checkerboard" coloring of the grid, otherwise paths connect points of opposite color. If $mn$ is odd, then there's a "majority color"; the line of entry points (and the line of exit points) must begin and end with that majority color.
By connecting the first exit point to the second exit point, reversing direction and so on, the problem can be viewed as asking whether there is a Hamiltonian path in the grid with additional structure. This led to some interesting references but no solution.
There are plenty of related problems here, such as the problem of counting queues. Some variant of the Gessel-Viennot lemma seems like it might be useful; this has been extended to graphs with cycles (e.g. here) but the property that all paths have the same length is not preserved by tail-swapping, so there's room for innovation.