Massachusetts Institute of Technology Handout 19 6.042J/18.062J: Mathematics for Computer Science October 3, 2000 Professors Nancy Lynch and Srinivas Devadas

Problem Set 5

Due: 2:35pm in lecture, Thursday, October 12, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study: Simple algorithms and pseudocode Read: Rosen Section 2.1 Self-study problems (not to be handed in): 1, 3, 5, 7, 9, 11, 19

—————————————————————————–

Reading: Lecture notes; Rosen 2.1, 3.5 (skim)

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 In ancient times, the downtown section of Verona was laid out in a 1000 by 1000 meter square. Romeo lived at grid point (0, 0) of the square, and Juliet lived at grid point (0, 1000). Of course, Romeo and Juliet wanted to meet, at exactly the same point in the square. However, both were restricted by their rather strange families to move according to very particular rules: Romeo could only move 3 units, parallel to either the x axis or y axis or at a 45 degree angle to both axes. Juliet could only move 3 units, and only parallel to either the x axis or y axis.

(a) Model Romeo and Juliet and their possible moves as a (single) state machine. That is, define the states Q, the start state Q_{0}, and the transitions δ.

Solution:

Q = {(R_{x}, R_{y}, J_{x}, J_{y})|R_{x}, R_{y}, J_{x}, J_{y} ∈ {0, …, 1000}}, where (R_{x}, R_{y}) and (J_{x}, J_{y}) are the positions of Romeo and Juliet, respectively.

Q_{0} = {(0, 0, 0, 1000)}

δ : (R_{x}, R_{y}, J_{x}, J_{y}) → (R_{x} + 3a, R_{y} + 3b, J_{x} + 3c, J_{y} + 3d)), where (a, b, c, d) ∈ {(1, 0, 0, 0), (−1, 0, 0, 0), (0, 1, 0, 0), (0, −1, 0, 0), (1, 1, 0, 0), (1, −1, 0, 0),

(−1, 1, 0, 0), (−1, −1, 0, 0), (0, 0, 1, 0), (0, 0, −1, 0), (0, 0, 0, 1), (0, 0, 0, −1)}

(b) Can Romeo and Juliet meet by some sequence of moves? If yes, then give such a sequence of moves. If no, then prove formally (using an invariant) that no sequence of moves can yield a meeting.

Solution: We show that for all reachable states q = (R_{x}, R_{y}, J_{x}, J_{y}),

R_{x} + R_{y} − J_{x} − J_{y} ≡ 2 (mod 3).

For notational convenience, let r(q) = R_{x} + R_{y} − J_{x} − J_{y}. For the only possible initial state q_{0}, r(q_{0}) = −1000, so r(q_{0}) ≡ 2 (mod 3). For any transition from state q to state q′, we note that r(q′) − r(q) is always a multiple of 3. Hence r(q′) ≡ 2 (mod 3) implies r(q) ≡ 2 (mod 3).

Suppose, for a contradiction, that Romeo and Juliet can meet in some state q. That would imply that r(q) = 0. However, we just showed that r(q) can never be 0, which yields a contradiction.

Problem 2 In the late 1960s, the military junta that ousted the government of the small republic of Miranda outlawed multiplication and division by any number other than 3. When democracy was reinstated 30 years later, people were interested in rediscovering the lost art of multiplication. A young inventor came up with the following algorithm to multiply any two natural numbers x and y using only multiplication and division by 3:

procedure multiply(x, y: natural numbers) r := x; s := y; a := 0; do until s = 0

if s ≡ 0 (mod 3) then r := 3r;

s := s/3;

else if s ≡ 1 (mod 3) then a := a + r;

r := 3r;
s := (s − 1)/3;

else

a := a + 2r;
r := 3r;
s := (s − 2)/3;

return a;

(a) Model the algorithm as a state machine (Q, Q_{0}, δ).

Solution:

Q = {(r, s, a, x, y)|r, s, a, x, y ∈ ℕ}

Q_{0} = {(x, y, 0, x, y)} δ : (r, s, a, x, y) → (3r, s′, a′, x, y), where

If s ≡ 0 (mod 3): s′ = s/3, and a′ = a

If s ≡ 1 (mod 3): s′ = (s − 1)/3, and a′ = a + r If s ≡ 2 (mod 3): s′ = (s − 2)/3, and a′ = a + 2r

(b) List the sequence of steps that appears in the execution of the algorithm for inputs x = 5 and y = 10.

Solution: (5, 10, 0, 5, 10) → (15, 3, 5, 5, 10) → (45, 1, 5, 5, 10) → (135, 0, 50, 5, 10)

(c) Prove that the algorithm gives the correct answer if it terminates, that is, that s = 0 implies a = xy. (Hint: Use induction on the number of steps in the execution. You will have to strengthen the inductive hypothesis.)

Solution: We prove the following invariant.

P (r, s, a, x, y) = “xy = rs + a”.

Base case: For any initial state we have P (x, y, 0, x, y) which is true.

Inductive step: Consider a transition from (r, s, a, x, y) to (r′, s′, a′, x′, y′). We need to prove that P (r, s, a, x, y) → P (r′, s′, a′, x′, y′). We consider three cases:

If s ≡ 0 (mod 3), then r′s′ + a′ = (3r)\frac{s}{3} + a = rs + a = xy = x′y′.

If s ≡ 1 (mod 3), then r′s′ + a′ = (3r)\frac{s−1}{3} + (a + r) = rs + a = xy = x′y′.

If s ≡ 2 (mod 3), then r′s′ + a′ = (3r)\frac{s−2}{3} + (a + 2r) = rs + a = xy = x′y′.

In all three cases, the last equality was derived by applying the inductive hypothesis, and in all cases P (r′, s′, a′, x′, y′) holds. When s = 0, the we get that a = xy. We also know that the algorithm terminates when s = 0. It follows, therefore, that if the algorithm terminates, then the correct answer is produced.

(d) Prove that the algorithm terminates.

Solution:

We first notice that s ≥ 0 for any reachable execution state. We prove that this is an invariant by showing it is true for the base case, y ≥ 0, and furthermore, no transition exists from a state with s ≥ 0 to s < 0 in all cases.

Now consider the value of s during any valid execution. Since s ≥ 0, as shown above, no transition increases s. Furthermore, for s > 0, all transitions decrease s by at least 1. Thus for any values of x, y ∈ ℕ, s decreases to 0 in a finite number of steps, and thus the program terminates in a finite number of steps.

Problem 3 Shah Shahryar’s wife betrays him with a slave and he vows revenge on all women. Each night, he will marry a new bride and the next morning have her beheaded. One night comes beautiful Sheherezade and presents the Shah with a game:

You have three numbers: 1, 1 and 2. At each time, you are allowed to replace any two numbers x, y with \frac{x+y}{\sqrt{2}} , \frac{x−y}{\sqrt{2}} , but you must not change your third number. You will win only if, using this rule, you can obtain the numbers a, b and c.

(a) Model Sheherezade’s game as a state machine. (Note: The representation is a little tricky because the numbers are not ordered.)

Solution:

Q = ℝ^{3}

Q_{0} = {(1, 1, 2)}

δ : (x, y, z) → (\frac{x+y}{\sqrt{2}} , \frac{x−y}{\sqrt{2}} , z) or (x, y, z) → (x′, y′, z′), where (x′, y′, z′) is a permutation of (x, y, z).

For each of the following choices of a, b and c, say whether or not the Shah can win the game. If yes, show a sequence of winning steps. If no, provide a proof using an invariant.

(b) (a, b, c) = (\frac{3\sqrt{2}}{2}, \frac{\sqrt{2}+1}{2}, \frac{\sqrt{2}−1}{2})

Solution: Yes. (1, 1, 2) → (2, 1, 1) → (\frac{3\sqrt{2}}{2}, \frac{\sqrt{2}}{2}, 1) → (\frac{3\sqrt{2}}{2}, \frac{\sqrt{2}+1}{2}, \frac{\sqrt{2}−1}{2}).

(c) (a, b, c) = (\frac{\sqrt{3}−1}{2}, \frac{\sqrt{3}+1}{2}, 7)

Solution: No. The predicate

P (x, y, z) : x, y, z ∈ \{p + q\sqrt{2}|p, q ∈ ℚ\}

is an invariant for the state machine. For the base case and the permutation transitions, the claim is evident. For the transitions of type (x, y, z) → (x′, y′, z′) where (x′, y′, z′) = (\frac{x+y}{\sqrt{2}} , \frac{x−y}{\sqrt{2}} , z), let x = p+q\sqrt{2}, y = r+s\sqrt{2}, z = u+v\sqrt{2}. Then x′ = 2(q+s)+(p+r)\sqrt{2}, y′ = 2(q−s)+(p−r)\sqrt{2}, z′ = z, so P (x, y, z) → P (x′, y′, z′).

To finish the proof, we show that \frac{\sqrt{3}−1}{2} is not of the form p + q\sqrt{2} for p, q ∈ ℚ. To derive a contradiction, let’s assume that

\frac{\sqrt{3} − 1}{2} = p + q\sqrt{2}.

If q = 0, then \sqrt{3} = 2p + 1. Since 2p + 1 ∈ ℚ, this is impossible. If q ≠ 0, we can rearrange terms to obtain

\sqrt{3} − q\sqrt{2} = 2p + 1.

Squaring this expression and rearranging terms again yields

\sqrt{6} = \frac{3 + 2q^{2} − (2p + 1)^{2}}{q}

this implies \sqrt{6} ∈ ℚ. Contradiction. It follows that P (\frac{\sqrt{3}−1}{2}, \frac{\sqrt{3}+1}{2}, 7) is false.

(d) (a, b, c) = (1, 2, 2)

Solution: No. The predicate

P (x, y, z) : x^{2} + y^{2} + z^{2} = 6

is an invariant for the state machine. For the base case and the permutation transitions, the claim is evident again. For the transitions of type (x, y, z) → (\frac{x+y}{\sqrt{2}} , \frac{x−y}{\sqrt{2}} , z), we have x^{2} + y^{2} + z^{2} = (\frac{x+y}{\sqrt{2}} )^{2}+ (\frac{x−y}{\sqrt{2}} )^{2} + z^{2}. Since P (1, 2, 2) does not hold, the state (1, 2, 2) is not reachable.

Problem 4 Consider the matching problem from lecture.

(a) For a particular value of n, give an example of a stable match between n boys and n girls where no person gets their first choice.

Solution:

Let n = 3. Call the boys 1, 2, 3 and the girls a, b, c. Consider the following preference list:

choice 1st 2nd 3rd choice 1st 2nd 3rd
1  a b  c  a  2 3  1
2  b c  a  b  3 1  2
3  c a  b  c  1 2  3

The matching (1, b), (2, c), (3, a) is stable even though no person gets their first choice.

(b) Can a stable match where no person gets their first choice be produced by the matching algorithm described in class? If yes, state an example and show why the example works. If not, prove using an invariant.

Solution:

Yes. For n = 4, for boys 1, 2, 3, 4 and the girls a, b, c, d, the following preference list yields such a match (x choices don’t matter):

choice 1st 2nd 3rd 4th choice 1st 2nd 3rd 4th
1  a c  x  x  a  3 2  1  4
2  b a  x  x  b  1 4  3  2
3  b d  x  x  c  x 1  x  x
4  a b  x  x  d  x 3  x  x

The matching algorithm executes as follows:

Round 1 a picks 1. b picks 3. 2, 4 are dropped.

Round 2 a picks 2. b picks 4. 1, 3 are dropped.

Round 3 c picks 1. d picks 3.

Problem 5 Consider an instance of the matching problem with n boys and n girls. Call a person unlucky if he or she is matched up with one of his or her ⌊\frac{n}{2}⌋ last choices. In this problem, we will prove the following:

Theorem The matching algorithm from class never produces a matching in which every person is unlucky.

Fix an execution of the matching algorithm. Define the variables B_{i}, G_{i}, i ∈ {1, 2, …, n} as follows:

B_{i} = j if the i-th boy is currently courting the j-th girl on his list

G_{i} is the number of boys that the i-th girl has rejected.

(a) Show that ∑_{i=1}^{n} B_{i} − ∑_{i=1}^{n} G_{i} is preserved at each step of the matching algorithm.

Solution: Let S = ∑_{i=1}^{n} B_{i} − ∑_{i=1}^{n} G_{i}. Suppose that at step t, boy b_{i} proposes to girl g_{j}. There are three possible outcomes:

If g_{j} has not had any previous proposals, she must accept. In this case, none of the B_{i}s and none of the G_{j}s change, so S is preserved.

If g_{j} rejects, then G_{j} increases by 1, B_{i} increases by 1, and the other Bs and Gs remain the same. S is preserved again.

If g_{j} accepts b_{i} because she likes him better than her current mate b_{i′}, then G_{j} increases by 1, B_{i′} increases by 1, and the other Bs and Gs remain the same. S is preserved in this case as well.

(b) Formulate an invariant that you can use to prove the theorem, and show that your invariant is correct.

Solution: Let P : S = n. In the initial state, this is true because everyone is courting the first girl on their list. From part (a) it follows that all transitions preserve the truth value of P. Therefore P is an invariant.

(c) Use your invariant to prove the theorem.

Solution: We prove the statement by contradiction. Consider a match M in which every person is unlucky. Then:

For every i ∈ \{1, …, n\}, B_{i} ≥ ⌈\frac{n}{2}⌉ + 1, and

For every i ∈ \{1, …, n\}, G_{i} ≤ ⌊\frac{n}{2}⌋ − 1.

It follows that ∑_{i=1}^{n} B_{i} − ∑_{i=1}^{n} G_{i} ≥ 2n. This violates the invariant P.