# Puzzles

## In memoriam: Edsger W. Dijkstra

### Interpreting the Problem Statement

First, we must make sure we understand the problem. The initial situation consists of (i) a river, represented in the diagram by the white background; (ii) two shores of the river, represented by the two hatched bands; (iii) six islands in the river, represented by circles between the two hatched bands; and (iv) thirteen bridges, represented by gray lines between the circles and between circles and the hatched bands.

This situation changes by bridges being “swept away” with “probability ½.” We interpret a bridge being “swept away” as the bridge being removed from the set of bridges available for use. We interpret the phrase “probability ½” as each bridge, independently, having an equal likelihood of remaining available for use or being removed from the set of bridges available for use.

The question involves whether “the shores remain connected.” We interpret this as asking whether there is a path from one shore to the other shore, where the path goes from a location over a remaining bridge to another location, and from that location over a remaining bridge to yet another location, and so forth.

Finally, the question asks the probability that the shores remain connected. To interpret this question, we need to understand just a little bit about about probability.

### The Math Part

A probability space is a triple (S, , P) where S is a nonempty set called the sample space, is a σ algebra of subsets of S called the set of events, and P: is a probability measure.

Come back! Come back! I promise I’ll be good. I’ll go back to English now, really!

There are 13 bridges. After a storm, each bridge either remains, or is removed. The possible outcomes are particular combinations of bridges remaining. The sample space is the set of possible outcomes. The sample space here is the set of combinations of the 13 bridges. Each outcome is a set of bridges that remain standing; the set of all outcomes — in this case, a set of sets — is the sample space.

#### Mathematical Amusements (a diversion)

The set of all subsets of a set A is called the power set of A. The power set of A is denoted by 2A. If we associate each bridge with an index taken from {1, 2, ..., 13}, then the outcomes are {} (the empty set, representing the case where no bridge survives the storm), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, ..., {1, 2, ..., 12, 13}. The sample space is therefore the power set of {1, 2, ..., 13}.

The number of elements in a set A is called its cardinality and is represented by the absolute value operator |A|. For finite sets A, |2A| = 2|A|, that is, the cardinality of the power set of a set is two to the power of the cardinality of the set.

The probability of an event is a number from 0 to 1 that measures the likelihood of an event. In this case, it is the likelihood of a particular combination of bridges remaining after a storm passes. A probability of 0 means an event is impossible, and cannot occur. A probability of 1 means an event is certain, and must occur. In our case, we assume that whether a given bridge remains or has been removed is not influenced by what other bridges remain or have been removed. This property of probabilities is called independence, and it implies that we can compute the probability of the intersection of two events — that they both happen at once — in a particularly easy way: we get to multiply the two probabilities together.

Suppose we have an outcome, that is, a combination of bridges that remain after a storm passes. There is a set of bridges that remained, and a set of bridges that were removed. Each bridge that remained, had a probability ½ of remaining; and each bridge that was removed, had a probability ½ of being removed. As the bridges remaining or being removed are independent of one another, we can multiply the probabilities together: ½ for the first bridge — either it remains, with probability ½, or it has been removed, with probability ½ — ½ for the second bridge, ½ for the third bridge, and so forth, on to ½ for the thirteenth bridge. There are 13 instances of ½ to multiple together, one for each bridge. The probability is therefore ½13, or 1/8192, for the outcome — for the particular combination of bridges to remain after the storm has passed. This is true for every outcome, regardless of which particular bridges remain.

Each outcome, that is, each possible combination of bridges remaining after the storm has passed, therefore has probability ½13, or 1/8192. What we are interested in, though, is “the probability that the shores remain connected,” that is, whether the bridges that remain after the storm let one travel from one shore to the other. For each possible combination of bridges that could remain after a storm, either the shores are connected or they are not. Further, if a particular combination of bridges remains after the storm, then no other combination of bridges remains after the storm. So what we want is the probability of the event that the two shores remain connected.

We have outcomes — combinations of bridges that remain after the storm — and events — sets of possible outcomes. We want the probability of the event “the shores remain connected.” One of the properties of a probability measure is that the probability of an event composed of a number of outcomes in the sum of the probabilities of the individual outcomes. So the probability that the event “the shores remain connected” occurs is just the sum of the probabilities of the outcomes where the shores remain connected.

#### Mathematical Amusements (a diversion)

The properties of a probability measure are:

where the zero with the slash through it indicates the null set, S we remember is the sample space, and the {Ai} are mutually exclusive events. The big “U” symbol indicates the union of the sets Ai; the capital sigma symbol indicates the sum of the values P(Ai); and iI underneath the union and sum operators indicates that the union or sum is taken over all the indexes in a set I. The phrase “mutually exclusive” means that no two events can occur at the same time.

Well, each outcome is an event, and the outcomes are mutually exclusive. So we can determine the probability of an event as just the sum of probabilities of the outcomes composing the event.

In the case of the bridges, each outcome has the same probability, 1/8192; so if C is the set of outcomes, that is, sets of bridges remaining, that leave the shores connected, the probability of the shores being connected is just the number of elements of C, divided by 8192.

Therefore, we can answer the question (remember the question? “What is the probability that the shores remain connected?”) by the following process:

1. Consider all possible outcomes;
2. Count the outcomes that leave the shores connected; and
3. Divide the count of outcomes that leave the shores connected by 8192.

Well, let’s get started, then.

Page last updated 10 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