Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

closed as off-topic by Slepz, Fimpellizieri, xnor, ghosts_in_the_code, Bravo Mar 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.

1  
.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 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 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 at 18:56
    
@Oray, Cool, thanks for letting us know. – user1717828 Mar 11 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 at 5:07
up vote 7 down vote accepted

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));
    }
}
share|improve this answer
1  
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 at 23:01
2  
The number of matches for n=3,5,7 can be also found in A007079. – Sleafar Mar 11 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 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 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 %.

share|improve this answer
    
There are $7$ players, not $6$. – LeGrandDODOM Mar 15 at 19:24
1  
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 at 19:25

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.

share|improve this answer
    
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 at 20:51

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.

share|improve this answer

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.

share|improve this answer

Name the cowboys $A$ to $G$ and let $G$ be the focal cowboy. Three boys who lost to $G$ can be chosen in $_6C_3$ ways, and the other three choose themselves as the ones who won against $G$.

In one of the combinations, let $A$, $B$, $C$ win against $G$. In the matches between $A$, $B$ and $C$, two possibilities arise:

1) They each lost one match and won one match against each other. (2 combinations)

2) One of them won both matches, the second won one and the third lost both. (6 combinations).

Similar cases can be written in case of matches between $D$, $E$ and $F$.

All that remains now is to determine the winner of matches where one team is from $(A,B,C)$ and the other is from $(D,E,F)$. These are nine matches in total - since each team must win three and lose three, only the outcome of three of these nine matches must be determined, the remaining six are determined automatically. We shall consider the case where $A$-group and $D$-group falls under (1) and (2) respectively.

Case (i): A-Group in (1) and D-group in (1): Six valid outcomes are possible for matches between the two groups.

Case (ii): A-Group in (1) and D-group in (2): Three valid outcomes possible.

Case (iii): A-Group in (2) and D-group in (1): Same as (ii).

Case (iv): A-Group in (2) and D-group in (2): Only one valid outcome is possible.

Thus adding all combinations, we have $_6C_3\times(6\times 2\times 2+ 3\times 2\times 6 \times 2+ 6\times 6 \times 1)=2640$, and the probability is $\frac{2640}{2^{21}}$.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.