insane odds

[art begotti]

i have no clue why, but i just wanted to see if it were possible to solve. so i turned to you guys.

suppose i were to randomly select one of two tiles, red or blue. i then place that at the bottomleft corner of a grid. for the sake of the probability, i replace whatever i took out so the odds for the draw are always 50/50.

so what are the odds, if i were to continue drawing, that when the grid of (x by x size) is finally filled, a path of red (made by up down left right, not diagonally) is made from the top of the grid to the bottom?

grid sizes:

3x3
5x5
10x10

and to throw more confusion into the mix, how about different tile sets?

red/blue (as listed above)
red/yellow/blue (equal odds 33/33/33)
r/y/b/green (25/25/25/25)
r/y/b/g/orange (20/20/20/20/20)

remember, the tile path made must be red, any other color doesnt count.

------------------
Good Night Gracie!

[ronl]

Am I missing something, or is the answer simply the probability of the event (i.e. 50%, 33%, 25% or 20%) raised to the number of events (5 for the 3x3, 9 for the 5x5, or 19 for the 10x10)?


------------------
This post is rated NWS: Not Worthy of a Signature.

[extropalopakettle]

Where are you getting the 5, 9 and 19 numbers from? There are far more than 19 ways to create a path from top to bottom on a 10 by 10 grid, and the paths may be of varying lengths.

[ronl]

Boy, I should know better than to answer a probability question before my first cup of coffee. I assumed (incorrectly) that the path had to go from the bottom corner to the top opposite corner.

My bad.



------------------
This post is rated NWS: Not Worthy of a Signature.

[Quailman]

Are the tiles placed systematically, or can the spot be optimally chosen? I would guess that after placing in the lower left, you go across the bottom row. When that's filled, you proceed to the left of row 2, and so on. Otherwise the odds of completing a path would be quite high indeed.

[dave10000]

For 3x3 and 50/50, I get 51/128.

[ronl]

Hmmm ... I get:

197/512 for 50/50 and 3x3 (38.5%),
2539/19683 for 33/33/33 and 3x3 (12.9%),
14473/262144 for 25/25/25/25 and 3x3 (5.5%)
54821/1953125 for 20/20/20/20/20 and 3x3 (2.8%)

22193/65536 for 50/50 and 4x4 (33.9%)
3330433/43046721 for 33/33/33 and 4x4 (7.7%)

but, admittedly, they were by the brute-force method.

------------------
This post is rated NWS: Not Worthy of a Signature.



[This message has been edited by ronl (edited 02-22-2002 11:01 AM).]

[art begotti]

let me clarify-- if you need it.

we'll just call x's red and o's blue.

code:

---

XOX


XXO


OXO


SUCCESS





XXO


OXO


XOX


FAILURE





XXX


XOO


OXX


FAILURE





XXO


XOO


XOX


SUCCESS

---