Distributing cards among players
$begingroup$
Moderator Note: This is a current contest question on codechef.com.
N players sit around a round table. There are $n cdot m$ cards with unique numbers of range $1ldots ncdot m$.
Each player has $m$ cards. In each set of the game each player selects some card and everyone shows his card at the same time. Card of $i^{text{th}}$ player is compared to card of player $p[i]$. If it’s number is greater than the number on card of player $p[i]$, then $i^{text{th}}$ gets a point. $P$ is a permutation of sequence $0ldots n-1$.
But all players when playing want this game want to win. So, we decided to give cards in such way, that each player gets a point with probability larger than $frac{1}{2}$.
We need to tell all m cards of each of the n players playing the game.
Example : Let $n=3$ and $m=3$ and array $P$ be [2 0 1]. Then here answer is :
Player 0: 2 6 7
Player 1: 3 4 8
Player 2: 1 5 9
Here in this case each player has probability $frac{5}{9}$.
So i need to find the distribution of these cards.
probability combinatorics contest-math
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
$endgroup$
add a comment |
$begingroup$
Moderator Note: This is a current contest question on codechef.com.
N players sit around a round table. There are $n cdot m$ cards with unique numbers of range $1ldots ncdot m$.
Each player has $m$ cards. In each set of the game each player selects some card and everyone shows his card at the same time. Card of $i^{text{th}}$ player is compared to card of player $p[i]$. If it’s number is greater than the number on card of player $p[i]$, then $i^{text{th}}$ gets a point. $P$ is a permutation of sequence $0ldots n-1$.
But all players when playing want this game want to win. So, we decided to give cards in such way, that each player gets a point with probability larger than $frac{1}{2}$.
We need to tell all m cards of each of the n players playing the game.
Example : Let $n=3$ and $m=3$ and array $P$ be [2 0 1]. Then here answer is :
Player 0: 2 6 7
Player 1: 3 4 8
Player 2: 1 5 9
Here in this case each player has probability $frac{5}{9}$.
So i need to find the distribution of these cards.
probability combinatorics contest-math
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
$endgroup$
$begingroup$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
1
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
1
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07
add a comment |
$begingroup$
Moderator Note: This is a current contest question on codechef.com.
N players sit around a round table. There are $n cdot m$ cards with unique numbers of range $1ldots ncdot m$.
Each player has $m$ cards. In each set of the game each player selects some card and everyone shows his card at the same time. Card of $i^{text{th}}$ player is compared to card of player $p[i]$. If it’s number is greater than the number on card of player $p[i]$, then $i^{text{th}}$ gets a point. $P$ is a permutation of sequence $0ldots n-1$.
But all players when playing want this game want to win. So, we decided to give cards in such way, that each player gets a point with probability larger than $frac{1}{2}$.
We need to tell all m cards of each of the n players playing the game.
Example : Let $n=3$ and $m=3$ and array $P$ be [2 0 1]. Then here answer is :
Player 0: 2 6 7
Player 1: 3 4 8
Player 2: 1 5 9
Here in this case each player has probability $frac{5}{9}$.
So i need to find the distribution of these cards.
probability combinatorics contest-math
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
$endgroup$
Moderator Note: This is a current contest question on codechef.com.
N players sit around a round table. There are $n cdot m$ cards with unique numbers of range $1ldots ncdot m$.
Each player has $m$ cards. In each set of the game each player selects some card and everyone shows his card at the same time. Card of $i^{text{th}}$ player is compared to card of player $p[i]$. If it’s number is greater than the number on card of player $p[i]$, then $i^{text{th}}$ gets a point. $P$ is a permutation of sequence $0ldots n-1$.
But all players when playing want this game want to win. So, we decided to give cards in such way, that each player gets a point with probability larger than $frac{1}{2}$.
We need to tell all m cards of each of the n players playing the game.
Example : Let $n=3$ and $m=3$ and array $P$ be [2 0 1]. Then here answer is :
Player 0: 2 6 7
Player 1: 3 4 8
Player 2: 1 5 9
Here in this case each player has probability $frac{5}{9}$.
So i need to find the distribution of these cards.
probability combinatorics contest-math
probability combinatorics contest-math
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
edited Jul 7 '14 at 7:26
robjohn♦
270k27312639
270k27312639
asked Jul 5 '14 at 20:32
user157452user157452
7110
asked Jul 5 '14 at 20:32
user157452user157452
7110
asked Jul 5 '14 at 20:32
user157452user157452
7110
7110
$begingroup$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
1
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
1
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07
add a comment |
$begingroup$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
1
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
1
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07
$begingroup$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
1
1
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
1
1
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.
answered Jan 7 at 9:09
user574848user574848
449117
$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%2f857401%2fdistributing-cards-among-players%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$
Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.
answered Jan 7 at 9:09
user574848user574848
449117
$endgroup$
add a comment |
$begingroup$
Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.
answered Jan 7 at 9:09
user574848user574848
449117
$endgroup$
add a comment |
$begingroup$
Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.
answered Jan 7 at 9:09
user574848user574848
449117
$endgroup$
Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.
answered Jan 7 at 9:09
user574848user574848
449117
answered Jan 7 at 9:09
user574848user574848
449117
answered Jan 7 at 9:09
user574848user574848
449117
answered Jan 7 at 9:09
user574848user574848
449117
449117
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%2f857401%2fdistributing-cards-among-players%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$
I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$?
$endgroup$
– MJD
Jul 5 '14 at 20:44
$begingroup$
@MJD Itjust shows that ith player card is compared with card of P[i]th player
$endgroup$
– user157452
Jul 5 '14 at 20:45
1
$begingroup$
@MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically.
$endgroup$
– Gina
Jul 5 '14 at 20:54
$begingroup$
@Gina Yeah right
$endgroup$
– user157452
Jul 6 '14 at 4:50
1
$begingroup$
This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over.
$endgroup$
– Mod
Jul 6 '14 at 14:07