Do seven questions. Of these at least three should be from section A and at least three from section B. If you work more than the required number of problems, make sure that you clearly mark which problems you want to have counted. Standard results from the courses may be used without proof provided they are clearly stated. If you have doubts about the wording of a problem or about what results may be assumed without proof, please ask for clarification. In no case should you interpret a problem in such a way that it becomes trivial.

## Section A.

## Question 1.

a. State and prove the Principle of Inclusion/Exclusion.

b. How many surjective maps are there from $\{ 1 , 2 , \ldots , n \}$ to $\{ 1 , 2 , \ldots , k \} ?$ Justfiy your answer.

Question 2. State and prove the Erd˝os-Ko-Rado Theorem concerning the maximum size of an intersecting family of k-sets.

Question 3.

a. Compute

$$
\sum _ { k = 0 } ^ { \lfloor n / 2 \rfloor } { \binom { n } { 2 k } } .
$$

b. Let $c _ { n }$ be the number of monotonically increasing functions from $\{ 1 , 2 , \ldots , n \}$ to itself with the property that $f ( i ) \leq i$ for all i. Find a recurrence relation satisfied by the sequence $( c _ { n } ) _ { 1 } ^ { \infty }$

## Question 4.

a. State and prove Burnside’s Lemma

b. How many distinguishable ways are there to color the faces of an octahedral die with the colors red, white, and blue? [Octahedral dice are available on request from the proctor.]

Question 5. Let C be a binary code of length n with minimum distance $d > n / 2$ having M codewords. Enumerate C as $C = \{ c _ { 1 } , c _ { 2 } , \dots , c _ { M } \}$

a. Prove that

$$
M ( M - 1 ) d \leq \sum _ { i = 1 } ^ { M } \sum _ { j = 1 } ^ { M } d ( c _ { i } , c _ { j } ) \leq { \frac { n M ^ { 2 } } { 2 } } .
$$

b. Deduce that C has at most $2 d / ( 2 d - n )$ codewords. (This bound is called the Plotkin bound.)

## Section B.

Question 6. Suppose that $d , d ^ { \prime }$ are metrics on the set X with $d ( x , y ) \leq d ^ { \prime } ( x , y )$ for every $x , y \in X$ . Show that the metric topology $( X , d )$ is coarser than the metric topology $( X , d ^ { \prime } )$

Question 7. A toplogical space $( X , \tau )$ is called limit-point compact if every infinite subset A of X has a limit point. Show that every closed subset of a limit-point compact space is limit-point compact.

Question 8. Let $S ^ { 1 } \subseteq \mathbb { R } ^ { 2 }$ denote the unit sphere (with the subspace topology), and R the real line with the usual topology. Show that for every continuous map $f : S ^ { 1 } \to$ R there is an $x \in S ^ { 1 }$ with $f ( x ) = f ( - x )$

Question 9. Let $\tau , \tau ^ { \prime }$ be two topologies on X. Show that if $( X , \tau )$ is compact and Hausdorff, $\mathcal { T } \subseteq \mathcal { T } ^ { \prime }$ and $\mathcal { T } \neq \mathcal { T } ^ { \prime }$ , then $( X , T ^ { \prime } )$ is Hausdorff but not compact.

Question 10. Recall that a topological space X is locally connected if for every point $x \in X$ and every neighbourhood U of x there exists a connected neighbourhood V of x with $V \subseteq U$

a. Prove that a topological space X is locally connected iff for every open set $U \subseteq X$ the components of U are open. Now let $p : X \to Y$ be a quotient map.

b. Prove that if C is a component of an open subset $U \subseteq Y$ then $p ^ { - 1 } ( C )$ is a union of components of $p ^ { - 1 } ( U )$ c. Deduce that if X is locally connected then so is Y .