Message from discussion
Gale and Bridges (Answer)
Path: sparky!uunet!mcsun!uknet!doc.ic.ac.uk!cc.ic.ac.uk!umahf69
From: umah...@ma.ic.ac.uk (Nairo Aparicio)
Newsgroups: rec.puzzles
Subject: Gale and Bridges (Answer)
Message-ID: <1992Nov27.154437.21132@cc.ic.ac.uk>
Date: 27 Nov 92 15:44:36 GMT
Sender: umah...@ic.ac.uk (?/20000)
Organization: Imperial College Mathematics Department
Lines: 87
Nntp-Posting-Host: macar.ma
Ok, here is the answer to the Gale and Bridges puzzle.
We have 13 bridges, so there are 2^13 = 8192 combinations.
Since the probability that each bridge will collapse es 1/2, you must agree
that the answer is the number of combinations such that you can cross the river
divided by 8192.
Let's call Sn the number of combinations such that: you can cross the river
AND there are exactly ``n'' bridges which have not collapsed.
The answer is obviously (S0 + S1 + S2 + ... + S13)/8192.
The beautiful thing of this problem is that you do not need to calculate
the Sn numbers, however, I am going to calculate some of then to make the
procedure easier to understand.
S0, S1 and S2 are obviously zero; you can not cross the river if there are
less than three bridges which have not collapsed. S3 is 3, and S4 requires
a little bit more work to be determined.
On the other hand, S13 = 1, there is only one combination where no bridges
has collapsed and you can cross the river in that combination.
S12 = C(13,1) = 13 and S11 = C(13,2) = 78, since in ALL the combinations
where there are more than 10 bridges which have not collapsed you can cross
the river. However, S10 = C(13,3) - 3 = 283, since there are three
combinations with just 10 bridges which have not collapsed where you can
not cross the river, they happen if three bridges parallel to each other
collapse. Now, to calculate S9, more work is requiered.
Now, what I think is the most beautiful part of this problem is the
following:
Take a sheet of paper and draw the river, the six islands and the 13 bridges
with one colour (say black). Between the bridges and the banks of the
river there are six squares. Take another colour (say blue) and draw ``six
virtual islands'' in the middle of each square. Turn the sheet 90 degrees.
Now, in blue ink, you have six islands arranged in a similar manner as the
six original islands (in black). Draw (with blue ink) 13 virtual bridges
and a virtual river arranged with respect to the 6 virtual islands as the
real bridges and river are with respect to the real islands. Each real
bridge is orthogonal with respect to one virtual bridge (say its twin
bridge).
Let's take as a convention that a real bridge collapses if and only if its
twin virtual bridge does not collapse and vice versa. If you study this
picture with care, you will realize that given a certain distribution of
bridges, you can cross the real river if and only if you can not cross the
virtual river.
If you call Tn the number of combinations such that: you can cross the
virtual river and exactly ``n'' virtual bridges have not collapsed, then:
Sn = C(13,n) - T(13 - n)
In words: The number of combination ``with n bridges'' such that you can
cross the real river is equal to the total number of combinations ``with n
bridges'' minus the number of combinations such that you can cross the
virtual river with exactly 13-n bridges. the reason for this is that if
you can cross the virtual bridge you can not cross the real bridge and the
sum of real bridges plus virtual bridges in a given combination is always
13.
Now, Tn = Sn since the virtual picture is equal to the real picture, so:
Sn + S(13-n) = C(13,n)
so S0 + S1 + S2 + ... + S13 = Sum from 0 to 13 of ((Sn + S(13-n))/2)
= Sum from 0 to 13 of C(13,n)/2 = 2^13/2.
So the answer is (2^13/2)/2^13 = 1/2.
If the river has a distribution of n times n-1 islands (n>1), the procedure
is exaclty the same and the answer is 1/2.
If you assume a collapse probability of ``p'', the answer will be:
3q^3p^10 + 38q^4p^9 + 433q^5p^8 + 636q^6p^7 + 1080q^7p^6 + 854q^8p^5 +
+ 677q^9p^4 + 283q^10p^3 + 78q^11p^2 + 13q^12p + q^13
where q = 1 - p
Nairo Aparicio
|
