This is a problem that I set myself when I was at school. Find a formula $f(N,M)$ for the number of paths in an $N\times M$ grid starting at the bottom left, ending at the top right and going through every square once and only once.

I never was able to find a formula for this.

Is there a solution?

  • 1
    $\begingroup$ Can you elaborate more on what you mean by a path? From what I understand, there's 0 such paths in a 2x2 grid, but I may be misunderstanding. $\endgroup$ – Green Mar 22 '18 at 20:11
  • $\begingroup$ When you say "every square" do you mean "every lattice point" ? $\endgroup$ – futurebird Mar 22 '18 at 20:11
  • $\begingroup$ Here's a related (I think) question on MO. It looks like it's a hard problem, and no closed-form enumeration is known. $\endgroup$ – pjs36 Mar 22 '18 at 20:22
  • $\begingroup$ @futurebird only difference is the function is then $f(N+1,M+1)$ (a)Green correct. (a)pjs36 yes, related to the Hamiltonian problem. Is there any latest research? What is the name of the problem? $\endgroup$ – zooby Mar 22 '18 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.