In how many ways can a rectangular maze be traversed?
$begingroup$
Say the maze consists of $Mtimes N$ cells and the visitor may enter a cell from another cell which shares a common side. The visitor starts from the top left cell and ends at the bottom right cell, visiting each cell exactly once. This is possible when $M,N$ are not both even. Question is, how many routes are there? Anybody has considered this problem before?
For example, the following routes are for $4times 3$ maze and $5times 5$ maze respectively.
More generally, if the visitor starts from a given cell and ends at another given cell for which a qualifying route exists, then how many such routes are there?
combinatorics
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
$endgroup$
add a comment |
$begingroup$
Say the maze consists of $Mtimes N$ cells and the visitor may enter a cell from another cell which shares a common side. The visitor starts from the top left cell and ends at the bottom right cell, visiting each cell exactly once. This is possible when $M,N$ are not both even. Question is, how many routes are there? Anybody has considered this problem before?
For example, the following routes are for $4times 3$ maze and $5times 5$ maze respectively.
More generally, if the visitor starts from a given cell and ends at another given cell for which a qualifying route exists, then how many such routes are there?
combinatorics
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
$endgroup$
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39
add a comment |
$begingroup$
Say the maze consists of $Mtimes N$ cells and the visitor may enter a cell from another cell which shares a common side. The visitor starts from the top left cell and ends at the bottom right cell, visiting each cell exactly once. This is possible when $M,N$ are not both even. Question is, how many routes are there? Anybody has considered this problem before?
For example, the following routes are for $4times 3$ maze and $5times 5$ maze respectively.
More generally, if the visitor starts from a given cell and ends at another given cell for which a qualifying route exists, then how many such routes are there?
combinatorics
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
$endgroup$
Say the maze consists of $Mtimes N$ cells and the visitor may enter a cell from another cell which shares a common side. The visitor starts from the top left cell and ends at the bottom right cell, visiting each cell exactly once. This is possible when $M,N$ are not both even. Question is, how many routes are there? Anybody has considered this problem before?
For example, the following routes are for $4times 3$ maze and $5times 5$ maze respectively.
More generally, if the visitor starts from a given cell and ends at another given cell for which a qualifying route exists, then how many such routes are there?
combinatorics
combinatorics
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
edited Dec 15 '18 at 10:47
Haoran Chen
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
asked Dec 15 '18 at 9:56
Haoran ChenHaoran Chen
2138
2138
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39
add a comment |
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3, n>1, f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3040341%2fin-how-many-ways-can-a-rectangular-maze-be-traversed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3, n>1, f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
$endgroup$
add a comment |
$begingroup$
There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3, n>1, f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
$endgroup$
add a comment |
$begingroup$
There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3, n>1, f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
$endgroup$
There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3, n>1, f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
edited Dec 15 '18 at 12:40
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
answered Dec 15 '18 at 12:28
Sameer BahetiSameer Baheti
5718
5718
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3040341%2fin-how-many-ways-can-a-rectangular-maze-be-traversed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Have you tried to interpret this question in graph theory?
$endgroup$
– fantasie
Dec 15 '18 at 10:24
$begingroup$
Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once?
$endgroup$
– fantasie
Dec 15 '18 at 10:33
$begingroup$
There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far.
$endgroup$
– Haoran Chen
Dec 15 '18 at 10:39