Analyzing double player games
$begingroup$
I know there are many questions/answers about double elimination tournaments out there, but I wanted to approach this question in a more holistic way.
For a double tournament with N teams, if B games are considered a winner, how many more games are needed to determine the best team with the smallest number of baskets?
In another way how many are needed to determine a loser?
These answers should probably be in an equation or expression form to apply . Good luck!
logical-deduction calculation-puzzle algebra
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
$endgroup$
add a comment |
$begingroup$
I know there are many questions/answers about double elimination tournaments out there, but I wanted to approach this question in a more holistic way.
For a double tournament with N teams, if B games are considered a winner, how many more games are needed to determine the best team with the smallest number of baskets?
In another way how many are needed to determine a loser?
These answers should probably be in an equation or expression form to apply . Good luck!
logical-deduction calculation-puzzle algebra
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
$endgroup$
$begingroup$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago
add a comment |
$begingroup$
I know there are many questions/answers about double elimination tournaments out there, but I wanted to approach this question in a more holistic way.
For a double tournament with N teams, if B games are considered a winner, how many more games are needed to determine the best team with the smallest number of baskets?
In another way how many are needed to determine a loser?
These answers should probably be in an equation or expression form to apply . Good luck!
logical-deduction calculation-puzzle algebra
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
$endgroup$
I know there are many questions/answers about double elimination tournaments out there, but I wanted to approach this question in a more holistic way.
For a double tournament with N teams, if B games are considered a winner, how many more games are needed to determine the best team with the smallest number of baskets?
In another way how many are needed to determine a loser?
These answers should probably be in an equation or expression form to apply . Good luck!
logical-deduction calculation-puzzle algebra
logical-deduction calculation-puzzle algebra
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
edited 7 mins ago
user18842sos
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
asked Mar 25 '18 at 16:58
user18842sosuser18842sos
1023
1023
$begingroup$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago
add a comment |
$begingroup$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago
$begingroup$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago
$begingroup$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Disclaimers and assumptions
Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.
To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.
Finally, to the point.
First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.
Minimal number of rounds that can guarantee finding the winner
On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.
Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in
$left lceil{frac{log(N)}{log(2)}} right rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")
Second place
The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes
$left lceil{frac{log(N)}{log(2)}} right rceil -1$ games,
because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.
All summed up
Therefore, finding the first and second places takes a total of
$N + left lceil{ frac{log(N)}{log(2)} } right rceil -2$ games.
Which for some sample values of N are
2 participants: $2 + left lceil{ frac{log(2)}{log(2)} } right rceil -2 = 1$ game
3 participants: $3 + left lceil{ frac{log(3)}{log(2)} } right rceil -2 = 3$ games
4 participants: $4 + left lceil{ frac{log(4)}{log(2)} } right rceil -2 = 4 $ games
10 participants: $10 + left lceil{ frac{log(10)}{log(2)} } right rceil -2 = 12 $ games
answered Mar 25 '18 at 19:17
BassBass
30k472185
$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: "559"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fpuzzling.stackexchange.com%2fquestions%2f62637%2fanalyzing-double-player-games%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$
Disclaimers and assumptions
Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.
To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.
Finally, to the point.
First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.
Minimal number of rounds that can guarantee finding the winner
On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.
Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in
$left lceil{frac{log(N)}{log(2)}} right rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")
Second place
The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes
$left lceil{frac{log(N)}{log(2)}} right rceil -1$ games,
because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.
All summed up
Therefore, finding the first and second places takes a total of
$N + left lceil{ frac{log(N)}{log(2)} } right rceil -2$ games.
Which for some sample values of N are
2 participants: $2 + left lceil{ frac{log(2)}{log(2)} } right rceil -2 = 1$ game
3 participants: $3 + left lceil{ frac{log(3)}{log(2)} } right rceil -2 = 3$ games
4 participants: $4 + left lceil{ frac{log(4)}{log(2)} } right rceil -2 = 4 $ games
10 participants: $10 + left lceil{ frac{log(10)}{log(2)} } right rceil -2 = 12 $ games
answered Mar 25 '18 at 19:17
BassBass
30k472185
$endgroup$
add a comment |
$begingroup$
Disclaimers and assumptions
Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.
To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.
Finally, to the point.
First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.
Minimal number of rounds that can guarantee finding the winner
On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.
Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in
$left lceil{frac{log(N)}{log(2)}} right rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")
Second place
The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes
$left lceil{frac{log(N)}{log(2)}} right rceil -1$ games,
because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.
All summed up
Therefore, finding the first and second places takes a total of
$N + left lceil{ frac{log(N)}{log(2)} } right rceil -2$ games.
Which for some sample values of N are
2 participants: $2 + left lceil{ frac{log(2)}{log(2)} } right rceil -2 = 1$ game
3 participants: $3 + left lceil{ frac{log(3)}{log(2)} } right rceil -2 = 3$ games
4 participants: $4 + left lceil{ frac{log(4)}{log(2)} } right rceil -2 = 4 $ games
10 participants: $10 + left lceil{ frac{log(10)}{log(2)} } right rceil -2 = 12 $ games
answered Mar 25 '18 at 19:17
BassBass
30k472185
$endgroup$
add a comment |
$begingroup$
Disclaimers and assumptions
Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.
To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.
Finally, to the point.
First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.
Minimal number of rounds that can guarantee finding the winner
On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.
Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in
$left lceil{frac{log(N)}{log(2)}} right rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")
Second place
The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes
$left lceil{frac{log(N)}{log(2)}} right rceil -1$ games,
because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.
All summed up
Therefore, finding the first and second places takes a total of
$N + left lceil{ frac{log(N)}{log(2)} } right rceil -2$ games.
Which for some sample values of N are
2 participants: $2 + left lceil{ frac{log(2)}{log(2)} } right rceil -2 = 1$ game
3 participants: $3 + left lceil{ frac{log(3)}{log(2)} } right rceil -2 = 3$ games
4 participants: $4 + left lceil{ frac{log(4)}{log(2)} } right rceil -2 = 4 $ games
10 participants: $10 + left lceil{ frac{log(10)}{log(2)} } right rceil -2 = 12 $ games
answered Mar 25 '18 at 19:17
BassBass
30k472185
$endgroup$
Disclaimers and assumptions
Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.
To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.
Finally, to the point.
First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.
Minimal number of rounds that can guarantee finding the winner
On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.
Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in
$left lceil{frac{log(N)}{log(2)}} right rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")
Second place
The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes
$left lceil{frac{log(N)}{log(2)}} right rceil -1$ games,
because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.
All summed up
Therefore, finding the first and second places takes a total of
$N + left lceil{ frac{log(N)}{log(2)} } right rceil -2$ games.
Which for some sample values of N are
2 participants: $2 + left lceil{ frac{log(2)}{log(2)} } right rceil -2 = 1$ game
3 participants: $3 + left lceil{ frac{log(3)}{log(2)} } right rceil -2 = 3$ games
4 participants: $4 + left lceil{ frac{log(4)}{log(2)} } right rceil -2 = 4 $ games
10 participants: $10 + left lceil{ frac{log(10)}{log(2)} } right rceil -2 = 12 $ games
answered Mar 25 '18 at 19:17
BassBass
30k472185
edited Mar 25 '18 at 19:39
answered Mar 25 '18 at 19:17
BassBass
30k472185
answered Mar 25 '18 at 19:17
BassBass
30k472185
answered Mar 25 '18 at 19:17
BassBass
30k472185
30k472185
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f62637%2fanalyzing-double-player-games%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$
Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 3.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?
$endgroup$
– iBot
37 mins ago