a) Proof by contradiction

• if w1 is not matched to m1, w1 must be matched with someone ranked higher than m1, which is m2

• however, m2 would propose to w2 before w1 and would not propose again unless w2 reject m2

• w2 would reject m2 only if m1 propose to w2, but m1 would only propose to w2 if m1 is rejected by w1

• So w1 can never matched to m2 since by the time m1 propose to w1, w1 and m1 would be matched and there's no reason that m1 will propose to m2 again.

• Thus, w1 can only be matched with m1

  Similarly, m2 can only be matched with w2 for the same logic since m2 would propose and match to w2 and m1 would never propose to w2 to break that match

  b) Proof by contradiction

  Let's say in a stable matching, m1 and w1 are not matched to either w1 or w2 but instead they are matched to w1' or w2' and w1 and w2 are matched to m1' and m2'

Since we are given the preference list, we know that the new preference list would look like this:

m1: w1 > w2 > ... > w1' > ...
m2: w2 > w1 > ... > w2' > ...
w1: m2 > m1 > ... > m1' > ...
w2: m1 > m2 > ... > m2' > ...

From the preference list, we can easily find out that if m1 is matched to w1' instead of w1 or w2 and w1 is matched with m1', this paring would be unstable since m1 prefer w1, w2 over w1' and w1 prefer m1 over m1'. Similar for w2 and m2.

Thus, for stable matchings, m1 can only match to either w1 or w2 and m2 can only match to w1 or w2 too, otherwise there would be unstable edges exist in the matching, making the whole match unstable.

def find(A):
	left, right = 1, length(A)
	while left <= right:
		mid = (left + right) / 2
		if A[mid] == mid:
			return True
		else if A[mid] > mid:
			right = mid -1
		else if A[mid] > mid:
			left = mid + 1
	return False
		

1 3 4 6 7

l       r
1 2 4 5 6
    ^
    3