Homework 4 Non-crossing Matchings and Power Sets

1. Non-crossing Matchings (20 points)
In this problem, you will show that given n red points and n blue points in the plane such that no three
points lie on a common line, it is possible to draw line segments between red-blue pairs so that all the
pairs are matched and none of the line segments intersect. Assume there are n red and n blue points
fixed in the plane.
(a) [6 Points] A matching M is a collection of n line segments connecting distinct red-blue pairs. The
total length of a matching M is the sum of the lengths of the line segments in M. Say that a
matching M is minimal if there is no matching with a smaller total length. Let IsMinimal(M) be
the predicate that is true precisely when M is a minimal matching. Give an (informal) argument
in English explaining why there must be at least one matching M so that IsMinimal(M) is true.
In other words: 9MIsMinimal(M). (The domain of discourse is all matchings.)
(b) [9 Points] Let HasCrossing(M) be the predicate that is true precisely when there are two line
segments in M that cross each other. Give an (informal) argument in English explaining why
8M(HasCrossing(M) ! :IsMinimal(M))
You may need to draw a picture and remember some high school geometry.
(c) [5 Points] Now use the two results above to give a formal proof of the statement:
9M:HasCrossing(M):
12. X − Y + Y = X (14 points)
Let X ⊆ Z, and y 2 Z. Consider the following possible identity:
(X n fyg) [ fyg =? X
(a) [7 Points] Prove or disprove (X n fyg) [ fyg ⊆ X.
(b) [7 Points] Prove or disprove X ⊆ (X n fyg) [ fyg.
3. Power Sets (16 points)
Prove or disprove the following statements:
(a) [8 Points] For any two sets S and T , it holds that:
P(S [ T ) = P(S) [ P(T ) [ P(S \ T ):
(b) [8 Points] For any two sets S and T , it holds that:
P(S \ T ) = P(S) \ P(T ):
4. Cartesian Elimination (15 points)
Let A; B; and C be non-empty sets. Prove that (A × B = A × C) ! B = C.
What happens if A is empty?
5. Modular Numerology (20 points)
Let a; b be integers and p; m be positive integers. Let c = a mod p and d = b mod p. Prove that if
m j p and a ≡ b (mod m), then
c ≡ d (mod m):
6. Prime Examples (15 points)
Prove that for any prime p 3, either p ≡ 1 (mod 6) or p ≡ 5 (mod 6).
7. Extra Credit:: Lottery (-NoValue- points)
A ticket in the lottery consists of six numbers chosen from 1; 2; : : : ; 48. After everyone has bought their
tickets, the manager picks 5 winning numbers from this set at random. Your ticket wins if it contains
each of these winning numbers (order is irrelevant). Prove that if you buy all possible tickets for which
the sum of the six entries on the ticket is divisible by 47, then you are guaranteed to have a winner.
2