\documentclass{article}
\usepackage{amssymb,graphics}

\def\mod#1{\ ({\rm mod\ }#1)}

\begin{document}
\begin{center}
{\Large
MATH 2113/CSCI 2113, Discrete Structures II

Winter 2008

Toby Kenney

\large Homework Sheet 5

Due: Wednesday 13th February: 1:30 PM}
\end{center}

\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] We have 10 points in a square of side 3cm. Show that two of the points are 
within $\sqrt{2}$cm of each other.

\item[2] (a) You are dealt 13 cards. You may choose 5 of them to make a poker 
hand. Assuming you make the best poker hand possible from the 13 cards, what is the 
worst hand you can end up with (and why)? [The type of hand is sufficient -- you don't 
need to give the exact cards.]

(b) What if you are dealt 17 cards? [You still have to create a 5-card hand.]

\item[3] (i) Find the generating function for ${n\choose k}k^2$ as a function of 
$k$. [Hint: You know the generating function for $n\choose k$.]

(ii) Deduce that ${\sum_{k=1}^n {n\choose k}k^2}=2^{n-2}n(n+1)$. 
[Recall that we also showed this in a different way on sheet 2.]

\item[4] At a party, there are $n$ people. Each of them knows some number of the 
other people. Show that there are some two people at the party who know the same number 
of other people. [You may assume that if $A$ knows $B$ then $B$ also knows $A$.]

\item[5] I have a sequence of integers $a_1,a_2,\ldots,a_n$ with the property that 
for any $i\leqslant j$, $a_i+a_{i+1}+\ldots+a_j$ is not a multiple of 17. What is the 
largest possible value of $n$. Justify your answer.

\item[6] There are 100 students in a class. There are 9 homework sheets. 

(a) Suppose that for each homework sheet at least $n$ students hand in solutions. 
How large does $n$ have to be to ensure that there is some student who attempts 
all the homework sheets?

(b) Suppose now that each student submits solutions to at least $m$ of the homework 
sheets. How large must $m$ be to ensure that there are 2 students who submit solutions 
to the same set of homework sheets?

\end{list}

\end{document}
