🚀 go-pugleaf

In article <1992Nov20.191537.27029@cc.ic.ac.uk>, Nairo Aparicio writes:

> Here there is a problem published on one of the boards of this department:
> "In a certain wide river, there are 6 islands joined to each other and
> the banks by 13 bridges, as shown below.   Unfortunately if there is a
> gale, the bridges will each collapse with independent probability 1/2.
> What is the probability that the river will be crossable after the gale?"

The river will be crossable iff there is a path from top to bottom;
it will be uncrossable iff the river has a path from left to right.
In the case for a rectangular bridge grid of mxn islands with probability
of collapse p the associated river grid is also rectangular but with size
(n-1)x(m+1) and (essentially) probability of collapse of 1-p.  Therefore,
P(m,n,p) = 1-P(n-1,m+1,1-p); for the given problem we get P(2,3,1/2) =
1-P(2,3,1/2) ==> P(2,3,1/2) = 1/2.  For general p the problem is more
tedious; I haven't done the computation yet, but I get that it's a
polynomial of degree 13 in p.
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618