Massachusetts Institute of Technology Handout 27 6.042J/18.062J: Mathematics for Computer Science October 9, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 4 Solutions

Problem 1. (10 points) Suppose that the dating game is played as described in class. That is, girls pursue their favorite boys, boys reject all but their top prospect, and the game ends when each boy has a single candidate remaining. Prove or disprove each of the following assertions.

(a) There is always some girl who gets her favorite boy.

The claim is false. Suppose that there are three girls named A, B, and C, and there are three boys named 1, 2, and 3. Assume that the boys and girls have the preferences shown in the table below.

girls’ picks boys’ picks
A : 1, 2, 3 1 : C, A, B
B : 2, 3, 1 2 : A, B, C
C : 2, 1, 3 3 : A, B, C

The next table shows what happens during the dating game. There is one row for each boy, and a column for each stage of the game. Each entry lists all the girls pursuing a boy at a given stage. The girl rejected at each stage is crossed off.

boy stage 1 stage 2 stage 3 stage 4
1 A A̸, C C C
2 B, C̸ B  A,B̸ A
3  B

In this case, every girl gets her second-favorite boy.

(b) For every number of girls and boys, it is possible for every boy to get stuck with his least favorite girl.

The claim is true. If every girl has a different favorite boy, then the algorithm terminates immediately and the boys’ preferences are irrelevant. In particular, every boy may be stuck with his least-favorite girl.

Problem 2. (5 points) There are two girls, Alice and Betty, and two boys, Steve and Tim. Alice prefers Steve, but the others’ preferences are such that every boy-girl dating arrangement is stable. What are Betty, Steve, and Tim’s preferences?

Steve prefers Betty, Betty prefers Tim, and Tim prefers Alice.

The key fact is that every dating arrangement must be stable. If Steve preferred Alice, then they would be a rogue couple if they were not dating. Therefore, Steve prefers Betty. If Betty preferred Steve, then they would be a rogue couple if they were not dating. Therefore, Betty prefers Tim. If Tim preferred Betty, then they would be a rogue couple if they were not dating. Therefore, Tim prefers Alice.

Problem 3. (10 points) Prove or disprove the following claim: for some n ≥ 3, there exists a set of boys’ and girls’ preferences such that every dating arrangement is stable.

The claim is false.

Proof. We will use letters to denote girls and numbers to denoted boys.

There must be some girl A rated worst by at most n − 2 boys. The reason is as follows. Each boy can rate exactly one girl worst. If each of the n girls was rated worst by at least n − 1 boys, then there would have to be at least n(n − 1) boys in all. But this is false when n ≥ 3, because then n(n − 1) exceeds n, the actual number of boys.

Suppose that this girl A is paired with the boy, 1, that she rates worst. Since at most n − 2 boys rate girl A worst, there is some other boy, 2, that rates a different girl, B, worst. Suppose that boy 2 is paired with girl B.

Now girl A and boy 2 form a rogue couple. Girl A prefers every other boy to her date, 1. Similarly, boy 2 prefers every other girl to his date B. Therefore, A and 2 prefer one another to their current dates.

Problem 4. (15 points) There are n girls in a tennis tournament. The tournament director hates to see anyone unhappy. Therefore, he plans to adjust the outcome of the tournament according to the following rule: if a player loses all her matches, then he will change all her losses to wins. Of course, changing the results in this way might create a new player who lost all her matches. Therefore, his plan is to continue applying his rule until there is no player who lost all her matches.

The tournament is played and the results are reported to the director. It so happens that the original tournament contains no cycles. The director now begins to adjust the results according to his rule.

(a) Use a state machine model and the Invariant Theorem to prove that the tournament director never creates a cycle through repeated application of his rule.

Proof. The proof uses the Invariant Theorem. Define a state machine as follows. Let the set of states Q be the set of tournaments. Let the set of start states Q_{0} be an arbitrary acyclic tournament. Let the transition relation δ consist of tournament pairs (T, T′) where T′ is obtained from T by applying the tournament director’s rule one time.

We will prove that the following invariant holds: the tournament is acyclic. In the start state, this invariant holds trivially. For each transition T → T′ in δ, assume that the invariant holds for T to prove that the invariant holds for T′.

Suppose that p is the player with all losses in tournament T that has all wins in tournament T′. There can be no cycle in T′ that does not involve player p, since this would imply a cycle in T as well. However, there can be no cycle in T′ that does involve player p, since she wins all her matches in T′.

Thus the invariant is established by the Invariant Theorem.

(b) Prove that by applying his rule, the director can never make everyone happy. That is, no matter how many times he applies his rule, there is still a player that lost all her matches.

Proof. The preceding proof implies that the director never creates a tournament with a cycle. We will prove that if a tournament does not contain a cycle, then there is player who lost all her matches. Together these facts imply that the director can never create a tournament where every player wins at least one match.

What remains is to prove that if a tournament does not contain a cycle, then there is a player who lost all her matches. We will actually prove the contrapositive: if every player won at least one match, then the tournament contains a cycle.

Form a sequence of players p_{1}, p_{2}, …, p_{n+1} as follows. Let p_{1} be an arbitrary player. Let p_{2} be one of the players beaten by p_{1}, let p_{3} be one of the players beaten by p_{2}, and so forth. We can form this sequence because every player won at least one a match by hypothesis. Since there are only n players, some player must appear more than once in the sequence p_{1}, p_{2}, …, p_{n+1}. Let p_{j} be the first player to appear a second time in the sequence, and let p_{i} be the first appearance of that player. Then the players p_{i}, p_{i+1}, …, p_{j−1} form a cycle.

Problem 5. (15 points) Suppose that the following procedure is used to multiply two non-negative integers a and b.

Let x = a, y = b, p = 0. Repeat the following steps.

If x = 0, then output p and terminate.

Otherwise, if x is even, then let x = x/2 and y = 2y. Otherwise, if x is odd, then let x = x − 1 and p = p + y.

(a) Model the procedure with a state machine.

The set of states Q consists of quintuples (a, b, x, y, p) where all variables are non-negative integers. The set of start states Q_{0} consists of the single state (a, b, a, b, 0). The set of transitions δ consists of transitions of the form (a, b, x, y, p) → (a, b, x′, y′, p′) where one of the following two sets of conditions holds:

1. x is even and positive, x′ = x/2, y′ = 2y, and p′ = p.

2. x is odd, x′ = x − 1, y′ = y, and p′ = p + y.

(b) Formulate an invariant relating a, b, x, y, and p that holds at the top of the loop. Your invariant should imply that when x = 0, p = ab.

xy + p = ab

(c) Prove that the invariant holds.

The invariant holds initially, because x = a, y = b, and p = 0. Suppose that the invariant holds in state (a, b, x, y, p). The invariant holds under a transition of the first type because:

x′y′ + p′ = (x/2) · 2y + p
= xy + p
= ab

The first equation follows from the definition of the first type of transition. The second line is obtained by simplification, and the third line uses the hypothesis that the invariant holds prior to the transition. By similar reasoning, the invariant holds under a transition of the second type:

x′y′ + p′ = (x − 1) · y + (p + y)
= xy + p
= ab

(d) Prove that the procedure terminates.

The variable x is a non-negative integer that decreases under every transition. Therefore, the procedure must terminate after at most x transitions.

Problem 6. (10 points) Brad Banks, the one 6.042 TA that Theory Pig trusts as his true friend, has promised our mascot a delicious treat. He places Theory Pig on one end of a 1 meter long rubber mat and places the treat at the other end of the mat. Theory Pig then begins to run excitedly toward his treat at the rate of 1 centimeter per second. (Theory Pig is four inches tall and a bit pudgy.)

However, after exactly one second has elapsed, Brad stretches the rubber mat out by 1 meter, so that its total length is now 2 meters. The mat stretches uniformly and instantly, so there are now 2 centimeters of mat behind Theory Pig and 198 centimeters between him and his treat. Theory Pig continues running toward his prize, but whenever another second elapses, Brad stretches the mat out by another meter.

Either prove that Theory Pig never reaches his treat or else compute approximately the number of seconds that he requires.

Running at a rate of 1 centimeter per second, Theory Pig crosses 1/100 of the mat in the first second, 1/200 of the mat in the second second, 1/300 of the mat in the third second, and so forth. He reaches his treat within n seconds provided that the sum of the first n of these fractions is greater than or equal to 1. Note that the sum of the first n of these fractions is just H_{n}/100. This expression is at least 1 when H_{n} is at least 100. Since H_{n} is about ln n, around e^{100} ≈ 10^{43} seconds are required for Theory Pig to reach his tasty treat.

Problem 7. (10 points)

(a) Sum the following infinite series.

∑_{i=0}^{∞} \frac{4^{i} − 3^{i}}{5^{i}}

∑_{i=0}^{∞} \frac{4^{i} − 3^{i}}{5^{i}} = ∑_{i=0}^{∞} (\frac{4}{5})^{i} − ∑_{i=0}^{∞} (\frac{3}{5})^{i}
= \frac{1}{1 − 4/5} − \frac{1}{1 − 3/5}
= \frac{5}{2}

In the first step, we split the one summation into two. The second step uses the formula for the sum of a geometric series. The last step is simplification.

(b) For the following summation use the integral method to find upper and lower bounds that differ by at most 0.1. Note that you may need to add the first few terms explicitly and then use integrals to bound the sum of the remaining terms.

∑_{i=1}^{∞} \frac{1}{i^{2}}

We can upper bound the summation as follows:

∑_{i=1}^{∞} \frac{1}{i^{2}} ≤ \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + ∫_{3}^{∞} \frac{1}{x^{2}} dx

= \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + (−\frac{1}{x})_{3}^{∞}
= \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \frac{1}{3}
= 1.694 …

We can lower bound the summation similarly:

∑_{i=1}^{∞} \frac{1}{i^{2}} ≥ \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + ∫_{3}^{∞} \frac{1}{(x + 1)^{2}} dx

= \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + (−\frac{1}{x + 1})_{3}^{∞}
= \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \frac{1}{4}
= 1.611 …

(The actual value of the summation turns out to be π^{2}/6 = 1.644 . . ..)

Problem 8. (10 points) A banker loans $100,000 to the Addams family so that they can purchase a new dilapidated mansion. At the end of each year for the next 20 years, Morticia Addams will drop by the bank to make a payment on the loan. The banker will immediately invest this returned money at a 7% annual rate of return.

What annual payment should the banker require of the Addams family so that his return after 20 years is the same as if he had invested the whole amount at 7% today instead of making the loan?

Suppose that Morticia pays p dollars at the end of each year for 20 years. The banker can invest the first payment for 19 years, the second payment for 18 years, etc. Therefore, after 20 years his total cash is:

∑_{i=0}^{19} p · 1.07^{i} = p · ∑_{i=0}^{19} 1.07^{i}

= p · \frac{1.07^{20} − 1}{1.07 − 1}

The second equation uses the formula for the sum of a finite geometric series. On the other hand, if the banker invests the money at 7% today, then after 20 years his total cash is 100, 000 · 1.07^{20}. Equating these two expressions and solving for p, Morticia’s annual payment, we find:

p · \frac{1.07^{20} − 1}{1.07 − 1} = 100, 000 · 1.07^{20}
p = 100, 000 · 1.07^{20} · \frac{1.07 − 1}{1.07^{20} − 1}
≈ $9439.29

Problem 9. (15 points) The 6.042 staff recently received the following mystifying, but disturbing email.

From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 2 complaint
We found your depiction of our society in problem set 2 simplistic,
inaccurate, and insulting.  We have launched a Fritolator device from
our homeworld at galactic coordinates (0, 0, 0).  During each hour,
the Fritolator can move in any one of the following ways.
  1.  first coordinate +4, second +1, third -1
  2.  first coordinate +1, second -1, third +3
  3.  first coordinate -2, second +3, third +4
Expect Earth, located at galactic coordinates (7, 8, 5), to be
Fritolated promptly.
/Grzzwk

We are unsure what Fritolation entails, but surmise that it is not good.

(a) Model the movement of the Fritolator as a state machine.

• The set of states Q consists of all triples of integers (x, y, z).

• The set of initial states Q_{0} consists of the single state (0, 0, 0).

• For all integers x, y, and z, the set of transitions δ contains the following three transitions:

(x, y, z) → (x + 4, y + 1, z − 1)
(x, y, z) → (x + 1, y − 1, z + 3)
(x, y, z) → (x − 2, y + 3, z + 4)

(b) Either list a sequence of Fritolator moves leading to the destruction of Earth, or use the Invariant Theorem to prove that Earth is safe.

Earth is safe.

Proof. The proof uses the Invariant Theorem. We prove that the following invariant holds: in state (x, y, z), 2x + 2y + z ≡ 0 (mod 3).

The invariant holds in the only start state, (0, 0, 0), because 2 · 0 + 2 · 0 + 0 ≡ 0 (mod 3). Next, we prove that the invariant is maintained under each transition in δ. There are three cases to consider corresponding to the three possible Fritolator moves.

• If the Fritolator moves from (x, y, z) to (x+4, y +1, z −1), then the invariant is maintained because:

2(x + 4) + 2(y + 1) + (z − 1) ≡ (2x + 2y + z) + 9 (mod 3)
≡ 2x + 2y + z (mod 3)
≡ 0 (mod 3)

Terms are just rearranged in the first step. The second step uses the fact that 6 is a multiple of 3, and the third step uses the assumption that the invariant holds in state (x, y, z).

• Similarly, if the Fritolator moves to position (x + 1, y − 1, z + 3), then the invariant is maintained because 2(x+1)+2(y−1)+(z+3) ≡ (2x+2y+z)+3 ≡ 0 (mod 3).

• If the Fritolator moves to position (x − 2, y + 3, z + 4), then the invariant is maintained because 2(x − 2) + 2(y + 3) + (z + 4) ≡ (2x + 2y + z) + 6 ≡ 0 (mod 3).

Earth is safe at coordinates (7, 8, 5), because 2 · 7 + 2 · 8 + 5 ≡ 2 (mod 3).