home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / puzzles / 7443 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.5 KB
  1. Path: sparky!uunet!spool.mu.edu!sgiblab!sgigate!rutgers!igor.rutgers.edu!remus.rutgers.edu!clong
  2. From: clong@remus.rutgers.edu (Chris Long)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Gale and Bridges (PARTIAL SPOILER)
  5. Message-ID: <Nov.22.01.54.49.1992.14102@remus.rutgers.edu>
  6. Date: 22 Nov 92 06:54:49 GMT
  7. References: <1992Nov20.191537.27029@cc.ic.ac.uk>
  8. Organization: Rutgers Univ., New Brunswick, N.J.
  9. Lines: 19
  10.  
  11. In article <1992Nov20.191537.27029@cc.ic.ac.uk>, Nairo Aparicio writes:
  12.  
  13. > Here there is a problem published on one of the boards of this department:
  14. > "In a certain wide river, there are 6 islands joined to each other and
  15. > the banks by 13 bridges, as shown below.   Unfortunately if there is a
  16. > gale, the bridges will each collapse with independent probability 1/2.
  17. > What is the probability that the river will be crossable after the gale?"
  18.  
  19. The river will be crossable iff there is a path from top to bottom;
  20. it will be uncrossable iff the river has a path from left to right.
  21. In the case for a rectangular bridge grid of mxn islands with probability
  22. of collapse p the associated river grid is also rectangular but with size
  23. (n-1)x(m+1) and (essentially) probability of collapse of 1-p.  Therefore,
  24. P(m,n,p) = 1-P(n-1,m+1,1-p); for the given problem we get P(2,3,1/2) =
  25. 1-P(2,3,1/2) ==> P(2,3,1/2) = 1/2.  For general p the problem is more
  26. tedious; I haven't done the computation yet, but I get that it's a
  27. polynomial of degree 13 in p.
  28. -- 
  29. Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
  30.