(Prob. 1) Say A1, A2, . . . , Am and B1, B2, . . . , Bm are all subsets of {1, 2, . . . , n}
such that |Ai ∩ Bj
| is even if i 6= j and |Ai ∩ Bi
| is odd for all
i. Show that m ≤ n.
(Prob 2) Say A1, A2, . . . , Am are subsets of {1, 2, . . . , n} such that |Ai
| is
even for all i and |Ai ∩ Aj
| is odd whenever i 6= j. Prove that
m ≤ n. (Hint: you can do this without linear algebra, given
what you learned using linear algebra.)
(Prob 3) Show that, for each positive integer n, there is some way to
direct each edge in the complete graph Kn so that there are at
least n!/2
n−1 paths v1, e1, v2, e2, …., vn−1, en−1, vn such that
– v1, v2, . . . , vn are all the n vertices of Kn, and
– for 1 ≤ i ≤ n − 1, the edge ei has been directed from vi−1
to vi
.
To clarify: think of the vertices as houses each edge as a street.
So, there is exactly one street between any two houses. By
directing edges, we make each edge a one-way street. We are
trying to show that we can put up one-way signs so that there
are at least n!/2
n−1 different ways (that’s a lot of ways!) to start
at some house and take a drive that visits each house exactly
once, without breaking the law. Note that the drive is allowed
to start at any house – two different drives can start at different
houses.
Sample Solution
