Could any coder/programer solve it? i'am really stucked

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?

Note by Kien Huu Nguyen
4 weeks, 1 day ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

I'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)

Alex Li - 3 weeks, 4 days ago

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.

Agnishom Chattopadhyay - 3 weeks, 6 days ago

Log in to reply

In Python:

import itertools
def g(a):
    if len(a) == 2: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += g([x-i for x in a[1:]])
    return sum

def lattice_ville(m, n):
    total = 0
    for i in itertools.combinations_with_replacement(range(1, m), r=n-2): #for each path Esther takes
        a = list(i)
        a.append(m-1)

        total += g(a) #add to the total the number of paths Daniel can take without intersecting
    return total

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

Eric Schneider - 5 days, 7 hours ago

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
nextmoves(rooms,vis,posD,posE) {
    if posD==posE==End position, then:
        return {length=size(vis), count=1};
    else: 
    loop through all possibilities, i, for next posD and next posE in rooms
    so that posD(i) and posE(i) not in vis u {posD,posE}
    for each i set obj(i) := nextmoves(rooms,vis u {posD,posE},posD(i),posE(i)).
    set m := max all the obj(i).length.
    set c := sum of all obj(i).count for i with obj(i).length==m
    return {length=m, count=c};
}

R Mathe - 3 weeks, 3 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...