It is currently Thu Mar 28, 2024 3:15 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 24 posts ]  Go to page 1, 2  Next
Author Message
Offline
 Post subject: math puzzle
Post #1 Posted: Sat May 28, 2011 5:23 pm 
Gosei
User avatar

Posts: 1744
Liked others: 702
Was liked: 288
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: 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?

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #2 Posted: Sat May 28, 2011 7:00 pm 
Oza
User avatar

Posts: 2644
Liked others: 304
Was liked: 631
Rank: kgs 6k
emeraldemon wrote:
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?

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #3 Posted: Sat May 28, 2011 7:41 pm 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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?

_________________
Occupy Babel!


This post by hyperpape was liked by: Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #4 Posted: Sat May 28, 2011 9:59 pm 
Gosei
User avatar

Posts: 1744
Liked others: 702
Was liked: 288
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: emeraldemon
jts wrote:

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.

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #5 Posted: Sat May 28, 2011 10:19 pm 
Gosei
User avatar

Posts: 1744
Liked others: 702
Was liked: 288
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: emeraldemon
hyperpape wrote:
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 :mrgreen:

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 :scratch:

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #6 Posted: Sat May 28, 2011 11:25 pm 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
Code:
                              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. :scratch:
And it generates a rediculous answer ( -1 ) for N = 1. :lol:

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #7 Posted: Sun May 29, 2011 12:09 am 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
F(n) = ( 3^(n-1) - 2^n + 1 ) / 3^(n-1)

It requires 9 tries.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207


This post by Joaz Banbeck was liked by: emeraldemon
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #8 Posted: Sun May 29, 2011 3:43 am 
Lives in gote

Posts: 414
Location: Durham, UK
Liked others: 96
Was liked: 15
Rank: KGS 9k
KGS: 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 :D


This post by robinz was liked by 3 people: cyclops, emeraldemon, Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #9 Posted: Sun May 29, 2011 8:50 am 
Gosei
User avatar

Posts: 1744
Liked others: 702
Was liked: 288
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: emeraldemon
Those look like the right answer to me!

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #10 Posted: Sun May 29, 2011 10:18 am 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
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! )

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #11 Posted: Sun May 29, 2011 10:51 am 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!


This post by hyperpape was liked by: ez4u
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #12 Posted: Sun May 29, 2011 11:42 am 
Lives in gote
User avatar

Posts: 643
Location: Munich, Germany
Liked others: 115
Was liked: 102
Rank: KGS 3k
KGS: LiKao / Loki
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.
Quote:
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

_________________
Sanity is for the weak.

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #13 Posted: Sun May 29, 2011 12:18 pm 
Dies with sente
User avatar

Posts: 106
Location: Germany
Liked others: 64
Was liked: 7
Rank: EGF 8k
Universal go server handle: ChradH
Joaz Banbeck wrote:
( 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

_________________
To sig or not to sig, that is the question.


This post by ChradH was liked by: Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #14 Posted: Tue Jun 07, 2011 9:32 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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 :P.)

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #15 Posted: Thu Jun 16, 2011 2:02 pm 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: 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?

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #16 Posted: Thu Jun 16, 2011 5:07 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
phillip1882 wrote:
its a bit like asking if Heads Tails Heads is more likely than Heads Heads Tails.

The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #17 Posted: Thu Jun 16, 2011 6:11 pm 
Lives in gote
User avatar

Posts: 324
Location: Dresden
Liked others: 26
Was liked: 22
Rank: KGS 7 kyu
KGS: Mnemonic, dude13
Araban wrote:
The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.

_________________
While I was teaching the game to a friend of mine, my mother from the other room:
"Cutting? Killing? Poking out eyes? What the hell are you playing?"

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #18 Posted: Thu Jun 16, 2011 7:33 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Mnemonic wrote:
Araban wrote:
The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.
If I did, I'd essentially be giving away the solution to the original question which I'm surprised no one has gotten so far. Regardless, writing a simulation program should be simple enough if you don't believe what I claim.

Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #19 Posted: Thu Jun 16, 2011 7:47 pm 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
Attempted answer. Of course we have previously established that I'm bad at probability...

After 3 flips, the two are obviously equal.

The trick is that starting with the fourth flip, some of the patterns that give you HTH are "blocked" by the HHT patterns.

Consider the fourth flip:

(1) HHH 1/2 chance of finishing HHT
(4) HTT
(5) THH 1/2 chance of finishing HHT
(6) THT 1/2 chance of finishing HTH
(7) TTH
(8) TTT

Missing from the list are
(2) HHT
(3) HTH
because you stop after three flips for these two.

I'm not sure how deeply related they are, but this reminds of an even more counterintuitive problem: http://mathoverflow.net/questions/17960 ... -want-boys with answers at http://mathoverflow.net/questions/17960 ... -want-boys. I don't pretend to understand even a fraction of that--the only part that made sense was to consider what happens if the country is just one family.

Edit: You actually have to show that the advantage HHT has after the fourth flip will persist. It seems obvious, but I don't have a good argument for it.

P.S. Oh, the question was about Starcraft. It's PvT, PvT, PvZ is more likely?

_________________
Occupy Babel!


Last edited by hyperpape on Fri Jun 17, 2011 5:27 am, edited 1 time in total.

This post by hyperpape was liked by: ez4u
Top
 Profile  
 
Offline
 Post subject: Re: math puzzle
Post #20 Posted: Thu Jun 16, 2011 8:24 pm 
Oza
User avatar

Posts: 2644
Liked others: 304
Was liked: 631
Rank: kgs 6k
Mnemonic wrote:
Araban wrote:
The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.

@mnemonic

Isn't it fairly obvious? If on average a coin comes up heads 50% of the time, then after it comes up heads on one flip, it needs to come up heads less than fifty percent of time on subsequent flips in order for the asserted probability to hold true. If you doubt me, flip a coin five or six times to test this.


Consider the sequences HTH and HTT. Obviously the conditional probability of getting H or T after having gotten the first two entries in the sequence (HT) is the same. So given a certain probability of getting HT, getting HTH and HTT on the next flip are equally likely. But after failing to get HTT, by definition you have an H in the third sequence, so you have a .25 chance of having HTT within two flips. But if you fail to get HTH, then you have a zero percent chance of getting HTH within two flips, and only a .125 chance of having HTT within three flips.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 24 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group