Esther and Daniel are playing a video game called Latticeville. Each level in Latticeville consists of a grid of m by n rooms, and the two players start in the southwest-most room. From each room in the level, the players are only permitted to move north or east. The level ends when both players reach the room furthest northeast. Esther and Daniel want to maximize the amount of the game that they explore collectively, so they want to ensure that—as much as possible—they never visit the same rooms as each other. But there seem to be many different ways to accomplish this. Given the size of a level in Latticeville, determine how many different subsets of rooms Esther and Daniel can visit such that the number of rooms visited is maximal.

Since the answer may be quite large, return the result modulo 109 + 7.

For m = 3 and n = 3, the output should be latticevillePaths(3, 3) = 3. In this level, they can visit a maximum of 8 rooms, and there are three ways for them to do that. The three pairs of routes are depicted below. The rooms that are visited in each case are lightly shaded.

For m = 3 and n = 4, the output should be latticevillePaths(3, 4) = 6. They can visit a maximum of 10 rooms in this level, and there are six ways to do that, depicted below.

what is the answer for the case which is n=5 and m=7 could anyone firgure out an algorithm for any n and m?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI'm almost certain I've seen this problem somewhere before, where did you get it from? (And it seems you're not the only one asking for an answer... https://math.stackexchange.com/questions/2790244/counting-lattice-paths/2790300)

Log in to reply

This is a very interesting problem. Did you come across this from some competitive programming site?

Also, before figuring out how many ways are there for them to cover the maximum number of cells, another interesting problem that we can try solving first is figuring out what this maximum number is.

Log in to reply

A good way to approach this problem is to look at it as a set of smaller problems. For this problem specifically, a good choice is:

## How many ways can we traverse an \(m\times n\) grid moving only north and east?

Imagine that we're programming a robot to move through some \(m\times n\) grid. This robot only has two commands: move one space north, and move one space east. We know that the grid is \(n\) spaces tall, so the robot has to move north \(n-1\) times. We also know that the grid is \(m\) spaces wide, so the robot has to move east \(m-1\) times. So, in total, we have \((n-1)+(m-1)=n+m-2\) commands to give the robot, from which, we choose \(n-1\) to tell it to move north. This means the robot can have \[{m+n-2\choose n-1}\] possible paths. This is an application of the stars and bars method.

Before we continue, let's think about the maximum number of spaces Esther and Daniel can hit on a given board. We know that one path will visit \(m+n-1\) spaces, and, in the maximal solution, two paths will only intersect at the beginning and end of the board, giving us \(2(m+n-1)-2 = 2m+2n-4\) spaces. Note here that in a \(1\times n\) or \(m\times 1\) board, there is an exception, but we know that that will always have \(1\) solution that will hit all \(nm\) spaces, so that's not too worrying.

Let's think about the paths that Esther and Daniel can take. If they both move in the same direction on the first space, they will intersect, giving a non-optimal solution. We also know that they will not intersect at their second-to-last move. This means we know that one player must start moving east and end moving north, while the other must start moving north and end moving east.

This means that both players traverse their own, intersecting \(m-1\times n-1\) sub-grid, with one sub-grid situated in the northwest corner of the board and the other situated in the southeast. That looks like this:

Where the red and blue lines represent each player's starting and ending moves, and the red and blue shading representing the grid they must traverse.

So now that we know this, how many ways can they both traverse these sub-grids?

To solve this, we must come up with a new way to represent the traversal of a grid. Let's label each point in the grid based on its distance from the leftmost square in the grid. That will look like this:

Then, any path can be described by a list of the labels of the grid squares where the player moves north. For example, the grid

can be described by the list

`[0, 2]`

, since the player moves north in those squares.It should be noted, though, that not every list corresponds with a valid lattice. The list

`[2, 1]`

, for example, is not valid, since moving north first at label \(2\) and then at label \(1\) would require one step west, which is not allowed. To fix this, we add one restriction: The list must benon-decreasing. Two consecutive numbers can be the same, which corresponds to moving north twice in a row, but if there is a set of numbers in the list that decreases, we know the player must move west, so the grid is not allowed.Very fortunately for us, there is a function in Python that generates non-decreasing lists of variable size from a given set of integers. This function is

`itertools.combinations_with_replacement`

. When used in a certain way, this returns an iterator that will give every non-decreasing list of size \(n-1\) constructed from integers in the interval \([0, m]\). We construct this like so:Note: From now on, we will assume Esther always travels east to start.This will give us the list description of every solution to an \(m-1 \times n-1\) rectangular grid. That's all well and good, but it surely isn't the solution. After all, one path for Esther could give way to a plethora of paths for Daniel. How do we solve this problem? Well, let's look at an example. Let's say we're on a \(4\times 4\) grid and Esther traverses her \(3\times 3\) sub-grid with the path represented by

`[1, 1]`

. That looks like this:As you can see, Esther has blocked off a significant portion of Daniel's grid. We

coulduse the same`itertools.combinations_with_replacement`

for Daniel and just root out any intersecting paths that Daniel takes, but that would be wasteful and take a very long time to calculate. After all, just using`itertools.combinations_with_replacement`

once puts our time complexity at \(O({m+n-4 \choose n-2})\), which gets bigfast, especially for square-like grids. We want a way to take the output of the`itertools`

function and somehow discover how many paths Daniel can take. Let's call the weird lattice-based polygon that Daniel needs to traverse alattice-gon. Then we have a new sub-problem.## How many ways can you traverse a lattice-gon?

Let's represent a lattice-gon in the same way we did a traversal path: as a list. For an \(n\)-tall lattice-gon, we can represent it as a list of integers, where the \(i^{\text{th}}\) integer represents the length of the polygon at height \(i\). Let's start with a \(1\)-tall lattice-gon. This is easy: there's only one way to traverse it! We just go east until we finish.

Let's try one level more: a \(2\)-tall lattice-gon. We know that

`list[0]`

will give us the length of the first row of the lattice-gon, so we have`list[0]`

places to go north. Once we go north, though, the rest of the problem is analogous to solving a \(1\)-tall lattice-gon, so we know that the number of solutions is equal to`list[0]`

.The next one is harder: a \(3\)-tall lattice-gon.

`list[0]`

will give us the length of the first row of the lattice-gon. So we have`list[0]`

ways to do this. Let's say we go north as soon as we can. Then, number of solutions branching from that path is analogous to the number of solutions to the lattice-gon`list[1:]`

, which is the list without its first element. If we go east \(x\) times before we go north, we will have cut off the first \(x\) elements of each row, so the number of solutions branching from that path is analogous to the number of solutions to the lattice-gon`[i-x for i in list[1:]]`

. The total number of solutions is the sum of the number of solutions for each branching path.This recursive pattern repeats for everything greater than \(3\).

One more thing before we write this in Python, though: It actually doesn't matter how long the top row is, so we will omit it in our list. So the function looks like this:

So we have two functions, but how do we connect them together? Well, it's really simple: The way that we used the

`itertools`

function meshes perfectly with our`lattice_gon`

function! I'll leave it as an exercise to the reader to figure out why, but it shouldn't be too hard.So our total function looks like:

This is a really slow function, but is slightly faster than brute-force as it generates no wrong solutions. I think it runs in \[O(m^2{m+n-4 \choose n-2}) \in O(m^2(m+n)!)\]

Which is much faster than the brute force solution, which runs in \[O(((m+n)!)^2)\]

`lattice_ville(5,7)`

returns \(\boxed{1176}\).Log in to reply

Thanks for the detailed explanation.

Apparently, Hana Wehbi's solution here has a more analytical approach which solves the problem almost in constant time (except for the cost of computing binomial coefficients), You might want to check it out.

Log in to reply

In Python:

I'll work on a write-up for how I got here if anybody asks, but the solution is \(\boxed{1176}\).

Log in to reply

I would really appreciate an explanation.

Log in to reply

Sounds good! I'm at work right now but I'll write it up when I get home. Expect something around 4 or 5 hours from now!

Log in to reply

Log in to reply

Log in to reply

A simple but inefficient way to do this is to generate an algorithm (here pseudocode).

Here

`rooms`

is a set of all positions in the room (of course this can be replaced by a simple parameterisation),`vis`

is the set of rooms already visitted,`posD`

= the current position of Daniel an`posE`

= current position of Esther.Calling

`nextmoves(array of mxn positions,{},(0,0),(0,0))`

will return an object containing the length of the longest possible explorations and the # of possible ways to achieve this.Log in to reply