Puzzles

In memoriam: Edsger W. Dijkstra

The Final Modification

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^24-13 — 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:

1. A diagram of the arrangement of bridges and islands being analyzed;
2. The program line setting the bridge list to the appropriate value;
3. The function plot of the probability the shores remain connected, as a function of the probability the individual bridges remain standing; and
4. The polynomial giving the probability the shores remain connected, as a function of the probability the individual bridges remain standing.

So here we go!

{1002}→List 1 P(p) = p	{1002,1002}→List 1 P(p) = -p2 + 2p	{1002,1002,1002}→List 1 P(p) = p3 - 3p2 + 3p
{1003,3002}→ List 1 P(p) = p2	{1003,1004,3004, 3002,4002}→List 1 P(p) = 2p5 - 5p4 + 2p3 + 2p2	{1003,1004,1005, 3004,4005,3002, 4002,5002}→List 1 P(p) = 4p8 - 18p7+ 27p6 - 10p5 - 9p4 + 4p3 + 3p2
{1003,3004,4002}→ List 1 P(p) = p3	{1003,1004,3004, 3005,4006,5006, 5002,6002}→List 1 P(p) = -4p8 + 14p7 - 13p6 - 2p5 + 4p4 + 2p3	{1003,1004,1005, 3004,4005,3006, 4007,5008,6007, 7008,6002,7002, 8002}→List 1 P(p) = 18p13 - 117p12 + 298p11 - 352p10 + 149p9 + 39p8 - 10p7 - 37p6+ 2p5+ 8p4 + 3p3

The final program is in the site library as a zip file.

The above table has a number of aspects that invite comment.

• The order of the probability polynomial is the same as the number of bridges involved. At first this seems peculiar. But remember how the probability function is computed: it is the sum of a number of terms, and each term is a count times p^k(1-p)^n-k where n is the number of bridges. The factor (1-p)^n-k is itself a polynomial of degree n-k, so the term as a whole is a polynomial of degree k+(n-k) or n, the number of bridges. The sum of these terms is therefore going to be a polynomial of at most degree n.
• The smallest power of p involved in the probability polynomial is the number of rows of islands. This may be a coincidence, or it may somehow reflect the structure of the problem. It invites inquiry.
• The graphs of the functions seem to have a particular kind of symmetry: the graph of the probability function for m rows of n bridges seems to be a reflection of the probability function for n rows of m bridges. The graphs seem to be a reflection through the point (½, ½); or, put another way, reflected both horizontally and vertically. A horizontal reflection replaces p with 1-p; a vertical reflection replaces P with 1-P. So, it seems the P(p) function for m rows of n bridges is very similar to the 1-P(1-p) function for n rows of m bridges.

This last apparent property is one we can actually test. P(p) is a polynomial in p, so P(1-p) is a polynomial in 1-p. We know from the binomial theorem that we can express as a polynomial in 1-p as a polynomial in p itself. We can find the coefficients of the reflection polynomial P(1-p) 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.