BMO1 2001 Problem 4
Problem 4: Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once)
The solution given in the book A Mathematical Olympiad Primer by Geoff Smith makes use of the Catalan Sequence. However, I don't see the linkage between the Catalan Sequence and the question. Does anyone know how they are linked?
combinatorics
asked Nov 26 at 12:15
Matthew Tan
395
add a comment |
Problem 4: Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once)
The solution given in the book A Mathematical Olympiad Primer by Geoff Smith makes use of the Catalan Sequence. However, I don't see the linkage between the Catalan Sequence and the question. Does anyone know how they are linked?
combinatorics
asked Nov 26 at 12:15
Matthew Tan
395
add a comment |
Problem 4: Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once)
The solution given in the book A Mathematical Olympiad Primer by Geoff Smith makes use of the Catalan Sequence. However, I don't see the linkage between the Catalan Sequence and the question. Does anyone know how they are linked?
combinatorics
asked Nov 26 at 12:15
Matthew Tan
395
Problem 4: Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once)
The solution given in the book A Mathematical Olympiad Primer by Geoff Smith makes use of the Catalan Sequence. However, I don't see the linkage between the Catalan Sequence and the question. Does anyone know how they are linked?
combinatorics
combinatorics
asked Nov 26 at 12:15
Matthew Tan
395
asked Nov 26 at 12:15
Matthew Tan
395
asked Nov 26 at 12:15
Matthew Tan
395
asked Nov 26 at 12:15
Matthew Tan
395
asked Nov 26 at 12:15
Matthew Tan
395
395
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0le kle n-1$. Thus $u_n=sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.
answered Nov 26 at 12:19
J.G.
22.3k22034
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%2f3014235%2fbmo1-2001-problem-4%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
Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0le kle n-1$. Thus $u_n=sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.
answered Nov 26 at 12:19
J.G.
22.3k22034
add a comment |
Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0le kle n-1$. Thus $u_n=sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.
answered Nov 26 at 12:19
J.G.
22.3k22034
add a comment |
Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0le kle n-1$. Thus $u_n=sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.
answered Nov 26 at 12:19
J.G.
22.3k22034
Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0le kle n-1$. Thus $u_n=sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.
answered Nov 26 at 12:19
J.G.
22.3k22034
answered Nov 26 at 12:19
J.G.
22.3k22034
answered Nov 26 at 12:19
J.G.
22.3k22034
answered Nov 26 at 12:19
J.G.
22.3k22034
22.3k22034
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3014235%2fbmo1-2001-problem-4%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
