So just what does our program do? It computes the function P(p) — not just values of the function, but the function itself — for a given arrangement of bridges and islands.
Wait. Where do we depend on that “given arrangement?” Only when we are determining whether a given combination of bridges leaves the two shores connected. And the only properties we use of the arrangement are (i) the shores are locations 1 and 2, and (ii) there is a table of bridge endpoints.
By Jove, all we have to do is modify the table of bridge endpoints, and we can compute the P(p) function for a different arrangement of bridges and islands!
Suppose we wanted just a single bridge, from location 1 (the top shore) to location 2 (the bottom shore). The only program change would be the first line, where the program specifies the bridge endpoints:
{1002}→List 1
That is it: everything else remains the same. (Lucky for us we used “Dim List 1” instead of “13” every time we needed the number of bridges!) The program draws a straight line from (0, 0) to (1, 1), and List 5 shows us P(p) = p. Well, yes, if there is only one bridge, and its probability of remaining is p, then the probability the shores remain connected is p.
We can compute any collection of bridges we want! Actually, not quite. Line 3 of the program:
Seq(0,A,1,8,1)→List 3
limits the number of locations to 8. This line just sizes List 3; List 3 is used to determine what locations are reachable. The List 3 elements are always indexed, so as long as List 3 is big enough, excess elements will not bother anything. (Excess elements will only make the Fill(0,List 3) operation a little slower.) So we change this line to:
Seq(0,A,1,25,1)→List 3
and we can have up to 25 locations. This is more than we will ever use: to actually need 25 locations would require 24 bridges, and computing with only 13 bridges takes hours. Computing with 24 bridges would increase the computation time by a factor of 2^{2413} — it would make computing over 2,000 times as long. It seems unlikely that we will try this size problem on a calculator.
Well, the original problem gives three rows of bridges across, and three rows of bridges. Let us try a number of different combinations. In each element of the following table, we will have:
So here we go!
{1002}→List 1

{1002,1002}→List 1

{1002,1002,1002}→List 1

{1003,3002}→

{1003,1004,3004,

{1003,1004,1005,

{1003,3004,4002}→

{1003,1004,3004,

{1003,1004,1005,

The final program is in the site library as a zip file.
The above table has a number of aspects that invite comment.
This last apparent property is one we can actually test. P(p) is a polynomial in p, so P(1p) is a polynomial in 1p. We know from the binomial theorem that we can express as a polynomial in 1p as a polynomial in p itself. We can find the coefficients of the reflection polynomial P(1p) for some collection of bridges, and see if they are the same as the coefficients of the polynomial P(p) for some other collection of bridges. If the coefficients are equal, the functions themselves are equal.
[ Previous page  Top of page  Next page ]
Copyright © 2002 Brian Hetrick
Page last updated 11 April 2006.