math puzzle

[emeraldemon]

Each game that I choose "random" in starcraft 2, I'm assigned Zerg, Terran, or Protoss with equal likelihood (I hope!). How many games would I have to play to have a 90% chance of playing each race at least once?

[jts]

Each game that I choose "random" in starcraft 2, I'm assigned Zerg, Terran, or Protoss with equal likelihood (I hope!). How many games would I have to play to have a 90% chance of playing each race at least once?

You mean pr(each at least once) or pr(x at least once), for all x?

[hyperpape]

Sounds like someone needs help with his homework!

No really, I know you'd never do that. This is a terrible place to ask for help on a Saturday night.

But after n games, you have a (1/3) ^ (n-1) chance of having always played the same race, and a (2/3) ^ (n-1) chance of having only played two different races. Sum them, and subtract from 1. So it takes 7 games. Right?

[emeraldemon]

You mean pr(each at least once) or pr(x at least once), for all x?

after N games, there will be a sequence like "ZTZPP..." . What I want to know is, what's the probability that sequence contains at least one Z, one T, and one P.

[emeraldemon]

Sounds like someone needs help with his homework!

No really, I know you'd never do that. This is a terrible place to ask for help on a Saturday night.

But after n games, you have a (1/3) ^ (n-1) chance of having always played the same race, and a (2/3) ^ (n-1) chance of having only played two different races. Sum them, and subtract from 1. So it takes 7 games. Right?

I thought it was pretty obvious, I was playing some starcraft and this little problem came to me when my "random" wasn't rolling up Zerg

Well, for the n = 3 case it's easy enough to enumerate all the ways we can get one of each
TPZ
TZP
PZT
PTZ
ZTP
ZPT

out of 3^3 = 27 total possible outcomes. 6/27 = 2/9
But if I understand your formula, you're suggesting
1 - ( (2/3)^2 + (1/3)^2) = 1 - (4/9 + 1/9) = 4/9
So something is off

[Joaz Banbeck]

Code: Select all

                              1
                              |
                ----------------------------
                |             |             |
                2             2             1
                |             |             |
           -----------   -----------   -----------
           |    |    |   |    |    |   |    |    |
           2    3    2   3    2    2   2    2    1

F(1) = 0
F(2) = 0
F(3) = 2/9
F(4) = 12/27

Hmmm...Hyperpape's formula does look right. It generates the right answer for N = 2 and N = 4. It generates a clearly wrong answer ( 4/9 ) for N = 3.
And it generates a rediculous answer ( -1 ) for N = 1.

[Joaz Banbeck]

F(n) = ( 3^(n-1) - 2^n + 1 ) / 3^(n-1)

It requires 9 tries.

[robinz]

I haven't read and considered all the replies, but some of them seem wrong to me. Here's my take:

If 1 of the 3 options is never selected in n attempts, there are clearly 2^n ways this can happen. That's for 1 specific, but arbitrarily chosen, option. For all 3 of them, we need to multiply by 3, but then subtract the cases we've counted twice. Clearly, the only cases we've counted twice are those where we've continually selected the same option, so there are only 3 of these.

Thus, the probability we want, after n attempts, is 1-[(3*2^n-3)/3^n], or (3^n-3*2^n+3)/3^n. I now notice this is the same as Joaz's formula (divide top and bottom by 3), so I can stop here and refer to his post

[emeraldemon]

Those look like the right answer to me!

[Joaz Banbeck]

BTW, my logic for finding the formula was to create a sort of 3-fold Pascal's Triangle, and to observe that there are obviously 3^(n-1) possibilities. Next I noticed that the paths that fail are close to 2^n, and should be exactly 2^n. Or so I thought.

I say 'close' because I finally realized that the paths that are all the same values (say, for example, Zerg Zerg Zerg etc) ecompass two 'failures' in one path. That is, they miss BOTH P and T every time, although they are only counted once. There is only one such path.
So the proper adjustment should be 2^n - 1.

( Dang, English is an imprecise language! )

[hyperpape]

I've always wished I'd taken either a probability or combinatorics class in college. I can think of five or ten classes I'd now trade for it.

[Li Kao]

Two more race distribution problems:
1) If you have all four players in a game of SC:BW are random, what is the probability to have the same race at least three times?

0

2) In a SC:BW 1on1 with both players random, what is the probability of a mirror matchup?

1/8 (Some sources say 1/24 but I assume they mean probability per matchup)

OK those were trick questions.

This gets interesting in case of multiple random players. It's not entirely random any more, the following rules apply:

2 players: the probability of a mirror matchup (same race twice) is only 1/8, as opposed to 1/3 as you would expect from a random distribution. All other matchups are equally likely.

More players: All matchups are equally likely, however only the following ratios are possible:
3: 1-1-1 or 2-1-0
4: 2-1-1
5: 2-2-1
6: 2-2-2 or 3-2-1
7: 3-2-2
8: 3-3-2

http://www.gamethreat.net/forums/starcr ... post546873

[ChradH]

( Dang, English is an imprecise language! )

I'm relieved others find it difficult to put their reasoning in words, too.

This is how I got there:

Probability of 'at least once' is 1 minus probability of 'never'.

After n games, probability of (for example) never being assigned Z is (2/3)^n
Note that this includes both the probabilities of always being assigned T as well as always being assigned P.

As there are three possibilities of leaving out one race, I initially thought the overall probability was three times the former value, that is 3*(2/3)^n or (2/3)^(n-1).

But after cross-checking with Joaz' results and seeing his were right, I found that simply adding the tree probabilities ends up counting those of being assigned only one race twice:
The probability of never being assigned T contains those for 'only Z' and 'only P' and the one of never being assigned P contains those for 'only Z' and 'only T'.
So one has to subtract three times the probability of being assigned a single race, which is 3*(1/3)^n or (1/3)^(n-1).

Putting it all together you get 1 - ( (2/3)^(n-1) - (1/3)^(n-1) ) which is incidentally identical to Joaz' result.

By the way, even the wrong formula without the last term yields the result n=9 for getting over 90%, apparently because the probability of being assigned only one race falls off rather quickly for large n.

edit: added hide tags

[Solomon]

In the spirit of Starcraft and math, here is another puzzle: I'm a Protoss player. Suppose I'm equally likely to face a Terran (PvT), a Zerg (PvZ), or a Protoss (PvP) on the ladder. Which of the following will take a fewer number of games on average: successively playing ladder games until I play a PvT then a PvT then a PvZ, or a PvT then a PvZ then a PvT ? (I hate mirror match-ups .)

[phillip1882]

i'd say they're both the same.
you have a 1/3 chance of playing any race on a match, and you have three matches. regardless of the arrangement of the races, this is the case.

its a bit like asking if Heads Tails Heads is more likely than Heads Heads Tails.

since starcraft probability math seems to be the theme, here's another.

an opponent will chose Zerg 28% of the time, terran 35% of the time, and protoss 37% of the time.
zerg beats protoss 57% of the time, terran beats zerg 55% of the time, and protoss beats terran 53% of the time.
if you pick a random race, what are your chances of winning?
if you want to pick the OP (overpowered) race, what race should you be?