number of possible sequences of a game
$begingroup$
Each of two teams has seven players numbered 1 to 7. In the first game, the two players numbered 1 play each other. The loser of each game is eliminated and replaced by the next player of the same team, until all players from one team have been eliminated. Let $N$ be the number of possible sequences of games. Find the remainder when $N$ is divided by 1000.
I think I can solve this by laying out all the possible cases of $a_1,a_2,...a_7$ and $b_1,b_2,...b_7$ combinations — one such example would be $a_b,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6,a_7,b_7$ (so team B wins). And even though I numbered each member, in truth, it really doesn't matter which exact number comes in, so we can say that all team members of A are $a$ and all team members of B are $b$. All games would start with $a,b,...$, so I think $frac{12!}{6!6!}$ would do the trick, but I'm not completely confident if I'm over/undercounting. Any help would really be appreciated!
sequences-and-series contest-math
$endgroup$
add a comment |
$begingroup$
Each of two teams has seven players numbered 1 to 7. In the first game, the two players numbered 1 play each other. The loser of each game is eliminated and replaced by the next player of the same team, until all players from one team have been eliminated. Let $N$ be the number of possible sequences of games. Find the remainder when $N$ is divided by 1000.
I think I can solve this by laying out all the possible cases of $a_1,a_2,...a_7$ and $b_1,b_2,...b_7$ combinations — one such example would be $a_b,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6,a_7,b_7$ (so team B wins). And even though I numbered each member, in truth, it really doesn't matter which exact number comes in, so we can say that all team members of A are $a$ and all team members of B are $b$. All games would start with $a,b,...$, so I think $frac{12!}{6!6!}$ would do the trick, but I'm not completely confident if I'm over/undercounting. Any help would really be appreciated!
sequences-and-series contest-math
$endgroup$
$begingroup$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36
add a comment |
$begingroup$
Each of two teams has seven players numbered 1 to 7. In the first game, the two players numbered 1 play each other. The loser of each game is eliminated and replaced by the next player of the same team, until all players from one team have been eliminated. Let $N$ be the number of possible sequences of games. Find the remainder when $N$ is divided by 1000.
I think I can solve this by laying out all the possible cases of $a_1,a_2,...a_7$ and $b_1,b_2,...b_7$ combinations — one such example would be $a_b,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6,a_7,b_7$ (so team B wins). And even though I numbered each member, in truth, it really doesn't matter which exact number comes in, so we can say that all team members of A are $a$ and all team members of B are $b$. All games would start with $a,b,...$, so I think $frac{12!}{6!6!}$ would do the trick, but I'm not completely confident if I'm over/undercounting. Any help would really be appreciated!
sequences-and-series contest-math
$endgroup$
Each of two teams has seven players numbered 1 to 7. In the first game, the two players numbered 1 play each other. The loser of each game is eliminated and replaced by the next player of the same team, until all players from one team have been eliminated. Let $N$ be the number of possible sequences of games. Find the remainder when $N$ is divided by 1000.
I think I can solve this by laying out all the possible cases of $a_1,a_2,...a_7$ and $b_1,b_2,...b_7$ combinations — one such example would be $a_b,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6,a_7,b_7$ (so team B wins). And even though I numbered each member, in truth, it really doesn't matter which exact number comes in, so we can say that all team members of A are $a$ and all team members of B are $b$. All games would start with $a,b,...$, so I think $frac{12!}{6!6!}$ would do the trick, but I'm not completely confident if I'm over/undercounting. Any help would really be appreciated!
sequences-and-series contest-math
sequences-and-series contest-math
asked Jan 28 at 8:12
jjhhjjhh
2,14411123
2,14411123
$begingroup$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36
add a comment |
$begingroup$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36
$begingroup$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Hint:
$frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$
A better approach might be to say that if team A wins overall then
- team A must win the last game
- team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n in {0,1,2,3,4,5,6}$
You then need to double this result since another possibility is that team B wins overall
Finally you have to do the remainder calculation
$endgroup$
add a comment |
$begingroup$
I think it should be $frac{14!}{7!7!}$.
Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.
$endgroup$
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
add a comment |
$begingroup$
There is an ambiguity in the question.
If "sequence of games" means sequence of winning teams (or losing teams) then there are $binom{14}{7}$ sequences, as Jaap Scherphuis shows.
But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $binom{14}{7} - binom{12}{6}$.
To illustrate the difference, consider the case of $2$ players on each team.
There are $binom{4}{2}=6$ sequence of winning teams:
$AA\
BAA\
ABA\
BB\
ABB\
BAB$
but only $binom{4}{2}-binom{2}{1}=4$ sequence of player pairs:
$(1,1),(2,1)\
(1,1),(2,1),(2,2)\
(1,1),(1,2)\
(1,1),(1,2),(2,2)$
$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%2f3090603%2fnumber-of-possible-sequences-of-a-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint:
$frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$
A better approach might be to say that if team A wins overall then
- team A must win the last game
- team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n in {0,1,2,3,4,5,6}$
You then need to double this result since another possibility is that team B wins overall
Finally you have to do the remainder calculation
$endgroup$
add a comment |
$begingroup$
Hint:
$frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$
A better approach might be to say that if team A wins overall then
- team A must win the last game
- team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n in {0,1,2,3,4,5,6}$
You then need to double this result since another possibility is that team B wins overall
Finally you have to do the remainder calculation
$endgroup$
add a comment |
$begingroup$
Hint:
$frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$
A better approach might be to say that if team A wins overall then
- team A must win the last game
- team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n in {0,1,2,3,4,5,6}$
You then need to double this result since another possibility is that team B wins overall
Finally you have to do the remainder calculation
$endgroup$
Hint:
$frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$
A better approach might be to say that if team A wins overall then
- team A must win the last game
- team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n in {0,1,2,3,4,5,6}$
You then need to double this result since another possibility is that team B wins overall
Finally you have to do the remainder calculation
answered Jan 28 at 8:31
HenryHenry
101k482169
101k482169
add a comment |
add a comment |
$begingroup$
I think it should be $frac{14!}{7!7!}$.
Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.
$endgroup$
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
add a comment |
$begingroup$
I think it should be $frac{14!}{7!7!}$.
Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.
$endgroup$
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
add a comment |
$begingroup$
I think it should be $frac{14!}{7!7!}$.
Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.
$endgroup$
I think it should be $frac{14!}{7!7!}$.
Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.
answered Jan 28 at 9:06
Jaap ScherphuisJaap Scherphuis
4,232717
4,232717
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
add a comment |
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
$begingroup$
+1. That is a nice argument to show $2sumlimits_{i=0}^n {n+i choose i} = 2sumlimits_{i=0}^n {n+i choose n} = 2{2n+1 choose n}={2n+2 choose n+1}$
$endgroup$
– Henry
Jan 28 at 13:24
add a comment |
$begingroup$
There is an ambiguity in the question.
If "sequence of games" means sequence of winning teams (or losing teams) then there are $binom{14}{7}$ sequences, as Jaap Scherphuis shows.
But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $binom{14}{7} - binom{12}{6}$.
To illustrate the difference, consider the case of $2$ players on each team.
There are $binom{4}{2}=6$ sequence of winning teams:
$AA\
BAA\
ABA\
BB\
ABB\
BAB$
but only $binom{4}{2}-binom{2}{1}=4$ sequence of player pairs:
$(1,1),(2,1)\
(1,1),(2,1),(2,2)\
(1,1),(1,2)\
(1,1),(1,2),(2,2)$
$endgroup$
add a comment |
$begingroup$
There is an ambiguity in the question.
If "sequence of games" means sequence of winning teams (or losing teams) then there are $binom{14}{7}$ sequences, as Jaap Scherphuis shows.
But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $binom{14}{7} - binom{12}{6}$.
To illustrate the difference, consider the case of $2$ players on each team.
There are $binom{4}{2}=6$ sequence of winning teams:
$AA\
BAA\
ABA\
BB\
ABB\
BAB$
but only $binom{4}{2}-binom{2}{1}=4$ sequence of player pairs:
$(1,1),(2,1)\
(1,1),(2,1),(2,2)\
(1,1),(1,2)\
(1,1),(1,2),(2,2)$
$endgroup$
add a comment |
$begingroup$
There is an ambiguity in the question.
If "sequence of games" means sequence of winning teams (or losing teams) then there are $binom{14}{7}$ sequences, as Jaap Scherphuis shows.
But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $binom{14}{7} - binom{12}{6}$.
To illustrate the difference, consider the case of $2$ players on each team.
There are $binom{4}{2}=6$ sequence of winning teams:
$AA\
BAA\
ABA\
BB\
ABB\
BAB$
but only $binom{4}{2}-binom{2}{1}=4$ sequence of player pairs:
$(1,1),(2,1)\
(1,1),(2,1),(2,2)\
(1,1),(1,2)\
(1,1),(1,2),(2,2)$
$endgroup$
There is an ambiguity in the question.
If "sequence of games" means sequence of winning teams (or losing teams) then there are $binom{14}{7}$ sequences, as Jaap Scherphuis shows.
But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $binom{14}{7} - binom{12}{6}$.
To illustrate the difference, consider the case of $2$ players on each team.
There are $binom{4}{2}=6$ sequence of winning teams:
$AA\
BAA\
ABA\
BB\
ABB\
BAB$
but only $binom{4}{2}-binom{2}{1}=4$ sequence of player pairs:
$(1,1),(2,1)\
(1,1),(2,1),(2,2)\
(1,1),(1,2)\
(1,1),(1,2),(2,2)$
answered Jan 28 at 10:29
gandalf61gandalf61
9,164825
9,164825
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%2f3090603%2fnumber-of-possible-sequences-of-a-game%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$
@Peter - then Player 1 of team A plays Player 2 of team B next
$endgroup$
– Henry
Jan 28 at 8:32
$begingroup$
OK, think I got this part. And what do we note ? $A1$ ?
$endgroup$
– Peter
Jan 28 at 8:36