Massachusetts Institute of Technology Handout 5 Mathematics for Computer Science August 1, 2005 Professor Charles E. Leiserson

Optional Homework 1

Problem 1. Four castaways must escape from an island to the mainland on a makeshift raft. Their weights are 50, 100, 200, and 250. The raft can hold at most two people. The number of minutes required to paddle the raft between the island and the mainland is equal to the weight of the heaviest passenger aboard.

Example: If 100 and 250 cross together, 250 minutes are used. If 100 then returns alone, another 100 minutes are used.

Claim: The four castaways can not all escape in less than 650 minutes.

Proof. At least three trips and two return trips are required. Since the lightest person has weight 50, a minimum of 100 minutes are required for the two return trips. The three forward trips then require a total of 550 minutes: 100 minutes for 50 and 100, 200 minutes for 50 and 200, and 250 minutes for 50 and 250. Therefore, the total time for all four people to cross is at least 100 + 550 = 650 minutes as claimed.

Determine whether this proof is valid. If the proof is correct, justify each step. If the proof is wrong, pinpoint the precise error and either provide a correct proof or find a better lower bound than 650 minutes.

Problem 2. Find the fallacy in the following proof, pinpointing the precise error in reasoning.

Claim: If every vertex in a graph is adjacent to some other vertex, then the graph is connected.

Proof. The proof is by induction. The induction hypothesis is that if every vertex in an n-vertex graph is adjacent to some other vertex, then the graph is connected. For the base case, note that every graph with a single vertex is connected, so the hypothesis is true vacuously.

In the inductive step, assume that the induction hypothesis holds for every graph with n ≥ 1 vertices in order to prove that it holds for every graph with n + 1 vertices. Consider an n + 1 vertex graph in which every vertex is adjacent to some other. Arbitrarily select a special vertex v. Observe that, excluding vertex v, the graph has only n vertices and is therefore connected by induction. (This connected portion of the graph is represented by the blob on the right in the figure below.)

To prove that the whole graph is connected, we must show that there exists a path between every pair of distinct vertices x_{1} and x_{2}. There are two cases to consider. If neither x_{1} nor x_{2} is vertex v, then the path exists because both lie in the connected portion of the graph. Otherwise, one of the vertices is v (say x_{1}) and the other is not. By assumption, v is adjacent to some other vertex (call it u), which must lie in the connected portion. Again the path exists: it runs from x_{1} to u to x_{2} as shown in the figure.

Problem 3. (Hard.) A husband and wife host a dinner party for five other couples. During cocktails, as people arrive, lots of handshaking goes on, but no one shakes hands with their spouse. During the dinner, the host asks each other person at the party how many people they have shaken hands with. He is surprised to discover that the eleven answers he receives from his guests and his wife are all distinct. How many hands did the hostess shake?