Seven cowboys play a coin tossing game [closed]

Seven cowboys play a coin tossing game with a fair coin where each player has a chance of 1/2 of winning. Each of them plays once against all other six. What is the probability that each cowboy wins exactly three games?

closed as off-topic by Slepz, Fimpellizieri, xnor, ghosts_in_the_code, BravoMar 16 '16 at 13:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Slepz, Fimpellizieri, xnor, ghosts_in_the_code, Bravo
If this question can be reworded to fit the rules in the help center, please edit the question.

• .045% chance? (1/2%) / 11 = .045 chance. I don't know, I'm not good with puzzles but I like trying lol – DemonicBirdFlu Mar 11 '16 at 12:45
• @Mike Earnest: Your link addresses the general problem of p-regular graphs on n vertices. My puzzle deals with the much simpler special case where n=2p+1. In any case I have tuned the puzzle down to seven cowboys. – Alexis Mar 11 '16 at 18:17
• I see, I saw a similarity to an unsolved problem, and jumped to the conclusion your problem was unsolvable. Sorry about that, seems like an interesting puzzle! – Mike Earnest Mar 11 '16 at 18:56
• @Oray, Cool, thanks for letting us know. – user1717828 Mar 11 '16 at 20:26
• I voted to close as a math q. Pls. let me know if you feel otherwise. – ghosts_in_the_code Mar 15 '16 at 5:07

It's pretty easy to calculate the exact result using a computer. I haven't found an easy way to calculate it by hand (yet), but if someone wants to check his result before posting:

$\frac{2640}{2097152} = \frac{165}{131072} = 0.00125885009765625$

Update: Optimized version, counting only matching combinations. It's now possible to verify, that the number of matches for all odd $n$ up to $11$ is listed in A007079.

public class Main {
private static final int SIZE = 7;
private static int[] rowSums = new int[SIZE + 1];
private static long count = 0;

private static void rec(int row, int col, int sum) {
if (row >= SIZE) {
++ count;
} else {
if (col >= SIZE) {
if (sum == SIZE / 2) {
rec(row + 1, row + 2, rowSums[row + 1]);
}
} else {
if (sum < SIZE / 2) {
rec(row, col + 1, sum  + 1);
}
if (rowSums[col] < SIZE / 2) {
++ rowSums[col];
rec(row, col + 1, sum);
-- rowSums[col];
}
}
}
}

public static void main(String[] args) {
rec(0, 1, 0);
System.out.printf("%d / %d\n", count, 1L << (SIZE * (SIZE - 1) / 2));
}
}
• Curse you! I was editing my answer from doing exactly this. Now I'm pretty sure I didn't have a bug. Oh yeah, and +1. – Joel Rondeau Mar 11 '16 at 23:01
• The number of matches for n=3,5,7 can be also found in A007079. – Sleafar Mar 11 '16 at 23:12
• +1. I checked it with some Maple code here (by no means optimizes running time, but calculations are not too large) and got the same answer. – Fimpellizieri Mar 12 '16 at 3:12
• For Maple, we can go with pol := 1; for i from 1 to k-1 do pol := coeff(pol ⋅ product( x[i] + x[j], j=i+1..k), x[i], m) end do; coeff(pol, x[k], m); where $m$ is the number of games each of the $k=2m +1$ cowboys needs to win. This is the fastest I could get, using the description in the link you provided. Without it, I produced some code that constructed each case iteratively, but it was lengthier and also slower. – Fimpellizieri Mar 13 '16 at 2:55

Making the events independent, we get a probabilty that is

$p_{i,j} = \mathbb{P}(\text{player }i\text{ wins }j\text{ games}) = {6 \choose j}\cdot 2^{-6}$.

(note: if six players wins 3 games, then the last player will also win 3 games)

So, for all players, assuming independent events (which clearly is not true), we get

$\prod_i p_{i,3} = \left({6 \choose 3}\cdot 2^{-6} \right)^6 \approx 0.000931.$

I run a simulation and got $\approx 0.0013$, so it is off by about 40 %.

• There are $7$ players, not $6$. – Gabriel Romon Mar 15 '16 at 19:24
• Yep. But as the note (see my answer) implied, if 6 players wins exactly 3 games, then the last player wins exactly 3. – Carl Löndahl Mar 15 '16 at 19:25

I'm not positive this is right, but I hopefully it's close.

$1/(6!)\approx 0.00139$

Let's say cowboy $i$ wins against cowboys $(i+1 \mod 7)$, $(i+2 \mod 7$), $(i+3 \mod 7$), and loses against all others. The number of cyclically invariant ways to order the $7$ cowboys is $6!$, only one assignment will match the above requirements.

Each cowboy would have 64 possible outcomes, of which 20 are 3 wins. 5/16^7 = 1.86e-8 ... Not very good odds.

That said I'm fairly certain my math is off somehow... At minimum, pretty sure I'm double counting all of the games, still even doubled, those odds would be pretty abysmal.

• You did 5/(16^7), where you should have done (5/16)^7=3e-4. There is a more subtle error: the chance of a cowboy getting exactly 3 wins is not independent of the chance of other cowboys getting 3 wins. (For instance, if 6 cowboys all have exactly 3 wins, then the 7th must also) – frodoskywalker Mar 11 '16 at 20:51

There are $7$ cowboys, and a total of $21$ games played $(6 + 5 + 4 + 3 + 2 + 1)$.

There is only one possible configuration (and $6!$ different reordering of players that can generate the same outcome) where each player wins $3$ games.

Not sure how to format this well, but one such configuration is this:

Player 1 wins against 2, 3, 4, loses to 5, 6, 7.

Player 2 wins against 3, 4, 5, loses to 6, 7, 1.

Player 3 wins against 4, 5, 6, loses to 7, 1, 2.

Player 4 wins against 5, 6, 7, loses to 1, 2, 3.

Player 5 wins against 6, 7, 1, loses to 2, 3, 4.

Player 6 wins against 7, 1, 2, loses to 3, 4, 5.

Player 7 wins against 1, 2, 3, loses to 4, 5, 6.

For this particular configuration to happen, all 21 games have to proceed with this configuration (or be one that is congruent (same outcome of wins/losses with player numbers swapped, basically a different reordering of players).

This gives us a probability of this, but it doesn't match simulation results:

$\dfrac{6!}{2^{21}} = \dfrac{5040}{2097152} \approx 0.00034332275$.

$6!$ for the number of different orderings of players that produce this one outcome, $2^{21}$ for the number of different possible outcomes for 21 games.

I also can't seem to edit the math to make it a spoiler...

Welp, I wrote a simulation in R, and I get a probability of around $0.0012$ as well...

Updated R simulation - can try $n = 3$ and $n = 5$:

all3wins = 0

n = 7
p = 1
q = p + 1
g = (n*(n-1))/2
neededwins = (n-1)/2
winsmatrix = array(0,dim = c(n,1))
gamematrix = array(0, dim = c(g,2))
threematrix = array(3,dim = c(n,1))

## Filling in the game matrix with correct pairings of 1v1
for (j in 1:g){
gamematrix[j,1] = p
gamematrix[j,2] = q
q = q + 1
if (q > n){
p = p + 1
q = p + 1
}
}

## Simulation part
for (qweq in 1:1000000){
winsmatrix = array(0,dim = c(n,1))
# Loops through 21 games
# Picks one of two winners from participants in game
# Adds one win to their row in winmatrix
for (j in 1:g)
{
w = gamematrix[j,sample(1:2,1)]
winsmatrix[w] = winsmatrix[w] + 1
}

# Counts how many times everyone gets 3 wins
isall3win = all(winsmatrix == neededwins)
all3wins = all3wins + isall3win
}
probability = all3wins/qweq

I tried $n = 3$ and $n = 5$ cases, and I got them to be this:

For 3 players, getting 1 win per player is $\dfrac{2!}{2^3} = \dfrac{1}{4} = 0.25$.

For 5 players, my simulation gets this... $0.0235 \approx \dfrac{4!}{2^{10}} = 0.0234375$ (the mathematical expression is just something I came up with that fits).

This makes me think that this should work for $n$ players:

$p = \dfrac{(n-1)!}{2^t}$ where $t = \dfrac{n(n-1)}{2} =$ number of games played, but this doesn't match simulation results for n = 7.