Previous page Next page Navigation bar

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 224-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!

One column, one row, no islands, one bridge

{1002}→List 1

Graph of function
P(p) = p

Two columns, one row, no islands, two bridges

{1002,1002}→List 1

Graph of function
P(p) = -p2 + 2p

Three columns, one row, no islands, three bridges

{1002,1002,1002}→List 1

Graph of function
P(p) = p3 - 3p2 + 3p

One column, two rows, one island, two bridges

{1003,3002}→
List 1

Graph of function
P(p) = p2

Two columns, two row, two islands, five bridges

{1003,1004,3004,
3002,4002}→List 1

Graph of function
P(p) = 2p5 - 5p4 + 2p3 + 2p2

Three columns, two rows, three islands, eight bridges

{1003,1004,1005,
3004,4005,3002,
4002,5002}→List 1

Graph of function
P(p) = 4p8 - 18p7+ 27p6 - 10p5 - 9p4 + 4p3 + 3p2

One column, three rows, two islands, three bridges

{1003,3004,4002}→
List 1

Graph of function
P(p) = p3

Two columns, three rows, four islands, eight bridges

{1003,1004,3004,
3005,4006,5006,
5002,6002}→List 1

Graph of function
P(p) = -4p8 + 14p7 - 13p6 - 2p5 + 4p4 + 2p3

Three columns, three row, six islands, 13 bridges

{1003,1004,1005,
3004,4005,3006,
4007,5008,6007,
7008,6002,7002,
8002}→List 1

Graph of function
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.

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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 11 April 2006.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data