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

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

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